----- 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];
  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.'

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
   curNum = BigInteger.ONE.or(new BigInteger(lenNum, rand));
  while(testOnce(curNum) == false);
  System.out.println("Failed " + failuresBetween+ " times");
  //passed once

  //run 127 more tests
  for(int j = 0; j < 127; j++)
  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]

Reply via email to