[19061] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Joseph Ashwood)
Fri Dec 2 12:41:01 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Joseph Ashwood" <ashwood@msn.com>
To: "Nicolas Rachinsky" <crypto-0@ml.turing-complete.org>
Cc: <cryptography@metzdowd.com>
Date: Thu, 1 Dec 2005 01:27:57 -0800
----- Original Message -----
From: "Nicolas Rachinsky" <crypto-0@ml.turing-complete.org>
Subject: Re: Fermat's primality test vs. Miller-Rabin
>* Joseph Ashwood <ashwood@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@metzdowd.com
