Transcript number_theory

Cryptography
CS 555
Topic 6: Number Theory Basics
CS555
Spring 2012/Topic 6
1
Outline and Readings
• Outline
– Divisibility, Prime and composite
numbers, The Fundamental
theorem of arithmetic, Greatest
Common Divisor, Modular
operation, Congruence relation
– The Extended Euclidian
Algorithm
– Solving Linear Congruence
• Readings:
• Katz and Lindell: 7.1.1, 7.1.2
CS555
Spring 2012/Topic 6
2
Divisibility
Definition
Given integers a and b, with a  0, a divides b
(denoted a|b) if  integer k, s.t. b = ak.
a is called a divisor of b, and b a multiple of a.
Proposition:
(1) If a  0, then a|0 and a|a. Also, 1|b for
every b
(2) If a|b and b|c, then a | c.
(3) If a|b and a|c, then a | (sb + tc) for all integers
s and t.
CS555
Spring 2012/Topic 6
3
Divisibility (cont.)
Theorem (Division algorithm)
Given integers a, b such that a>0, a<b then there exist
two unique integers q and r, 0  r < a s.t. b = aq + r.
Proof:
Uniqueness of q and r:
assume  q’ and r’ s.t b = aq’ + r’, 0  r’< a, q’ integer
then aq + r=aq’ + r’  a(q-q’)=r’-r  q-q’ = (r’-r)/a
as 0  r,r’ <a  -a < (r’-r) < a  -1 < (r’-r)/a < 1
So -1 < q-q’ < 1, but q-q’ is integer, therefore
q = q’ and r = r’
CS555
Spring 2012/Topic 6
4
Prime and Composite Numbers
Definition
An integer n > 1 is called a prime number if its
positive divisors are 1 and n.
Definition
Any integer number n > 1 that is not prime, is called
a composite number.
Example
Prime numbers: 2, 3, 5, 7, 11, 13, 17 …
Composite numbers: 4, 6, 25, 900, 17778, …
CS555
Spring 2012/Topic 6
5
Decomposition in Product of
Primes
Theorem (Fundamental Theorem of Arithmetic)
Any integer number n > 1 can be written as a product
of prime numbers (>1), and the product is unique if
the numbers are written in increasing order.
n  p1 p2 ... pk
e1
e2
ek
Example: 84 = 2237
CS555
Spring 2012/Topic 6
6
Classroom Discussion Question
(Not a Quiz)
• Are the total number of prime numbers finite or
infinite?
CS555
Spring 2012/Topic 6
7
Greatest Common Divisor (GCD)
Definition
Given integers a > 0 and b > 0, we define gcd(a, b) = c,
the greatest common divisor (GCD), as the greatest
number that divides both a and b.
Example
gcd(256, 100)=4
Definition
Two integers a > 0 and b > 0 are relatively prime if
gcd(a, b) = 1.
Example
25 and 128 are relatively prime.
CS555
Spring 2012/Topic 6
8
GCD as a Linear Combination
Theorem
Given integers a, b > 0 and a > b, then d = gcd(a,b) is the
least positive integer that can be represented as ax + by,
x, y integer numbers.
Proof: Let t be the smallest positive integer s.t. t = ax + by.
We have d | a and d | b  d | ax + by, so d | t, so d  t.
We now show t ≤ d.
First t | a; otherwise, a = tu + r, 0 < r < t;
r = a - ut = a - u(ax+by) = a(1-ux) + b(-uy), so we found
another linear combination and r < t. Contradiction.
Similarly t | b, so t is a common divisor of a and b, thus
t ≤ gcd (a, b) = d. So t = d.
Example
gcd(100, 36) = 4 = 4  100 – 11  36 = 400 - 396
CS555
Spring 2012/Topic 6
9
GCD and Multiplication
Theorem
Given integers a, b, m >1. If
gcd(a, m) = gcd(b, m) = 1, then gcd(ab, m) = 1
Proof idea:
ax + ym = 1 = bz + tm
Find u and v such that (ab)u + mv = 1
CS555
Spring 2012/Topic 6
10
GCD and Division
Theorem
Given integers a>0, b, q, r, such that b = aq + r,
then gcd(b, a) = gcd(a, r).
Proof:
Let gcd(b, a) = d and gcd(a, r) = e, this means
d | b and d | a, so d | b - aq , so d | r
Since gcd(a, r) = e, we obtain d ≤ e.
e | a and e | r, so e | aq + r , so e | b,
Since gcd(b, a) = d, we obtain e ≤ d.
Therefore d = e
CS555
Spring 2012/Topic 6
11
Finding GCD
Using the Theorem: Given integers a>0, b, q, r,
such that b = aq + r, then gcd(b, a) = gcd(a, r).
Euclidian Algorithm
Find gcd (b, a)
while a 0 do
r  b mod a
ba
ar
return b
Q ui ck Ti m e ™ an d a T I FF ( U nc om p r es se d) de co m pr e ss or ar e n ee de d t o se e t hi s p i ct ur e .
CS555
Spring 2012/Topic 6
12
Euclidian Algorithm Example
Find gcd(143, 110)
143 = 1  110 + 33
110 = 3  33 + 11
33 = 3  11 + 0
gcd (143, 110) = 11
CS555
Spring 2012/Topic 6
13
Modulo Operation
Definition:
a mod n  r   q, s.t. a  q  n  r
where 0  r  n 1
Example:
7 mod 3 = 1
-7 mod 3 = 2
CS555

Spring 2012/Topic 6
14
Congruence Relation
Definition: Let a, b, n be integers with n>0, we say
that a  b (mod n),
if a – b is a multiple of n.
Properties: a  b (mod n)
if and only if n | (a – b)
if and only if n | (b – a)
if and only if a = b+k·n for some integer k
if and only if b = a+k·n for some integer k
E.g., 327 (mod 5), -1237 (mod 7),
1717 (mod 13)
CS555
Spring 2012/Topic 6
15
Properties of the Congruence Relation
Proposition: Let a, b, c, n be integers with n>0
1. a  0 (mod n) if and only if n | a
2. a  a (mod n)
3. a  b (mod n) if and only if b  a (mod n)
4. if a  b and b  c (mod n), then a  c (mod n)
Corollary: Congruence modulo n is an equivalence
relation.
Every integer is congruent to exactly one number in
{0, 1, 2, …, n–1} modulo n
CS555
Spring 2012/Topic 6
16
Equivalence Relation
Definition
A binary relation R over a set Y is a subset of Y  Y.
We denote a relation (a,b)  R as aRb.
•example of relations over integers?
Definition
A relation is an equivalence relation on a set Y, if R is
Reflexive: aRa for all a  R
Symmetric: for all a, b  R, aRb  bRa .
Transitive: for all a,b,c  R, aRb and bRc  aRc
Example
“=“ is an equivalence relation on the set of integers
CS555
Spring 2012/Topic 6
17
More Properties of the Congruence
Relation
Proposition: Let a, b, c, n be integers with n>0
If a  b (mod n) and c  d (mod n), then:
a + c  b + d (mod n),
a – c  b – d (mod n),
a·c  b·d (mod n)
E.g., 5  12 (mod 7) and 3  -4 (mod 7), then, …
CS555
Spring 2012/Topic 6
18
Multiplicative Inverse
Definition: Given integers n>0, a, b, we say that b
is a multiplicative inverse of a modulo n if
ab  1 (mod n).
Proposition: Given integers n>0 and a, then a has
a multiplicative inverse modulo n if and if only if
a and n are relatively prime.
CS555
Spring 2012/Topic 6
19
Towards Extended Euclidian
Algorithm
• Theorem: Given integers a, b > 0, then d =
gcd(a,b) is the least positive integer that can be
represented as ax + by, x, y integer numbers.
• How to find such x and y?
CS555
Spring 2012/Topic 6
20
The Extended Euclidian Algorithm
First computes
b = q 1a + r1
a = q 2r 1 + r 2
r 1 = q 3r 2 + r 3

rk-3 =qk-1rk-2+rk-1
rk-2 = qkrk-1
Then computes
x0 = 0
x1 = 1
x2 = -q1x1+x0

xk = -qk-1xk-1+xk-2
And
y0 = 1
y1 = 0
y2 = -q1y1+y0

yk = -qk-1yk-1+yk-2
We have axk + byk = rk-1 = gcd(a,b)
CS555
Spring 2012/Topic 6
21
Extended Euclidian Algorithm
Extended_Euclidian (a,b)
x=1; y=0; d=a; r=0; s=1; t=b;
while (t>0) {
q = d/t;
u=x-qr; v=y-qs; w=d-qt;
x=r;
y=s;
d=t;
r=u;
s=v;
t=w;
}
return (d, x, y)
end
CS555
Spring 2012/Topic 6
Invariants:
ax + by = d
ar + bs = t
22
Another Way
Find gcd(143, 111)
143 = 1  111 + 32
111 = 3  32 + 15
32 = 2  15 + 2
15 = 7  2 + 1
gcd (143, 111) = 1
CS555
32 = 143  1  111
15 = 111  3  32
= 4111  3 143
2 = 32  2  15
= 7 143  9  111
1 = 15 - 7  2
= 67  111 – 52  143
Spring 2012/Topic 6
23
Linear Equation Modulo n
If gcd(a, n) = 1, the equation
ax 1 mod n
has a unique solution, 0< x < n. This solution
is often represented as a-1 mod n
Proof: if ax1  1 (mod n) and ax2  1 (mod n),
 a(x -x )  0 (mod n), then n | a(x -x ),
then
1 2
1 2
then n | (x1-x2), then x1-x2=0
How to compute a-1 mod n?
CS555
Spring 2012/Topic 6
24
Examples
Example 1:
• Observe that
3·5  1 (mod 7).
• Let us try to solve
3·x+4  3 (mod 7).
• Subtracts 4 from both side,
3·x  -1 (mod 7).
• We know that
-1  6 (mod 7).
• Thus
3·x  6 (mod 7).
• Multiply both side by 5,
3·5·x  5·6 (mod 7).
• Thus, x  1·x  3·5·x  5·6  30  2 (mod 7).
• Thus, any x that satisfies 3·x+4  3 (mod 7) must satisfy x
 2 (mod 7) and vice versa.
Question: To solve that 2x  2 (mod 4).
Is the solution x1 (mod 4)?
CS555
Spring 2012/Topic 6
25
Linear Equation Modulo (cont.)
To solve the equation
ax  b mod n
When gcd(a,n)=1, compute x = a-1 b mod n.
When gcd(a,n) = d >1, do the following
•
•
If d does not divide b, there is no solution.
Assume d|b. Solve the new congruence, get x0
(a / d ) x  b / d (mod n d )
•
CS555
The solutions of the original congruence are
x0, x0+(n/d), x0+2(n/d), …, x0+(d-1)(n/d)
(mod n).
Spring 2012/Topic 6
26
Solving Linear Congruences
Theorem:
• Let a, n, z, z’ be integers with n>0. If gcd(a,n)=1,
then azaz’ (mod n) if and only if zz’ (mod n).
• More generally, if d:=gcd(a,n), then azaz’ (mod
n) if and only if zz’ (mod n/d).
Example:
• 5·2  5·-4 (mod 6)
• 3·5  3·3 (mod 6)
CS555
Spring 2012/Topic 6
27
Basic Number Theory
• Divisibility
Let a,b be integers with a≠0. if there exists an
integer k such that b=ka, we say a divides b
which is denoted by a|b
11|143, 1993|3980021
◇ if a≠0, then a|0 and a|a; 1|b for each b
a|b and b|c → a|c
a|b and a|c → a|sb+tc for all s, t
Prime Numbers
• An integer p>1 that is divisible only by 1 and
itself is called a prime number, otherwise it is
called composite (P.64)
• primegen.c generates prime numbers
• Let π(x) be the number of primes less than x,
then π(x) ≈x/ln(x) as x→∞
• Exercise Plot π(x) vs. x for x=216 to 232
A Plot of π(x)≈x/ln(x) vs. x
Prime Factorization Theorem
• Every positive integer is a product of primes. This
factorization into primes is unique, up to
reordering the factors
• 49500=22 32 5311
• If a prime p|ab, then either p|a or p|b Moreover,
p|x1 x2 … xn →p|xj for some j
• 7|14•30,
Greatest Common Divisor gcd
• gcd(343, 63)=7, gcd(12345,11111)=1
gcd(1993,3980021)=1993
• Euclidean Algorithm to compute gcd(a,b) does
not require the factorization of the numbers and
is fast.
• gcd(482,1180)=2
Solving ax+by=1 when gcd(a,b)=1
• Let a,b be integers with a2 +b2 ≠0, and
gcd(a,b)=1, then ax+by=1 has an integer solution
(x,y) ♪ Euclidean Algorithm
• Example 7(-2) + 5(3) =1
• Solving ax+by=d with gcd(a,b)=d can be reduced
as solving
• a0x + b0y = 1 where a=a0d, b=b0d
Congruences
• Let a,b,n be integers with n≠0. We say that a≡b
(mod n)
{read as a is
congruent to b mod n}
if n|(a-b) a=b+nk
for an integer k is
another description
• Example 32≡7 (mod 5)
Simple Properties
• Let a,b,c,n be integers with n≠0
(1) a≡0 (mod n) iff n|a
(2) a≡a (mod n)
(3) a≡b (mod n) iff b≡a (mod n)
(4) a≡b and b≡c (mod n) → a≡c (mod n)
(5) a≡b and c≡d (mod n) → a+c≡b+d,
a−c≡b−d, ac≡bd (mod n)
(6) ab≡ac (mod n) with n≠0, and gcd(a,n)=1,
(mod n)
then b≡c
Computational Properties
• Finding a-1 (mod n)
• Solving ax≡c (mod n) when gcd(a,n)=1
• What if gcd(a,n)>1
☺Solve 11111x≡4 (mod 12345)
☻Solve 12x≡21 (mod 39)
♫ How to solve x2 ≡a (mod n)?
□ Working with fractions (inverse ?)
The Chinese Remainder Theorem
• Let m1, m2, …, mk be integers with gcd(mi, mj)
= 1, there exists only one solution x (mod m1
m2…mk) to the simultaneous congruences [P.7678]
x≡a1 (mod m1)
x≡a2 (mod m2)
: :
x≡ak (mod mk)
Fermat's Little Theorem
• How to fast evaluate 21234 (mod 789)?
• How to fast evaluate Xa (mod n)?
• If p is a prime and gcd(p,a)=1, then
ap-1 ≡ 1 (mod p)
Euler’s φ-Function and Theorem
• φ(n)= #{a | 1 ≤ a ≤ n, gcd(a,n)=1}, that is,
the number of positive integers which are
relatively prime to n
Examples: φ(15)=8, φ(16)=8, φ(17)=16
φ(pq)=(p-1)(q-1) if p and q are primes
φ(p)=p-1 if p is a prime number
φ(pr)=pr-pr-1=pr(1- 1/p)
• If gcd(a,n)=1, then aφ(n) ≡ 1 (mod n)
Examples and Basic Principle
•
•
•
•
[Page 82]
What are the last three digits 7803 ?
Compute 243210 (mod 101)
Let a,n,x,y be integers with n≥1 and gcd(a,n)=1.
If x≡y (mod φ(n)), then
ax ≡ ay (mod n)
(Hint) x=y+kφ(n); by Euclidean Theorem
Primitive Roots
If p is a prime, a primitive root mod p is a number g
whose power yield every nonzero class mod p.
{gk|0<k<p}={1,2,…,p-1}
Proposition: Let g be a primitive root mod p
(1) gn≡1 (mod p) iff (p-1)|n or n≡0 (mod p-1)
(2) gj≡gk (mod p) iff j≡k (mod p-1)
♪ 3 is a primitive root mod 7 but not for mod 13
Inverting Matrices (mod n)
• A matrix M is invertible under (mod n) if
gcd(det(M), n)=1
• The inverse of A=[1 2;3 4] (mod 11) is
A-1
=[9 1 ; 7 5] and det(A)= -2≡9 (mod 11)
• The inverse of M=[1 1 1; 1 2 3; 1 4 9] under
(mod 11) is [3 3 6; 8 4 10; 1 4 6], where det(M)=
½ ≡ 6 (mod 11)
Square Roots mod n (1/9)
• X2 ≡71 (mod 77) has solutions ±15, ±29
• How to (efficiently) solve X2 ≡b (mod pq), where
p,q are (very close) primes?
• Every prime p (except 2) must satisfy
(mod 4) or p≡3 (mod 4)
• The square roots of 5 mod 11 are ±4
p≡1
Square Roots mod n (2/9)
• Let p≡3 (mod 4) be prime and y is an integer
such that x≡y(p+1)/4 (mod p).
♪ If y has a square root mod p, then the square
roots of y mod p are x and –x
♪ If y has no square roots mod p, then –y has a
square root mod p, and the square roots of –y
are x and –x.
Square Roots mod n (3/9)
Proof:
x4 ≡ yp+1≡ y2 . yp-1 ≡ y2 (mod p) →
(x2 + y ) (x2 - y ) ≡ 0 (mod p)
Suppose both y and –y are squares mod p
This is impossible.
Square Roots mod n (4/9)
• Lemma:
Let p ≡ 3 (mod 4) be prime, then
X2 ≡ -1 (mod p) has no solutions.
Proof:
Let p = 4q+3
X2 ≡ -1→ Xp-1 ≡ -1(p-1)/2≡ -12q+1 ≡-1
But Xp-1 ≡ 1 (Fermat’s theorem)
Square Roots mod n (5/9)
• Suppose both y and –y are squares mod p, say y
≡ a2 and -y ≡ b2. Then (a/b)2 ≡ -1 (mod p)
But according to the previous lemma, (a/b)2 ≡ -1
(mod p) is impossible
Square Roots mod n (6/9)
2. y ≡ x2 (mod p), the square roots of y are ± x.
3. -y ≡ x2 (mod p), the square roots of -y are ± x.
Examples for Square Roots (7/9)
•
•
•
•
x2 ≡ 5 (mod 11)
(p+1)/4 = 3
x ≡ 53 ≡ 4(mod 11)
Since 43 ≡ 5 (mod 11), the square root of 5 mod
11 are ±4
Examples for Square Roots (8/9)
◎ To solve x2≡ 71 (mod 77)
(1) x2≡ 1 (mod 7) → x ≡±1 (mod 7)
(2) x2≡ 5 (mod 11) → x ≡±4 (mod 11)
By Chinese remainder theorem
x ≡±15 , x ≡±29 (mod 77)
Square Roots mod n (9/9)
• Suppose n=pq is the product of two primes
congruent to 3 mod 4 (type 4k+3), and let y with
gcd(y,n)=1 has a square root mod n. Then
finding the four solutions x=±a, ±b to x2 ≡ y (mod
n) is computationally equivalent to factoring n
which is regarded as extremely difficult when n is
large, say n has a length of 256 bits or higher
Group Theory
•
(1)
(2)
(3)
(4)
Let G be a nonempty set and let ⊕ be a binary
operation defined on GxG. G is said to be a
group if
For any elements a,b in G, a⊕b is in G
(a⊕b)⊕c=a⊕(b⊕c) for any a,b,c in G
There exists a unit element e such that
e⊕a=a⊕e for any a in G
For each a in G, there exists an inverse a-1
such that a-1⊕a=a⊕a-1 = e
Field (Informal Definition)
• (F, +,‧) is a nonempty set F with two binary
operations +, ‧such that
(1) (F,+) is a commutative group with unit element
0
(2) (F’, ‧) is a commutative group with unit element
1, where F’=F\{0}
(3) a‧(b+c)=(a‧b) + (a‧c) for any a,b,c
Examples
Groups
• (Z,+) is a group, Z is the set of all integers
• Zp ={0, 1, 2, …, p-1} with + under (mod p)
• Zp-1={1,2,…,p-1} with x under (mod p)
Fields
• (R,+,*)
• (Zp,+,x) under (mod p)
Finite Fields with Applications
• A field with finite elements
• Suppose we need to work in a field whose range
is 0 to 28-1
• Z256={0,1, ‥‥, 255} is not a field
since 256 is not a prime
GF(4)={0,1, ω, ω2}
• Zp (p is prime)
• GF(pn) (p is prime)
Galois Field
n
GF(p )
• Z2[X] be the set of polynomials whose
coefficients are integers mod 2. e.g., X+1,
X6+X3+1 are in this set
• GF(pn) has pn elements, where p is prime
• Zp[X] mod an irreducible polynomial whose
degree is pn.
• GF (28) = Z2[X] (mod X8+X4+X3+X+1)
Galois Field
• For every power pn of a prime p, there is exactly
one finite field with pn elements
• It can be proved that two fields with pn elements
constructed by two different polynomials of
degree n are isomorphic
Multiplication of
n
GF(2 )
• (X7+ X6 + X3 + X + 1) (X)=? (mod X8+ X4 + X3 + X
+ 1)
• 11001011 b7=1
• Left shift one bit, we have
b6 b5 b4 b3b2 b1 b00 = 10010110
• ?=110010110 + 100011011 = 10001101
=X7+X3+X2+1
Linear Feedback Shift Register
•
•
•
•
•
•
•
Xn+4 ≡ Xn + Xn+1 (mod 2) A recurrence Eq.
If the initial values are X0 X1 X2 X3 = 1101,
The sequence is 1101011110001001101...
Associated with the recurrence Eq. is
X4 +X+1 which is irreducible (mod 2)
The k-th bit can be obtained by
Xk(1+X+X3) (mod X4 +X+1) for k≧4