COSC3325                               Program-1(B)               Due:  Wed., 3/4/2009   

                                        Prime number testing

 

Background:

1.         Public-key Encryption (such as RSA) needs large prime numbers for the

            public key.

2.         It is believed that there are some 10¹⁵¹   primes 512 bits in length or less.

            For numbers near n, the probability that a random number is prime is small,

            approximately one in ln(n)

3.         Finding a prime number can be done in two ways:

            a. By checking to see if a number under consideration has a factor.

                This is very time-consuming especially when the number is very large as such a

    number can have a very large number of potential factors.

            b. By picking a large random number and repeatedly checking to see if it may not

                be a composite. (probabilistic)

 

Task:

A.        Find all prime numbers smaller than 1000.

B.         Test primality of each of following eight large numbers:

                        9876543210123

                        9876543212345

                        9876543214567

                        9876543216789

                        9876543218901

                        1365347734339

                        2365347734339

                        3365347734339

 

            The testing of each number above should be done in two steps:

B.1       By checking if none of the primes less 1000 actually divides the potential number

            under testing.

B.2       By conducting “Rabin-Miller” testing at least ten times only when the potential

number passes the first test of step (B.1) above.

It is believed that the probability of a composite escaping this test is no higher

than 25%.

 

Output Requirements:

A.        The list of all primes smaller than 1000.

B.         The count of above primes.

C.         For each of above 8 large numbers, an indicator of whether the number is

            definitely NOT a prime or possibly a prime.

            In order for a number to be considered as “Possibly a prime” it must pass both tests

            above.

 

 

Rabin-Miller algorithm:

 

a.         Calculate b where it is the total number of times 2 divides p-1 where p is the

            potential prime number under consideration.

            That is, p = 1 + 2^b  * m   where m is a positive odd integer.

 

            For example, if p is 69, b must be 2, as

            69 = 1 + 2²  * 17

 

b.         Choose a relatively small random integer, a, such that it is less than p.

           

c.         z = a^m   (mod  p)

                        Note that  x (mod p) is the remainder we get by dividing x by p and hence

                        it is between 0 and p-1.

                        200 (mod 9) is 2.

                        In the above case, we say that 2 is the Residue of 200, (modulo 9)

                        200 ⁵  (mod 9)  =  (200 (mod 9)) ⁵    =  2⁵ (mod 9) =  32 mod 9 =  5

                        In the above case, we do not have to calculate 200 ⁵ 

d.         if  (z == 1), then return (“p may be prime”)

/* In this case, p passes the test and we assume that it may be prime.

                            So, in this case, we repeat the entire algorithm for another small random

                            integer, a.

                        */

e.         for j = 0 to b-1

                        if (z == p-1) then return (“p may be prime”)        // p passes the test again here

                        else z =  z²  (mod p)                   

f.          return (“p is definitely composite”)

***********END-OF-RABIN-MILLER*********

 

Notes:

a.         Above algorithm is based upon the following “Fermat’s Little Theorem:”

                If m is a prime and a (an integer) is smaller than m, (or more generally,

                a is any integer, small or large, that p does not divide),  then  a ^m-1    =  1  (mod m).

 

            EX.

 

Suppose that  m=7 (a prime).  Then we have

1 ⁶   =   1 (mod 7) 

2 ⁶   =   1 (mod 7)   as  64 = 7*9 + 1 

3 ⁶   =   1 (mod 7)   as 729 = 7*104 + 1

4 ⁶   =   1 (mod 7)   as 4096 = 7*585 + 1

5 ⁶   =   1 (mod 7)   as 15625 = 7*2232 + 1

6 ⁶   =   1 (mod 7)   as 46656 = 7*6665 + 1

 

b.         To speed up step (d) above:  z = a ^m   (mod  p)

            consider the following equality:

           

                        a ²⁵  (mod p) =              // note  25 = 1 + (2*(2*(2*(2+1))))

                        ((((a² (mod p)*a)²  (mod p)) ²  (mod p))²  *a) (mod p)