1 of 2

Division and Greatest common divisor

Author: Zademn

Introduction

Two of the skills a cryptographer must master are:

Knowing his way and being comfortable to work with numbers.
Understanding and manipulating abstract objects.

This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Let $\mathbb{Z} = \{\dots , -1, 0, 1, 2, 3 \dots \}$ be the set denoting the integers.

Definition - Divisibility

For $a, b, \in \mathbb{Z}$ we say that $a$ divides $b$ if there is some $k \in \mathbb{Z}$ such that $a \cdot k = b$
Notation: $a | b$

Example

For $a = 2, b = 6$ we have $2 | 6$ because we can find $k = 3$ such that $6 = 2 \cdot 3$ .

Properties

Definition - Division with remainder

Examples:

q, r = divmod(6, 2)
print(q, r)
# 3 0 

q, r = divmod(13, 5)
print(q, r)
# 2 3 
# Note that 13 = 2 * 5 + 3

q = 13 // 5
print(q)
# 2

r = 13 % 5
print(r)
# 3

Exercises:

Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Examples:

# In python we can import math to get the GCD algo
import math
print(math.gcd(18, 12)) # -> 6
# Sage has it already!
print(gcd(18, 12)) # -> 6

Remark:

Things to think about

Euclidean Algorithm

Introduction

Although we have functions that can compute our $\gcd$ easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

If $a = b \cdot q + r$ and $d = \gcd(a, b)$ then $d | r$ . Therefore $\gcd(a, b) = \gcd(b, r)$

Algorithm

We write the following:

$a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0$

Or iteratively $r_{k-2} = q_k \cdot r_{k-1} + r_k$ until we find a $0$ . Then we stop

Now here's the trick:

\gcd(a, b) = gcd(b, r_0) = gcd(r_0, r_1) = \dots = \gcd(r_{n-2}, r_{n-1}) = r_{n-1} = d

Pause and ponder. Make you you understand why that works.

Example:

Code

def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3

Exercises:

Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

This section needs to be expanded a bit.

Bezout's identity

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3

Division and Greatest common divisor

Author: Zademn

Introduction

Two of the skills a cryptographer must master are:

Knowing his way and being comfortable to work with numbers.
Understanding and manipulating abstract objects.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Let $\mathbb{Z} = \{\dots , -1, 0, 1, 2, 3 \dots \}$ be the set denoting the integers.

Definition - Divisibility

For $a, b, \in \mathbb{Z}$ we say that $a$ divides $b$ if there is some $k \in \mathbb{Z}$ such that $a \cdot k = b$
Notation: $a | b$

Example

For $a = 2, b = 6$ we have $2 | 6$ because we can find $k = 3$ such that $6 = 2 \cdot 3$ .

Properties

$a | a, \ 1 | a \text{ and } a | 0$
$a | b$ and $a | c$ implies $a | (bu + cv) \ \forall u, v, \in \mathbb{Z}$
- Example: Let $b = 6, u = 5$ and $c = 9, v = 2$
- $3 | 6$ and $3 | 9 \Rightarrow 3 | (6 \cdot 5 + 9 \cdot 2) \iff 3 | 48$ . We can find $k = 16$ such that $48 = 3 \cdot 16$
$a | b$ and $b | c$ implies $a | c$
if $a|b$ and $b|a$ then $a = \pm b$

Definition - Division with remainder

Let $a, b \in \mathbb{Z}$ with $b≥1$ ,
There exists unique $q, r \in \mathbb{Z}$ such that $\boxed{a = bq + r}$ and $0 \leq r < b$
$q$ is called the quotient and $r$ the remainder

Examples:

To find $q, r$ python offers us the divmod() function that takes $a, b$ as arguments

q, r = divmod(6, 2)
print(q, r)
# 3 0 

q, r = divmod(13, 5)
print(q, r)
# 2 3 
# Note that 13 = 2 * 5 + 3

If we want to find only the quotient $q$ we can use the // operator
If we want to find the remainder $r$ we can use the modulo % operator

q = 13 // 5
print(q)
# 2

r = 13 % 5
print(r)
# 3

Exercises:

Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Let $a, b \in \mathbb{Z}$ be 2 integers. The greatest common divisor is the largest integer $d \in \mathbb{Z}$ such that $d | a$ and $d | b$
Notation: $\gcd(a, b) = d$

Examples:

# In python we can import math to get the GCD algo
import math
print(math.gcd(18, 12)) # -> 6
# Sage has it already!
print(gcd(18, 12)) # -> 6

Remark:

for all other common divisors $c$ of $a, b$ we have $c | d$

Things to think about

What can we say about numbers $a, b$ with $\gcd(a, b) = 1$ ? How are their divisors?

Euclidean Algorithm

Introduction

Although we have functions that can compute our $\gcd$ easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

If $a = b \cdot q + r$ and $d = \gcd(a, b)$ then $d | r$ . Therefore $\gcd(a, b) = \gcd(b, r)$

Algorithm

We write the following:

$a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0$

Or iteratively $r_{k-2} = q_k \cdot r_{k-1} + r_k$ until we find a $0$ . Then we stop

Now here's the trick:

\gcd(a, b) = gcd(b, r_0) = gcd(r_0, r_1) = \dots = \gcd(r_{n-2}, r_{n-1}) = r_{n-1} = d

If $d = \gcd(a, b)$ then $d$ divides $r_0, r_1, ... r_{n-1}$

Pause and ponder. Make you you understand why that works.

Example:

Calculate $\gcd(24, 15)$

$24 = 1 \cdot 15 + 9 \\ 15 = 1 \cdot 9 + 6 \\ 9 = 1 \cdot 6 + 3 \\ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15)$

Code

def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3

Exercises:

Pick 2 numbers and calculate their $\gcd$ by hand.
Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

This section needs to be expanded a bit.

Bezout's identity

Let $d = \gcd(a, b)$ . Then there exists $u, v$ such that $au + bv = d$

The extended euclidean algorithm aims to find $d = \gcd(a, b), \text{ and }u, v$ given $a, b$

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3