----- Original Message ----- From: "Nicolas Rachinsky" <[EMAIL PROTECTED]>
Subject: Re: Fermat's primality test vs. Miller-Rabin


* Joseph Ashwood <[EMAIL PROTECTED]> [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 [EMAIL PROTECTED]

Reply via email to