----- Original Message -----
From: "Sidney Markowitz" <[EMAIL PROTECTED]>
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 [EMAIL PROTECTED]
