Transcript ppt

Primality Testing
Is a given odd integer prime or composite ?
No known algorithm can solve this problem
with certainty in a reasonable time when the
number has more than a few hundred decimal
digits.
Prabhas Chongstitvatana
1
1640 Fermat’s Little theorem
Let n be prime then a n-1 mod n = 1; 1  a  n 1
Is n prime?
Contrapositive : if n and a are integers
if an-1 mod n != 1 then n is NOT prime.
Fermat hypothesises that Fn  2  1
2n
is prime for all n. F0=3, F1=5, F2=17, . . .
F4=65537, F5=4,294,967,297
Prabhas Chongstitvatana
2
About one century later Euler factored
F5= 641 x 6,700,417
can be proof easily by
3F5 1 mod ...F5  3,029,026,160  1
By expo squaring 32 times F5-1 = 232
Prabhas Chongstitvatana
3
Fermat(n)
a = uniform(1..n-1)
if expomod(a, n-1, n) = 1 then return true
else return false
If FALSE n is definitely composite but no clue
to how to factor it.
Factorization is much harder than primality
testing.
Prabhas Chongstitvatana
4
P-correct
The algorithm return a correct answer with
probability at least p on every instance.
Error probability
when k successive calls each return the
wrong answer is at most (1- p)k
Prabhas Chongstitvatana
5
What if Fermat() return TRUE ?
Need the converse of Fermat theorem
an-1 mod n != 1 when n is composite a: 1.. n-1
This is not the case
1n-1 mod n = 1 for all n >= 2 and
(n-1)n-1 mod n = 1 for all odd n >= 3
Prabhas Chongstitvatana
6
False witness
414 mod 15 = 1 ; 15 is composite
This is called “false witness”.
Fermat() a:2..n-2, fails on false witness
False witness is few.
Fermat test on odd composite number
smaller than 1000 is less than 3.3%
(even smaller for larger number)
Prabhas Chongstitvatana
7
BUT There are composite numbers that
admit a significant proportion of false
witness. 561 admits 318 false witness!
For any del > 0 there are infinitely many
composites for which Fermat test discovers
with probability less than del.
In other words, Fermat test is not p-correct
for any p > 0.
Cannot reduce error probability by
repeating call to Fermat().
Prabhas Chongstitvatana
8
Modified Fermat test
n is odd integer > 4
s, t integer which n-1 = 2s t t is odd
note : s > 0 since n-1 is even.
Let B(n) a set of integers define by
iff a: 2.. n-2
a  B (n)
at mod n = 1 or
i:0..s such that a
2i t
mod n = n-1
Prabhas Chongstitvatana
9
Given n is odd a:2..n-2 call on Btest(a,n)
return TRUE for a in B(n).
Prabhas Chongstitvatana
10
Btest(a,n)
s = 0; t = n-1
repeat s = s+1; t = t div 2
until t mod 2 = 1
x = expomod(a, t, n)
if x =1 or x = n-1 then return TRUE
for i = 1 to s-1 do
x = x2 mod n
if x = n-1 then return TRUE
return FALSE
Prabhas Chongstitvatana
11
Example 158 in B(289)
set s = 5, t = 9, n-1 = 288 = 25 x 9
at mod n = 1589 mod 289 = 131
successive square x mod n up to s-1 times
a2t mod n = 1312 mod 289 = 110
a4t mod n = 1102 mod 289 = 251
a8t mod n = 2512 mod 289 = 288
Prabhas Chongstitvatana
12
Extension to Fermat test :
a in B(n) a: 2.. n-2 when n is prime
Strong false witness :
n is a strong pseudo prime to the base a.
a is strong false witness of primality test for n ,
n > 4, when n is odd composite and a in B(n)
158 is a strong false witness of 289. 289=172
Strong false witness is much rarer than false
witness.
Prabhas Chongstitvatana
13
Every odd composite integer 5 .. 1013 fails to be
a strong pseudo prime to at least on of the bases
2, 3, 5, 7, 61.
Five calls on Btest() are sufficient to decide
deterministically on the primality of any integer
up to 1013
MillerRabin(n) // n > 4 is odd
a = uniform(2.. n-2)
return Btest(a,n)
Prabhas Chongstitvatana
14
Btest() always return true when n is prime, n >
4 , a: 2.. n-2, and return false with prob. > 3/4
when n is a composite odd.
MillerRabin() is Monte Carlo algorithm 3/4correct for primality testing.
MillerRabin() has at most prob 1/4 of hitting a
strong false witness. Call k times the prob of
hitting strong false witness consecutively for k
times is 4-k . k = 10, the error will be less than
one in a million.
Prabhas Chongstitvatana
15
Analysis of running time of MillerRabin()
Btest(a,n)
4-k < e
s = 0; t = n-1
22k >= 1/e
repeat s = s+1; t = t div 2
k = ceil(1/2 lg 1/e)
until t mod 2 = 1
O(log t)
x = expomod(a, t, n)
if x =1 or x = n-1 then return
TRUE
Squaring O(log n) times
for i = 1 to s-1 do
x = x2 mod n
each takes O(log3 n )
if x = n-1 then return TRUE
Tn in O(log3 n lg 1/e)
return FALSE
Prabhas Chongstitvatana
16