Fermat's primality test vs. Miller-Rabin

[Joseph Ashwood]

----- Original Message ----- 
From: "Nicolas Rachinsky" <crypto-0 at ml.turing-complete.org>
Subject: Re: Fermat's primality test vs. Miller-Rabin


>* Joseph Ashwood <ashwood at msn.com> [2005-11-22 02:50 -0800]:
>> 16384 times
>> ..................

> If I remember the proof of MR correctly it assumes an odd number. Were
> all your questions odd?

The random numbers tested were almost certainly not all odd, no filtering 
was done on random.

> If not, please try again with odd numbers only.

I'm running an abbreviated test right now, and it's looking less impressive, 
I have to assume I'm hitting a bad streak somehow. Real bad, 30 numbers 
tested, no primes at all so far, I see one that has passed 79 tests. I have 
to assume I'm missing something really stupid at this point in my new number 
chooser that I don't have the time to find right now. So I'm asking for 
anyones help in pointing out to me, why after I let it go the full 128 runs 
(that is 128 numbers that passed a single round of MR) I didn't get a single 
number to pass more than 79? Did I just hit a really, really bad streak?

The exact code for the function and the support variables :

 static int lenNum = 512;
 static SecureRandom rand = new SecureRandom();
 static BigInteger two = BigInteger.valueOf(2);

 static BigInteger chooseValue()
 {
  //pick a random integer
  BigInteger curNum = null;
  byte [] rawBytes = new byte[lenNum/8];
  rand.nextBytes(rawBytes);
  curNum = new BigInteger(rawBytes);

  //make sure it's odd
  if(curNum.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0)
  {
   curNum = curNum.add(BigInteger.ONE);
  }

  //it's 0 or negative try again
  if(curNum.compareTo(BigInteger.ZERO)<=0)
  {
   return chooseValue();
  }
  return curNum;

 }

This should choose a 512-bit random odd positive number, unless I'm missing 
something horribly, horribly braindead.

Anyway, back to trying to design a "cool" user interface (anyone who knows 
me knows that the cue to begin laughing, I can't design a UI for sh*t).
                    Joe 



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