Transcript x - Cinvestav

Códigos y Criptografía
Francisco Rodríguez Henríquez
CINVESTAV
e-mail: [email protected]
Códigos y Criptografía
Francisco Rodríguez Henríquez
Number Theory: Some
definitions and Theorems
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions
The set of integers {…, -3, -2, -1, 0, 1, 2, 3, …} is
denoted by the symbol Z.
Let a, b be integers. Then a divides b if there exists an
integer c such that b = ac. If a divides b, then it is
denoted by a|b.
Examples: -3|18, since 18 = (-3)(-6); any integer a
divides 0, a|0, since 0 = (a)(0).
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: integers
The following are some elementary properties of
divisibility:
Fact: (properties of divisibility) For all a, b, c,  Z, the
following are true:
i. a|a
ii. If a|b and b|c, then a|c
iii. If a|b and a|c, then a|(bx+cy) for all x, y  Z.
iv. If a|b and b|a, then a = ±b
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: division for integers
Definition (division algorithm for integers) If a and b
are integers with b≥1, then ordinary long division
of a by b yields integers q (the quotient) and r (the
remainder) such that
a = qb+r, where 0 ≤ r <b
Moreover, q and r are unique. The remainder of the
division is denoted a mod b, and the quotient is
denoted a div b.
Definition An integer c is a common divisor of a and b
if c|a and c|b.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: gcd
Definition A non-negative integer d is the greatest common
divisor of integers a and b, namely
d = gcd(a, b), if
i.
d is a common divisor of a and b; and
ii. Whenever c|a and c|b, then c|d.
Equivalently, gcd(a, b) is the largest positive integer that divides
both a and b, with the exception that gcd(0,0) = 0.
Definition Two integers a and b are said to be relatively prime or
coprime if gcd(a, b)=1
Definition An integer p≥2 is said to be prime if its only positive
divisor are 1 and p. Otherwise, p is called composite.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: lcm
Definition A non-negative integer d is the least
common multiple of integers a and b, namely
d = lcm(a, b), if
i. a|d is and b|d; and
ii. Whenever a|c and b|c, then d|c.
Equivalently, lcm(a, b) is the smallest positive integer
divisible by both a and b.
Fact If a and b are positive integers, then
lcm(a, b)=a*b/gcd(a, b).
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: Prime Numbers
Definition An integer p≥2 is said to be prime if its only
positive divisor are 1 and p. Otherwise, p is called
composite.
Fact If p is prime and p|ab, then either p|a or p|b or
both. (is it true if p is composite?).
Fact There are an infinite number of prime numbers
(how can we prove it?)
Fact (prime number theorem) Let (x) denote the
number of prime numbers ≤ x. Then
lim
x 
Códigos y Criptografía
 x 
x / ln x
1
Francisco Rodríguez Henríquez
Definitions: Prime Numbers
Fact (upper and lower bounds for (x)). Let (x) denote
the number of prime numbers ≤ x. Then for x≥17
and for x > 1,
x
 x  
ln x
x
  x   1.25506
ln x
Códigos y Criptografía
Francisco Rodríguez Henríquez
Fundamental Theorem of Arithmetic
• Every integer n ≥ 2 has a factorization as a product of
prime powers:
n  p p p ,
e1
1
e2
2
ek
k
• Where the pi are distinct primes, and the ei are positive
integers. Furthermore, the factorization is unique up to
the rearrangement of factors.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Fundamental Theorem of Arithmetic
• Proof: existence [sketch] Suppose there exist positive
integers that are not product of primes. Let n be the
smallest such integer. Then n cannot be 1 or a prime, so
n must be composite. Therefore n = ab with 1 < a, b <
n. Since n is the smallest positive integer that is not a
product of primes, both a and b are product of primes.
But a product of primes times a product of primes is a
product of primes, so n = ab is a product of primes.
Therefore, every positive integer is a product of
primes.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Fundamental Theorem of Arithmetic
• Proof: uniqueness [sketch] If p is a prime and p divides a
product of integers ab, then either p|a or p|b (or both!), (is this
statement true for composite numbers?).
Suppose that an integer n can be written as a product of primes
in two different ways:
as
at
a1 a2
a1 a2
n  p1 p2  ps  q1 q2  qt ,
• If a prime occurs in both factorizations divide both sides by it to
obtain a shorter relation. Now take a prime that occurs on the
left side, say p1. Since p1 divides n then it must divide one of the
factors of the right side, say qj. But since p1 is prime, we are
forced to write p1= qj, which is a contradiction with the original
hyphotesis.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Prime Numbers: How many?
Fact There are an infinite number of prime numbers (how
can we prove it?)
Euclid did it! But how?
Should we have a quizz????
Hint: Follow the same line of reasoning used for FTA…
Any idea???
Códigos y Criptografía
Francisco Rodríguez Henríquez
Fundamental Theorem of Arithmetic
• Fact If a  p1e1 p2e2  pkek , b  p1f1 p2f 2  pkf k ,
where each ei ≥ 0 and fi ≥ 0, then
i k
min e , f 
min e , f 
min e , f  min e , f 


gcd a, b  p1
p2
 pk
  pi
1
1
2
2
k
k
i
i
i 1
and
i k
lcm a, b   p1max e1 , f1  p2max e2 , f 2   pkmax ek , f k    pimax ei , f i 
i 1
Códigos y Criptografía
Francisco Rodríguez Henríquez
Fundamental Theorem of Arithmetic
Example: Let a = 4864 = 2819,
b = 3458 = 2 7 13 19.
Then gcd(4864, 3458) = 2 19 = 38 and,
lcm(4864, 3458)= 287 13 19 = 442624
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: Euler phi Function
Definition For n ≥ 1, let (n) denote the number on
integers in the interval [1, n], which are relatively
prime to n. The function  is called the Euler phi
function (or the Euler totient function).
Fact (properties of Euler phi function)
i.
If p is a prime, then (p) = p-1.
ii.
The Euler phi function is multiplicative. That is, if
gcd(m, n) = 1, then (mn) = (m)(n).
Códigos y Criptografía
Francisco Rodríguez Henríquez
Definitions: Euler phi Function
iii.
If n  p1e p2e  pke ,
then

n   n1 
1
is the prime factorization of n,
k
2

1 
1  
1 
1  1  
p1  p2   pk 
iv. For all integers n ≥ 5,
n
n  
6 ln ln n
Códigos y Criptografía
Francisco Rodríguez Henríquez
Euclidean algorithm
m,n
Euclidean
Algorithm
gcd(m,n)
Fact If a and b are positive integers with a>b, then
gcd(a,b)=gcd(b, a mod b);
gcd(m, n)
x = m, y = n
while(y > 0)
r = x mod y
x=y
y=r
return x
Códigos y Criptografía
Francisco Rodríguez Henríquez
Euclidean algorithm
Example The following are the division steps for
computing gcd(4864, 3458) = 38:
4864 = 1*3458 + 1406
3458 = 2*1406 + 646
1406 = 2*646 + 114
646 = 5*114 + 76
114 = 1*76 + 38
76 = 2*38 + 0
(Which method is more efficient and why??)
Códigos y Criptografía
Francisco Rodríguez Henríquez
gcd: Computational Complexity
Assuming mod operation complexity is K:
integer euclid(m, n)
x = m, y = n
while( y > 0)
r = x mod y
x=y
y=r
return x
K+
¿?  ( O (1) +
K
+ O (1)
+ O (1) )
+ O (1)
= ¿?  K  O(1)
Where “¿?” is the number of while-loop iterations.
Códigos y Criptografía
Francisco Rodríguez Henríquez
gcd: Computational Complexity
Facts: (x’ = next value of x, etc. )
1.
x can only be less than y at very beginning of
algorithm
–once x > y, x’ = y > y’ = x mod y
2.
When x > y, two iterations of while loop guarantee
that new x is < ½ original x
–because x’’ = y’ = x mod y. Two cases:
I.
II.
y > ½ x  x mod y = x – y < ½ x
y ≤ ½ x  x mod y < y ≤ ½ x
Códigos y Criptografía
Francisco Rodríguez Henríquez
gcd: Computational Complexity
(1&2) After first iteration, size of x decreases
by factor > 2 every two iterations.
i.e. after 2i+1 iterations,
x < original_x / 2i
Q: When –in terms of number of iterations i–
does this process terminate?
Códigos y Criptografía
Francisco Rodríguez Henríquez
gcd: Computational Complexity
After 2i+1 steps, x < original_x / 2i
A: While-loop exits when y is 0, which is right
before “would have” gotten x = 0. Exiting
while-loop happens when 2i > original_x,
(why??) so definitely by:
i = log2 ( original_x )
Therefore running time of algorithm is:
O(2i+1) = O(i) = O (log2 (max (a, b)) )
Códigos y Criptografía
Francisco Rodríguez Henríquez
gcd: Computational Complexity
Measuring input size in terms of n = number of digits of
max(a,b):
n = (log10 (max(a,b)) ) = (log2 (max(a,b)) )
Therefore running time of algorithm is:
O(log2 (max(a,b)) ) = O(n)
(Except fot the mod operation complexity K, which in
general is operand-size dependant)
A more formal derivation of the complexity of Euclidean
gcd can be found in section 4.5.3, Volume II of
Knuth’s “The Art of Computing Programming”
Códigos y Criptografía
Francisco Rodríguez Henríquez
Euclidean gcd: Revisited
Properties:
i.
By definition gcd(0, 0) = 0.
ii. gcd(u, v) = gcd(v, u)
iii. gcd(u, v) = gcd(-u, v)
iv. gcd(u, 0) = |u|
v.
gcd(u, v)w = gcd(uw, vw) if w ≥0
vi. lcm(u, v)w = lcm(uw, vw) if w ≥0
vii. uv = gcd(u, v) lcm(u, v) if u, v ≥0
viii. gcd(lcm(u, v), lcm(u, w)) = lcm(u, gcd(v, w));
ix. lcm(gcd(u, v), gcd(u, w)) = gcd(u, lcm(v, w))
Códigos y Criptografía
Francisco Rodríguez Henríquez
Euclidean gcd Revisited
Binary Properties:
i. If u and v are both even, then
gcd(u, v) = 2 gcd(u/2, v/2);
i. If u is even and v is odd, then
gcd(u, v) = gcd(u/2, v);
i. gcd(u, v) = gcd(u-v, v).
ii. If u and v are both odd, then u-v is even and
|u-v| < max(u, v).
Códigos y Criptografía
Francisco Rodríguez Henríquez
Binary gcd algorithm
Input: u, v positive integers, such that u > v.
Output: w = gcd(u, v).
1. for (k = 0; u, v both even; k++) {
u /= 2; v /= 2;
}; /* [Find power of 2] */
2. [Initialize] if (u is odd) t =-v else t = u;
3. [halve t] while (t is even) t /= 2;
4. if (t > 0) u = t else v = -t;
5. [Subtract] t = u-v. If t ≠ 0 go back to 3,
otherwise output w = u2k.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Binary gcd algorithm: Example
Example find the gcd of u =40902, v = 24140.
t
u
v
-12070, -6035
+14416, +901
-5134, -2567
40902
20451
20451
901
24140
6035
6035
6035
-1666, -833
+68, +34, +17
-816, -51
901
901
17
2567
833
833
-34, -17
17
51
0
17
17
Códigos y Criptografía
w=17*21=34
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
The Euclidean algorithm can be extended so
that it not only yields the greatest common
divisor d of two integers a and b, but also
generates x and y satisfying
ax +by = d.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Modular Inverses
THM1: e has an inverse modulo N if and only if e
and N are relatively prime.
This will follow from the following useful fact.
THM2: If a and b are positive integers, the gcd of a
and b can be expressed as an integer combination
of a and b. I.e., there are integers s, t for which
gcd(a,b) = sa + tb
Códigos y Criptografía
Francisco Rodríguez Henríquez
Modular Inverses
Proof of THM1 using THM2:
If an inverse d exists for e modulo N, we have
de  1 (mod N) so that for some k, de = 1 +kN, so
1 = de – kN. This equation implies that any
number dividing both e and N must divide 1,
so must be 1, so e,N are relatively prime.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Modular Inverses
On the other hand, suppose that e,N are
relatively prime. Using THM2, write
1 = se + tN. Rewrite this as se = 1-tN.
Evaluating both sides mod N gives
se  1 (mod N) .
Therefore s is seemingly the inverse e
except that it may be in the wrong range so
set d = s mod N.
•
Códigos y Criptografía
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
A constructive version of THM2 which gives s and t
will give explicit inverses. This is what the extended
Euclidean algorithm does.
The extended Euclidean algorithm works the same as
the regular Euclidean algorithm except that we keep
track of more details –namely the quotient q = x/y in
addition to the remainder r = x mod y. This allows us
to backtrack and write the gcd(a,b) as a linear
combination of a and b.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
0
x = qy + r
-
Códigos y Criptografía
x
y
244 117
gcd = ax+by
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
244=2·117+10
Códigos y Criptografía
x
y
gcd = ax+by
244 117
117 10
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
2
244=2·117+10
117=11·10+7
Códigos y Criptografía
x
y
gcd = ax+by
244 117
117 10
10
7
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
2
3
244=2·117+10
117=11·10+7
10=7+3
Códigos y Criptografía
x
y
gcd = ax+by
244 117
117 10
10
7
7
3
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
2
3
4
244=2·117+10
117=11·10+7
10=7+3
7=2·3+1
Códigos y Criptografía
x
y
gcd = ax+by
244 117
117 10
10
7
7
3
3
1
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
2
3
4
5
244=2·117+10
117=11·10+7
10=7+3
7=2·3+1
3=3·1+0
Códigos y Criptografía
x
y
gcd = ax+by
244 117
117 10
10
7
7
3
3
1
1
0
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
2
3
4
5
244=2·117+10
117=11·10+7
10=7+3
7=2·3+1
3=3·1+0
Códigos y Criptografía
x
y
244 117
117 10
10
7
7
3
3
1
1
0
gcd = ax+by
1=7-2·3
Solve for r. Plug it in.
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
2
244=2·117+10
117=11·10+7
x
y
244 117
117 10
10
7
3
10=7+3
7
3
4
5
7=2·3+1
3
1
1
0
3=3·1+0
Códigos y Criptografía
gcd = ax+by
1=7-2·(10-7)
= -2·10+3·7
1=7-2·3
Solve for r. Plug it in.
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
1
-
2
244=2·117+10
117=11·10+7
x
y
244 117
117 10
10
7
1=-2·10+3·(117-11·10)
= 3·117-35·10
1=7-2·(10-7)
= -2·10+3·7
3
10=7+3
7
3
4
5
7=2·3+1
3
1
1
0
3=3·1+0
Códigos y Criptografía
gcd = ax+by
1=7-2·3
Solve for r. Plug it in.
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
gcd(244,117):
Step
x = qy + r
0
-
1
2
3
244=2·117+10
117=11·10+7
x
y
gcd = ax+by
244 117
117
10
10
1= 3·117-35·(244- 2·117)
= -35·244+73·117
7
1=-2·10+3·(117-11·10)
= 3·117-35·10
1=7-2·(10-7)
= -2·10+3·7
10=7+3
7
3
7=2·3+1
4
3=3·1+0
5 y Criptografía
Códigos
3
1
1
0
1=7-2·3
Solve
forRodríguez
r. PlugHenríquez
it in.
Francisco
Extended Euclidean Algorithm
inverse of 244
modulo 117
gcd(244,117):
Step
x = qy + r
0
-
1
2
3
244=2·117+10
117=11·10+7
x
y
gcd = ax+by
244 117
117
10
10
1= 3·117-35·(244- 2·117)
= -35·244+73·117
7
1=-2·10+3·(117-11·10)
= 3·117-35·10
1=7-2·(10-7)
= -2·10+3·7
10=7+3
7
3
7=2·3+1
4
3=3·1+0
5 y Criptografía
Códigos
3
1
1
0
1=7-2·3
Solve
forRodríguez
r. PlugHenríquez
it in.
Francisco
Extended Euclidean Algorithm
Summary:
Extended Euclidean algorithm
works by keeping track of how remainder r
results from dividing x by y. Last such
equation gives gcd in terms of last x and y.
By repeatedly inserting r into the last equation,
one can get the gcd in terms of bigger and
bigger values of x,y until at the very top is
reached, which gives the gcd in terms of the
inputs a,b.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
Input two positive integers a and b with a ≥ b.
Output d = gcd(a, b) and integers x, y satisfying ax+by =d.
1. if (b = 0) {
d = a; x = 1; y = 0;
Fact: This algorithm has a
Running time of O((lg n)2)
return(d, x, y);
bit operations.
}
2. x2 = 1; x1 = 0; y2 = 0; y1 = 1.
3. while (b >0) {
q  a / b; r  a % b; x  x2  qx1 ; y  y2  qy1 ;
a  b; b  r; x2  x1 ; x1  x; y2  y1 ; y1  y;
}
4. d = a; x = x2; y = y2; return(d, x, y);
Códigos y Criptografía
Francisco Rodríguez Henríquez
Extended Euclidean Algorithm
Example: Let a = 4864 and b = 3458. Hence gcd(a, b) = 38 and
(4864)(32) + (3458) (-45) = 38.
q
1
r
1406
x
1
y
-1
a
b
4864 3458
3458 1406
x2
1
0
x1
0
1
y2
0
1
y1
1
-1
2
2
5
1
646
114
76
38
-2
5
-27
32
3
-7
38
-45
1406
646
114
76
646
114
76
38
1
-2
5
-27
-2
5
-27
32
-1
3
-7
38
3
-7
38
-45
2
0
-91
128
38
0
32
-91
-45
128
Códigos y Criptografía
Francisco Rodríguez Henríquez
Quizz !!
1. Prove that there are an infinite number of
prime numbers.
2. Prove that e has an inverse modulo N if
and only if e and N are relatively prime.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Finite fields: definitions and
operations
FP finite field operations : Addition, Squaring,
multiplication and inversion
Códigos y Criptografía
Francisco Rodríguez Henríquez
What is a Group?
An Abelian group <G, +> is an abstract mathematical object consisting of a set
G together with an operation * defined on pairs of elements of G, here denoted
by +:
 : G  G  G : a, b  a  b
In order to qualify as an Abelian group, the operation has to fulfill the
following conditions:
i.
Closed:
ii.
Associative:
iii.
Commutative:
iv.
Neutral element:
v.
Inverse elements:
Códigos y Criptografía
a, b  G : a  b  G
a, b, c  G : a  b  c  a  (b  c)
a, b  G : a  b  b  a
0  G, a  G : a  0  a
a  G, b  G : a  b  0
Francisco Rodríguez Henríquez
What is a Group?
•
Example: The best-known example of an Abelian Group is <Z, +>
•
Example: The additive group Z15 uses the integers from 0 to 14. Some examples of
additions in Z15 are:
(10 + 12) mod 15 = 22 mod 15 = 7
•
In Z15, 10 + 12 = 7 and 4 + 11 = 0.
Notice that both calculations have answers between 0 and 14.
•
Additive Inverses
– Each number x in an additive group has an additive inverse element in the
group; that is an integer -x such that x + (-x) = 0 in the group. In Z15, -4 =11
since (4 + 11) mod 15 = 15 mod 15 = 0.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Rings (1/2)
1.
2.
3.
A ring <R, +, *> consists of a set R with 2 operations defined on its
elements, here denoted by + and *. In order to qualify as a ring, the
operations have to fulfill the following conditions:
The structure <R, +> is an Abelian group.
The operations * is closed, and associative over R. There is a neutral
element for * in R.
The two operations + and * are related by the law of distributivity:
a, b, c  R : a  b c  a  c  b  c
4.
A ring <R, +. *> is called a commutative ring if the operation * is
commutative.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Rings (2/2)
• The integer numbers, the rational numbers, the real numbers and the
complex numbers are all rings.
• An element x of a ring is said to be invertible if x has a multiplicative
inverse in R, that is, if there is a unique e  R such that:
xu  ux  1
• 1 is called the unit element of the ring.
Códigos y Criptografía
Francisco Rodríguez Henríquez
What is a Field?
•
A structure <F, +, *> is called a field if F is a ring in which the multiplication
is commutative and every element except 0 has a multiplicative inverse. We
can define the field F with respect to the addition and the multiplication if:
 F is a commutative group with respect to the addition.
• F  0 is a commutative group with respect to the
multiplication.
 The distributive laws mentioned for rings, hold.
Códigos y Criptografía
Francisco Rodríguez Henríquez
What is a Field?
• A field is a set of elements with two custom-defined arithmetic
operations: most commonly, addition and multiplication. The elements of
the field are an additive abelian group, and the non-zero elements of the
field are a multiplicative abelian group. This means that all elements of
the field have an additive inverse, and all non-zero elements have a
multiplicative inverse.
• A field is called finite if it has a finite number of elements. The most
commonly used finite fields in cryptography are the field Fp (where p is a
prime number) and the field F2m.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Finite Fields
• A finite field or Galois field denoted by GF(q=pn), is a field with
characteristic p, and a number q of elements. As we have seen, such a
finite field exists for every prime p and positive integer n, and contains a
subfield having p elements. This subfield is called ground field of the
original field.
• For the rest of this class, we will consider only the two most used cases
in cryptography: q=p, with p a prime and q=2m. The former case, GF(p),
is denoted as the prime field, whereas the latter, GF(2m), is known as the
finite field of characteristic two or simply binary field.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Finite Fields
• A finite field is a field with a finite number of elements. The
number of elements in a finite field is called the order of the
field. Fields of the same order are isomorphic: they display
exactly the same algebraic structure differing only in the
representation of the elements.
Códigos y Criptografía
Francisco Rodríguez Henríquez
The field Fp
• The finite field Fp (p a prime number) consists of the numbers from 0 to p1. Its operations are addition and multiplication. All calculations must be
reduced modulo p.
• It is mandatory to select p as a prime number in order to guarantee that all
the non-zero elements of the field have a multiplicative inverse.
• Other operations in Fp (such as division, subtraction and exponentiation)
can be derived from the definitions of addition and multiplication.
Códigos y Criptografía
Francisco Rodríguez Henríquez
The field Fp
Example:
Some calculations in the field F23 include
10*4 - 11 mod 23 = 29 mod 23 = 6
7-1 mod 23 = 10 (since 7 * 10 mod 23= 70 mod 23 = 1)
(29) / 7 mod 23 = 512 / 7 mod 23
= 6 * 7-1 mod 23
= 6 * 10 mod 23 = 14
Códigos y Criptografía
Francisco Rodríguez Henríquez
Congruences
Definition: Let a, b, n be integers with n ≠ 0. We say that
a  b mod n , (read: a is congruent to b mod n). If (a-b) is a
multiple (positive or negative) of n, i.e., a = b + nk, for some
integer k.
Examples: 32=7 mod 5, -12 = 37 mod 7.
Proposition: Let a, b, c, d, n be integers with n ≠ 0.
i.
ii.
iii.
iv.
a = 0 mod n iff n|a.
a = a mod n; a = b mod n iff a = b mod n.
If a = b mod n and b = c mod n, then a = c mod n.
a = b mod n and c = d mod n. Then a ± c = b ± d mod n,
ac = bd mod n
Códigos y Criptografía
Francisco Rodríguez Henríquez
Fermat’s Petit Theorem
Theorem: Let p be a prime.
i. If gcd( a, p)  1, then a p 1  1mod p
ii. If r  s mod p  1, then a r  a s mod p, a  
In other words, when working modulo a prime p,
exponents can be reduced modulo p-1.
iii. In particular a p  a mod p, a  
Códigos y Criptografía
Francisco Rodríguez Henríquez
Euler Theorem
Theorem: Let n ≥ 2 be an integer.
Then, If gcd( a, n)  1, then a  n   1mod n
If n is a product of distinct primes, and if
r  s mod n, then a r  a s mod n
In other words, when working modulo such an n,
exponents can be reduced modulo (n).
A special case of Euler’s theorem is Fermat’s petit
theorem.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Euler and Fermat’s theorems examples
Examples:
1. What are the last three digits of 7803
Equivalent to work mod 1000 (why?).
Since (1000)=1000(1-1/2)(1-1/5)=400, we have
7803 = (7400)273=(1) 273=73=343 mod 1000. (why?)
2. Compute 23456 mod 5. From Fermat’s petit theorem we
know that 24=1 mod 5. Therefore,
23456 = (24)864 = (1) 864 = 1 mod 5
Códigos y Criptografía
Francisco Rodríguez Henríquez
The order of an element in the field Fp
The order of an element  in F, is defined as the smallest positive integer k
such that k=1 mod p. Any finite field always contains at least one element,
called a primitive element, which has order p-1. From Euler’s theorem we
know that for any element  in F,
  p   
p 1
 1mod p,
Using the above result, one can easily prove that the order of any element  in
F must divide (p)=p-1, i.e., ord ( )| (p)= ord ( )| p-1.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Primitive Elements: how many?
Fact: Suppose that  is a primitive element in F.
Then b = i mod n is also a primitive element
in F iff gcd(i, (n))=1. It follows that the
number of primitive elements in F is
¿Cuál es el otro?
((n)).
Example: Consider the powers of 3 mod 7:
31=3;32=2; 33=6;34=4;35=5;36=1.
There are ((7)) = 2 primitive elements in F7
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
Fairy Tale: Chinese Emperor used to count his army
by giving a series of tasks.
1. All troops should form groups of 3. Report back
the number of soldiers that were not able to do
this.
2. Now form groups of 5. Report back.
3. Now form groups of 7. Report back.
4. Etc.
At the end, if product of all group numbers is
sufficiently large, can ingeniously figure out
how many troops.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
mod 3:
N mod 3 = 1
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
mod 5:
N mod 5 = 2
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
mod 7:
N mod 7 = 2
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
Secret inversion formula (for N < 105 = 3·5·7):
N  a (mod 3)
N  b (mod 5)
N  c (mod 7)
Implies that N = (-35a + 21b + 15c) mod 105.
So in our case a = 1, b = 2, c = 2 gives:
N = (-35·1 + 21·2 + 15·2) mod 105
= (-35 + 42 + 30) mod 105
= 37 mod 105
= 37
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
How can we find the secret formula?
For any x, a, b, and c satisfying
x  a (mod 3)
x  b (mod 5)
x  c (mod 7)
Chinese Remainder Theorem says that this is
enough information to uniquely determine x
modulo 3·5·7. Proof, gives an algorithm for
finding x –i.e. the secret formula.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
Theorem: Suppose that gcd(m, n) = 1. Given a and b, there exists
exactly one solution x (mod mn) to the simultaneous
congruences
x  a mod m, x  b mod n.
Proof [sketch]: There exist integers s, t such that ms+nt=1 (why?).
Then ms=1 mod n and nt =1 mod m (why?). Let x = bms +ant.
Then,
x  ant  a mod m, x  bms  b mod n
Suppose x1 is another solution, then c = (x-x1) is a multiple of both,
m and n (why?). But then provided that m and n are relatively
primes then c is also a multiple of mn. Hence, any two solutions
x to the system of congruences are congruent mon mn as
claimed.
Códigos y Criptografía
Francisco Rodríguez Henríquez
Chinese Remainder Theorem
THM (CRT): Let m1, m2, … , mn be pairwise relatively
prime positive integers. Then there is a unique
solution x in [0,m1·m2···mn-1] to the system of
congruences:
x  a1 (mod m1 )
x  a2 (mod m2 )
x  an (mod mn )
Códigos y Criptografía
Francisco Rodríguez Henríquez