Transcript Chapter 8 Introduction To Number Theory Prime

Chapter 8
Introduction To Number Theory
Prime Numbers
• Prime numbers only have divisors of 1 and
self.
• Prime numbers cannot be written as a
product of other numbers.
• An integer p>1 is a prime number if and only
if its only divisors are ±1 and ±p.
• For example:2,3,5,7,11,13,17,19,23,29,31,37 are some
prime numbers
An Integer Representation
 Any integer a>1 can be represented in prime
factorization as
a=p1a1.p2a2……….pnan
Where p1<p2<……..<pn are prime numbers
and ai (i=1,2,3……n) is a positive integer.
For example:91=7×13
3600=24×32×52
11011=7×112×13
An Integer Representation
General Form:If P is the set of all prime
numbers, then any integer can be uniquely
written in the general form as
a = ∏ pap where each ap≥0
pεP
For example:- 3600=24×32×52
a=3600 , p=2,3,5
a2=4 a3=2 and a5=2
An Integer Representation (cont.)
The integer 12 represented as by {a2=2,a3=1}
The integer 18 represented as by {a2=1,a3=2}
Multiplication:Multiplication of two numbers is
equivalent to adding the corresponding exponents:
12×18=216
Or
a2=2+1=3
a3=1+2=3
23x33=216
Division:Any integer of the form pk can be
divided only by an integer that is of a lesser or
equal power of the same prime number, pj with
j≤k.
a|b
a p ≤ bp
for all p
For Example:a=24 b=72
and 24|72
24=23×3
72=23×32
a2=3=b2
a3=1≤2=b3
Greatest Common Divisor (GCD):300= 2 × 2 × 3 × 5 × 5
300= 22 × 31 × 52
90= 2 × 3 × 3 × 5 OR 90= 21 × 32 × 51
GCD=2 × 3 × 5 = 30
GCD=21 × 31 × 51 = 30
In general
k=gcd(a,b)
kp=min(ap,bp) for all p
Problem:• To find prime factors of a large number is not so
simple.
• Therefore above methods are less applied for large
prime numbers.
Fermat’s Theorem
Also called Fermat’s little theorem.
Statement:If ‘p’ is a prime, and ‘a’ is a
Positive Integer not divisible by p, then
ap-1 ≡ 1 mod p
For Example: a = 7, p = 19
Fermat’s Little Theorem:
719-1 ≡ 1 mod 19
718 ≡ 1 mod 19
Fermat’s Theorem
Show that: 718 ≡ 1 mod 19
As 718 = 72 x 74 x 74 x 78
72 = 49 ≡ 11 mod 19
74 ≡ 121 ≡ 7 mod 19
74 ≡ 121 ≡ 7 mod 19
78 ≡ 49 ≡ 11 mod 19
So: (11 x 7 x 7 x 11) mod 19
= [(77 mod 19) x(77 mod 19)] mod 19
≡ 1 mod 19
Fermat’s Theorem
Alternative form of Fermat’s theorem:If ‘p’ is prime and ‘a’ is any positive
integer not divisible by ‘p’, then
ap ≡a mod p
For Example:1. p = 5, a = 3,
35 = 243 ≡3 mod 5
2. p = 5, a = 10, 105 = 100000 ≡10 mod 5
≡0 mod 5
Euler’s Totient Function ø(n)
• By doing arithmetic modulo with n
• Complete set of residues is: {0,1,2,......n-1}
• Set of residues is those numbers (residues)
which are relatively prime to n.
For Example:n=10
Complete set of residues is {0,1,2,3,4,5,6,7,8,9}
Set of relatively prime is {1,3,7,9}
Therefore ø(n) is the number of positive integers
less than n and relatively prime to n.
Euler’s Totient Function ø(n)
Example:1. ø(37)= ?
2. ø(35)= ?
1. As 37 is prime, therefore all positive integers from
1 to 36 are relatively prime to 37.
ø(37)= 36
It shows that for a prime number ‘n’
ø(n)= n-1
2. As 35 is not prime, therefore list of positive
integers which are relatively prime to 35.
1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,25,26,27
,29,31,32,33,34
Euler’s Totient Function ø(n)
There are 24 numbers in the list, so
ø(35)=24
ø(35) = ø(7 x 5)
= ø(7) x ø(5)
= (7 - 1) x (5 - 1)=6 x 4=24
Therefore if n=pq , where p and q are prime
numbers, with pq. Then
ø(n) = ø(pq) = ø(p) x ø(q)
= (p – 1) x (q – 1 )
Some values of ø(n)
n
1
2
3
4
5
6
7
8
9
10
ø(n)
1
1
2
2
4
2
6
4
6
4
n
11
12
13
14
15
16
17
18
19
20
ø(n)
10
4
12
6
8
8
16
6
18
8
n
21
22
23
24
25
26
27
28
29
30
ø(n)
12
10
22
8
20
12
18
12
28
8
Euler's Theorem
Euler’s theorem states that for every ‘a’ and ‘n’ that
are relatively prime:
aø(n) ≡ 1mod n
Examples:(i).
a=3; n=10;
ø(10)=4
34 = 81 = 1 mod 10
(ii).
a=2; n=11;
ø(11)=10
210 = 1024 = 1 mod 11
Testing For Primality
• In a number of cryptographic algorithms use
very large prime numbers are taken randomly.
• To find out a large prime number is difficult
tasks.
• Divide by all numbers (primes) in turn less
than the square root of the number is only
useful for small numbers.
• For that reason use Miller and Rabin algorithm
to find out a large prime number.
Miller and Rabin Algorithm
•
A test based on Fermat’s Theorem.
TEST (n)
1. Find integers k, q, k > 0, q odd,
so that (n–1)=2kq
2. Select a random integer a, 1<a<n–1
3. if aq mod n = 1 then return (“inconclusive");
4. for j = 0 to k – 1 do
jq
2
5. if a mod n = n-1 then return(" inconclusive ")
6. return ("composite")
Miller and Rabin Algorithm
Example # 1:For prime number n= 29 n – 1=28=22(7)=2kq
Let us try a=5
aq mod n = 1
57 mod 29 = 28 (No result)
jq
2
In next step:a mod n = n-1
07
2
5 mod 29=28 (inconclusive)
If test is perform for all integer ‘a’ from 1 to 28, get
same inconclusive result, which shows that n=29 is
prime number.
Miller and Rabin Algorithm
Example # 2:For composite number n=13 x 7=221
n – 1=220=22(55)=2kq
Let us try a=21
aq mod n = 1
2155 mod 29 = 200(No result)
jq
2
In next step:a mod n = n-1
0
22 55 mod 29=220(inconclusive)
which shows that n=221 is maybe prime number.
In fact ,of the 220 integer from 1 to 220 ,six of integer
return an inconclusive result (1,21,47,174,200,220)
Probabilistic Considerations
• If Miller and Rabin algorithm returns
“composite” the number is definitely not prime.
• Otherwise is a prime
• Fail to detects that ‘n’ is not prime is < ¼
• Hence if repeat test with different random ‘a’
then chance n is prime after t tests is:
• Probability (n prime after t tests) = 1-4-t
• For t=10 this probability is > 0.99999
Prime Distribution
• Prime number theorem states that primes occur
roughly every (ln n) integers.
• Since can immediately ignore evens and
multiples of 5, in practice only need test 0.4 ln(n)
numbers of size n before locate a prime.
• For example ,if a prime on the order of magnitude
of 2200 were sought, then about 0.4ln(2200)=55
trials are need to find a prime.
• This is only the “average” sometimes primes are
close together, at other times are quite far apart.
Chinese Remainder Theorem
• Chinese Remainder Theorem used to speed up
modulo computations
• Working modulo a product of numbers
e.g.
mod M = m1m2……mk
• Chinese Remainder theorem lets us work in
each moduli mi separately.
• since computational cost is proportional to
size, this is faster than working in the full
modulus M.
Chinese Remainder Theorem
A↔(a1,a2,……,ak)
B ↔(b1,b2,……,bk)
then
(A+B) mod M ↔((a1+b1)modm1,…,(ak+bk)modmk)
(A-B) mod M ↔((a1-b1)modm1,…,(ak-bk)modmk)
(A×B) mod M ↔((a1×b1)modm1,…,(ak×bk)modmk)
ci = Mi×(Mi-1 mod mi) for 1≤i ≤k
If
k
A ≡ ( ∑ aici ) mod M
i=1
Chinese Remainder Theorem
Example:- To represent 973 mod 1813 as a pair of
numbers mod 37 and 49 as;
m1=37 ,m2=49
M=1813, A=973
M1=49, M2=37
M1-1=34 mod m1, M2-1=4 mod m2
973 mod 37 = 11
973 mod 49 = 42
973 is represented as (11,42)
Chinese Remainder Theorem
• To add 678 to 973:973 ↔(973 mod 37,973 mod 49)=(11,42)
678 ↔(678 mod 37,678 mod 49)=(12,41)
(11+12) mod 37,(42+41) mod 49=(23,34)
• To Check the result:(23,34)↔(a1M1M1-1+a2M2M2-1) mod M
=[(23)(49)(34)+(34)(37)(4)] mod 1813
=43350 mod 1813
=1651
(973+678) mod 1813=1651
Primitive Roots
• According to Euler’s theorem:aø(n)mod n=1
• Consider ammod n=1 as
GCD(a,n)=1
• must exist for m= ø(n) but may be smaller.
• once powers reach m, cycle will repeat.
• If smallest is m= ø(n) then a is called a primitive root.
• If p is prime, then successive powers of a "generate" the
group mod p, e.g. for prime number 19; its primitive root
are 2,3,10,13,14 and 15.
• These are useful but relatively hard to find.