Transcript PowerPoint 簡報 - National Chiao Tung University

6.3 Primality Testing
(1) Prime numbers

1. How to generate large prime numbers?
(1) Generate as candidate a random odd number n of
appropriate size.
(2) Test n for primality.
(3) If n is composite, return to the first step.
p2.

2. Distribution of prime numbers
(1) prime number theorem
Let Π(x) denote the number of prime
numbers ≦x.
Π(x) ~ x/ln(x) when n∞.
(2)Dirichlet theorem
If gcd(a, n)=1, then there are infinitely many
primes congruent to a mod n.
p3.
(3) Let Π(x, n, a) denote the number of primes in the
interval [2, x] which are congruent to a modulo n,
where gcd(a, n)=1 . Then
Π(x, n, a) ~
x
 ( n ) ln x
The prime numbers are roughly uniformly distributed
among the φ(n) congruence classes in Zn*
(4) Approximation for the nth prime number pn
n ln n  pn  n( ln n  ln ln n) for n  6
p4.
(2) Solovay-Strassen primality test

1. Trial method for testing n is prime or composite
 a [2, n ], if a does not divide n  n is prime

2. Definition ：Euler witness
Let n be an odd composite integer and
(1) If
gcd( a, n)  1 or a
( n 1) / 2
1  a . n
a
   (modn)
n
then a is an Euler witness (to compositeness) for n.
p5.
(2) Otherwise, if
gcd( a, n)  1 and a
( n 1) / 2
a
   (modn)
n
then n is said to be an Euler pseudoprime to
the base a. The integer a is called an Euler liar
(to primality) for n.
p6.

3. Example (Euler pseudoprime)
 Consider n = 91 (= 7x13)
9
Since 945 =1 mod 91, and    1
 91
so 91 is an Euler pseudoprime to the base 9.

4. Fact
At most Φ(n)/2 of all the numbers a, are Euler liars
for n.
p7.

5. Algorithm ：Solovay-Strassen(n, t)

INPUT: n is odd, n ≧3, t ≧1

OUTPUT: “prime” or “composite”

1. for i = 1 to t do :
1.1 choose a random integer a, 2 ≦ a≦n-2
if gcd(a,n) ≠1 then return ( “composite” )
1.2 compute r=a(n-1)/2 mod n (use square-andmultiply)
if r ≠ 1 and r ≠ n-1 then return ( “composite” )
a
 
n
1.3 compute Jacobi symbol s=
if r ≠ s then return ( “composite” )

2. return ( “prime” )
p8.

6. Solovay-Strassen error-probability bound

For any odd composite integer n, the
probability that Solovay-Strassen (n, t)
declares n to be “prime” is less than (1/2)t
p9.
 (3) Miller-Rabin primality test

1. Fact
 p : odd prime
p-1 = 2sr, where r is odd
 For a in Zp*
then ar = 1 (mod p)
j
or a2 r = -1 (mod p) for some j, 0≦ j≦s-1

Why ?
(1) Fermat’s little theorem, ap-1 = 1 mod p
(2) 1, -1 are the only two square roots of 1 in Zp*
p10.

2. Definition
 n : odd composite integer
n-1 = 2sr, where r is odd
1≦a ≦n-1
 a is a strong witness to compositeness for n
if ar ≠ 1 (mod n), and
j
a2 r ≠ -1 (mod n) for all j, 0≦ j≦s-1

n is a strong pseudoprime to the base a
if ar =
1 (mod n)
j
or a2 r = -1 (mod n) for some j, 0≦ j≦s-1
(a is called a strong liar to primality for n)
p11.

3. Algorithm: Miller-Rabin (n, t)
 INPUT: n is odd, n ≧3, t ≧1
 OUTPUT: “prime” or “composite”



1. write n-1 = 2sr such that r is odd.
2. for i = 1 to t do :
2.1 choose a random integer a, 2 ≦ a≦n-2
2.2 compute y=ar mod n (use square-and-multiply)
2.3 if y ≠ 1 and y ≠ n-1 do :
j1
while j ≦ s-1 and y ≠n-1 do :
y  y2 mod n
if y = 1 then return ( “composite” )
j  j+1
if y ≠ n-1 then return ( “composite” )
3. return ( “prime” )
p12.

4. Example (strong pseudoprime)
 Consider n = 91 (= 7x13)
 91-1 = 2*45, s=1, r=45
r
45 =1 mod 91, 91 is a strong
 Since 9 = 9
pseudoprime to the base 9.
 The set of all strong liars for 91 is {1, 9, 10,
12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79,
81, 82, 90}
 The number of strong liars of for 91 is
18 = Φ(91)/4
p13.

5. Fact
 If n is an odd composite integer, then at
most ¼ of all the numbers a, 1 ≦a ≦n-1 are
strong liars for n. In fact if n=!9, then
number of strong liars for n is at most
Φ(n)/4.
p14.

6. Miller-Rabin error-probability bound

For any odd composite integer n, the
probability that Miller-Rabin (n, t) declares
n to be “prime” is less than (1/4)t

7. Remark

For most composite integers n, the number
of strong liars for n is actually much smaller
than the upper bound of Φ(n)/4.

Miller-Rabin error-probability bound is much
smaller than (1/4)t .
p15.