Ref. Chapter 8 INTRODUCTION TO MODERN CRYPTOGRAPHY by Jonathan Katz and Yehuda Lindellbar
Let us consider $\mathbb Z$ the set of integers and $\mathbb N$ the set of natural numbers.
Definition ($a|b$) : $a \in \mathbb Z$ divides $b \in \mathbb Z$ if there exists an integer $c$ such that $ac=b$. If $a$ is positive, we say that $a$ is a divisor of $b$.
Definition: An integer $p\ne\pm 1$ is a prime if whenever $p|ab$, then $p|a$ or $p|b$.
Proposition 1: Let $p\in \mathbb Z $ and $p \ne \pm 1$. $p$ is a prime if and only if it has only two divisors, i.e. 1 and $p$.
Theorem (Fundamental theorem of arithmetic/Unique factorization): Every integer $n>1$ can be decomposed uniquely (up to permutation) as a product of prime factors. More precisely, there exist unique $p_1<\dots<p_k$ prime integers and $e_1,\dots e_k\in\mathbb N^+$ such that $$ n= \prod_{j=1}^k p_j^{e_j}$$
We call this decomposition the factorization of $n$.
Theorem 2: Let $a \in \mathbb Z$ and $b \in \mathbb N$. There exists unique integers $q,r$ such that $a=qb+r$ and $0\le r< b$.
We call $r$ the reminder of the division of $a$ by $b$.
CompFact: There exist an algorithm to compute $r,q$ in polyonomial time (Polynomial what??).
a,b,c=10,5,3
qb=a//b
qc=a//c
rb=a%b
rc=a%c
print(qb,rb)
2 0
a==qb*b+rb
True
print(qc,rc)
3 1
a==qc*c+rc
True
f=451
g=21
print(f//g,f%g)
21 10
Definition: Let $a,b \in \mathbb Z$. The greatest common divisor of $a$ and $b$ is $$gcd(a,b)=\max \{c \in \mathbb Z ~:~ c|a~~~ and ~~~ c|b \}.$$
Definition: Let $a,b \in \mathbb Z$. If $gcd(a,b)=1$ we say that they are coprime.
from math import gcd
gcd(21,81)
3
CompFact: The Euclidian algorithm computes the gcd in polyonomial time (Polynomial what??). We will see this algorithm.
CompOpenQuest: Can we compute the factorization?? Ideas??
L=[36, 44, -45, -38, -14, -50, 35, -49, -34, -12, 43,37, 24, -37, 40, -11, 7, 38]
[x%5 for x in L]
[1, 4, 0, 2, 1, 0, 0, 1, 1, 3, 3, 2, 4, 3, 0, 4, 2, 3]
Let us consider $a,r,N\in \mathbb Z$ and $N>1$. Suppose $r$ is the reminder of the division of $a$ by $N$. We define $$[a \mod N]=r.$$ r is also called class of a modulo N.
The reduction mod N is the mapping $a \rightarrow [a \mod N]$. Notice that $$ [* \mod N ]: \mathbb Z \rightarrow \{0,1,\dots,N-1\}\subseteq\mathbb Z$$
Definition: $a$ and $b$ are congruent modulo N if and only if $[a \mod N]=[b \mod N]$. In such a case we write $a =b \mod N$.
Proposition 2: $a=b\mod N \iff a-b=0 \mod N \iff N|(a-b)$
Exercise. Prove that the congruence modulo N is an equivalence relation.
Compute 674 and -674 modulo 7.
674%7
2
-674%7
5
$-674=-679 +5 = - 97\cdot7 + 5= 5 \mod 7$
Indeed, congruence modulo $N$ commutes with addition and multiplication! Suppose $\bar a=[a \mod N]$ and $\bar b=[b \mod N]$.
print(34%6,13 %6, 13+34, (34 + 13) %6 )
4 1 47 5
(34 % 6) + (13 %6)
5
This is not true for the 'usual' division!
(34 // 13) %6
2
(34 % 6) // (13 %6)
4
Definition: An integer $a\in \mathbb Z$ is invertible modulo N if there exits $y\in \mathbb Z$ such that $ a\cdot y =1 \mod N$.
Attention false friend: $ab = ac \mod N$ does NOT imply $b = c \mod N$!
If $y,y'\in \mathbb Z$ are such that $ a\cdot y= a\cdot y' =1 \mod N$, then $ y=y'\mod N$ (this is not obvious!!). Therefore, we can define $a^{-1}=[y \mod N ] $ the inverse of $a$ modulo $ N $.
( 15*2 )% 24 == (3*2) %24
True
15 % 24 == 3 % 24
False
Definition: Let $b$ be invertible modulo $N$. We define $[a/b \mod N]= [a\cdot b^{-1} \mod N]$.
Proposition 3: Let $a,b,c\in \mathbb Z$ and $a$ be invertible modulo $N$. Then $$ ab = ac \mod N \Rightarrow b = c \mod N.$$
CompFact: We can test in poly time if an integer is invertible mod $N$.
Proposition 4: Let $b,N \in \mathbb Z$ and $N>1$ and $b\ge 1$. Then $b$ is invertible modulo $N$ if and only if $gcd(b,N)=1$.
Lemma GCD: Let $a,b \in \mathbb N$. Then there exist $X,Y\in \mathbb Z$ such that $aX+bY=gcd(a,b)$ and $gcd(a,b)$ is the smallest integer that can be expressed in this way.
Compute if possible the inverse of 13 and 36 mod 6.
from math import gcd
print(gcd(13,6))
print(gcd(34,6))
1 2
Since $13 =1 \mod 6$, the inverse of 13 modulo 6 is 1. While 34 is not invertible.
We want to compute now $[ 9 / 40 \mod 11]$. First we check if 40 is invertible!
40%11
7
(7*8)%11
1
First we check if 40 is invertible, and in such a case we have to find its inverse.
print(gcd(40,11))
1
(-3 *40 + 11*11) % 11
1
-3 % 11
8
(8*40) % 11
1
Finally, we compute $[ 9 \cdot 8 \mod 11]$.
(9*8)%11
6
CompFact: Using the Extended euclidian algorithm we can compute the "division" in polyonomial time (Polynomial what??).
The reduction mod N $a \rightarrow [a \mod N]$
def mod(a,N): return a%N
def eq_mod(a,b, N): return mod(a,N)==mod(b,N)
def sum_mod(a,b,N): return (a+b)%N
def sum_mod(a,b,N): return mod(a+b,N)
def sum_mod(a,b,N): return mod(mod(a,N)+mod(b,N),N)
def prod_mod(a,b,N): return (a*b)%N
def prod_mod(a,b,N): return mod(mod(a,N)*mod(b,N),N)
def pow_mod(a,k,N): return (a**k)%N
To check if $a$ is invertible we want to use Propostion 4. So we have to compute the GCD.
Euclidean algorithm:
Output: $gcd(a,b)$
1) Set $r_0 = a$ and $r_1 = b$.
2) For $i\ge 2$, compute $q_i,r_i$ such that $ r_i=r_{i-2}-q_ir_{i-1}$ and $0\le r_i<|r_{i-1}|$ until $r_k=0$.
3) return $r_{k-1}$.
def gcd(a,b):
if a<b: a,b = b,a
if a%b==0 : return b
else: return gcd(b, a%b)
gcd(56,12)
4
def is_inv_mod(a,N): return gcd(a,N)==1
is_inv_mod(12,15)
False
Extended Euclidean algorithm:
Output: $gcd(a,b)$,$X,Y$ such that $aX+bY=gcd(a,b)$.
1) Set $r_0 = a$ and $r_1 = b$.
2) Set $X_0=1$, $Y_0=0$, $X_1=0$, $Y_1=1$,
3) For $i\ge 2$ until $r_k=0$ :
compute $q_i,r_i$ such that $ r_i=r_{i-2}-q_ir_{i-1}$ and $0\le r_i<|r_{i-1}|$
$X_i=X_{i-2}-q_iX_{i-1}$
4) return $r_{k-1},X_{k-1},Y_{k-1}$.
Remark: Notice that at each step $r_i=aX_i+bY_i$.
def xgcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = xgcd(b % a, a)
return (g, x - (b // a) * y, y)
xgcd(123,25)
(1, 12, -59)
Since $xgcd$ returns $X,Y$ such that $aX+NY=1$, we have that $a^{-1}=X \mod N$
def inv_mod(a,N):
r,x,y=xgcd(a,N)
#ax+Ny=r
if r==1:
return x%N
else:
raise Exception('%d is not invertible modulo %d' %(a,N))
def div_mod(a,b,N):
ib=invmod(b,N)
return prod_mod(a,ib,N)
inv_mod(123,25)
12
inv_mod(125,25)
--------------------------------------------------------------------------- Exception Traceback (most recent call last) <ipython-input-42-c45380548673> in <module> ----> 1 inv_mod(125,25) <ipython-input-40-d36ade07b57b> in inv_mod(a, N) 5 return x%N 6 else: ----> 7 raise Exception('%d is not invertible modulo %d' %(a,N)) Exception: 125 is not invertible modulo 25