Transcript Basic Number Theory

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,
then b≡c (mod n)
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.76-78]
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
p≡1 (mod 4) or p≡3 (mod 4)
• The square roots of 5 mod 11 are ±4
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
Let G be a nonempty set and let ⊕ be a
binary operation defined on GxG. G is
said to be a group if
(1) For any elements a,b in G, a⊕b is in G
(2) (a⊕b)⊕c=a⊕(b⊕c) for any a,b,c in G
(3) There exists a unit element e such that
e⊕a=a⊕e for any a in G
(4) 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 GF(pn)
• 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 GF(2n)
• (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
k
3
4
X (1+X+X ) (mod X +X+1) for k≧4