Index of /6.857/OldStuff/Fall01/handouts/H11

 Name                    Last modified       Size  Description

 Parent Directory        07-Jun-2002 17:45      -  
 FindPrime.java          03-Oct-2001 01:14     6k  

 Written by

  Yip,Alexander S : yipal@MIT.EDU
  Yuditskaya,Sophia C : scyudits@MIT.EDU
  Hydari,Muhammad Z. : hydari@MIT.EDU
 
 October 2, 2001

May be freely reproduced for educational or personal use

We used Miller-Rabin randomized primality testing algorithm for our
program.  Some precomputation was done to avoid unnecessary checking.
We made sure that the number was odd by checking the last appended
byte.  Moreover, we tested our candidate number to make sure it was
not divisible by 3, 5 or 7.  According to Bruce Scheier, ({\em Applied
Crytography}) this eliminates 54 percent of the odd numbers.

We also tested {\texttt isPrime()} with 23 Carmichael numbers obtained
from ftp.dpmms.cam.ac.uk/pub/Carmichael/carmichael-14.gz.  All of
these numbers were rejected in just one call to {\texttt isPrime()}
(the base used was 7).  The Carmichael numbers we used were: 561,
1105, 1729, 2465, 2821, 6601, 8911, 10585 , 15841, 29341, 41041,
46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217,
 162401,146843929, 161242705, 2023528501.    

The number of times that {\texttt isPrime()} is called with a random
base each time can be set based on the level of confidence that the
user desires.  The algorithm is false-biased Monte Carlo so it is
alway right when it declares that a number is not prime.  However,
when the algorithm declares the number as prime, the probability of it
being wrong is atmost $(1/4)^{n}$ where ``n'' is th e number of times
the {\texttt isPrime()} is run.  Knuth proves in the solution to
Exercise 22 of section 4.5.4 ({\em Volume 2: Seminumerical
Algorithms}) that the probability of failure of {\texttt isPrime()} is
atmost $1/4$.  This upper bound is true regardless of the value of the
number being tested.  In practise however, the algorithm rarely fails.
So if we repeat the test a number of times with a random base the
upper bound on the probability of failure becomes negligible.
(e.g. it would be less than $(1/4)^{23}$ if we run {\texttt isPrime()}
23 times)

If we express our candidate prime as $p = 1 + 2^{t}*u$ and if the
random chosen base is ``a'', we know that $a^{u} (mod p)$ can be
calculated in $O(log u)$ multiplication operations.  Then a further
``t'' multiplications will generate $a^{p-1}$.  We did not brute-force
the last two bytes - multiples of 2, 3, , 5, 7 were sifted and not fed
into Miller-Rabin testing.