Fermat's primality test vs. Miller-Rabin

Joseph Ashwood ashwood at msn.com
Sun Dec 4 18:54:38 EST 2005


----- Original Message ----- 
From: "Sidney Markowitz" <sidney at sidney.com>
Subject: Re: Fermat's primality test vs. Miller-Rabin


> Joseph Ashwood wrote:
>>   byte [] rawBytes = new byte[lenNum/8];
>>   rand.nextBytes(rawBytes);
>>   curNum = new BigInteger(rawBytes);

> curNum = BigInteger.ONE.or(new BigInteger(512, rand));

Ok after making that change, and a few others. Selecting only odd numbers 
(which acts as a small seive) I'm not getting much useful information. It 
appears to be such that at 512 bits if it passes once it passes 128 times, 
and it appears to fail on average about 120-130 times, so the sieve 
amplifies the values more than expected. Granted this is only a test of the 
generation of 128 numbers, but I got 128 primes (based on 128 MR rounds). 
For the sake of full code review and duplication I've appended the entire 64 
lines of code. You'll see I made a few optimizations, and removed writing 
the data to a csv. I developed compiled and ran it only through Eclipse.'
                Joe




import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.IOException;

public class millerMain {
 static int numTests = 128;
 static int lenNum = 512;
 static SecureRandom rand = new SecureRandom();
 static BigInteger two = BigInteger.valueOf(2);


 public static void main(String[] args) throws IOException {
  BigInteger curNum = null;
  int totalPrimes = 0;
  int [] successes = new int[numTests];
  int failuresBetween = 0;
  for(int i = 0; i < numTests; i++)
  {
   failuresBetween = -1;
   //choose starting number
   do
   {
    curNum = BigInteger.ONE.or(new BigInteger(lenNum, rand));
    failuresBetween++;
   }
   while(testOnce(curNum) == false);
   System.out.println("Failed " + failuresBetween+ " times");
   //passed once


   //run 127 more tests
   for(int j = 0; j < 127; j++)
   {
    if(testOnce(curNum))
    {
     successes[i]++;
    }
   }
   if(successes[i] == 127) totalPrimes++;
   System.out.println("Test Number "+i+" successes "+(successes[i]+1)+" 
Total Prime so far "+totalPrimes);

   BigInteger temp = BigInteger.valueOf(successes[i]);
   String num = temp.toString();
  }
 }


 static boolean testOnce(BigInteger N){
  BigInteger A = null;

  // 0 < A < N
  A = new BigInteger(lenNum, rand).mod(N);
  if(A.compareTo(BigInteger.ZERO) == 0) return testOnce(N);

  BigInteger Nminus1 = N.subtract(BigInteger.ONE);

  //shouldBeOne = A^(N-1)     mod N
  BigInteger shouldBeOne = A.modPow(Nminus1, N);
  if(shouldBeOne.compareTo(BigInteger.ONE)!= 0) return false;
  return true;

 }
}



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list