[19058] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Nicolas Rachinsky)
Fri Dec 2 12:39:05 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 30 Nov 2005 19:57:46 +0100
From: Nicolas Rachinsky <crypto-0@ml.turing-complete.org>
To: Joseph Ashwood <ashwood@msn.com>
Cc: cryptography@metzdowd.com
Mail-Followup-To: Nicolas Rachinsky <crypto-0@ml.turing-complete.org>,
Joseph Ashwood <ashwood@msn.com>, cryptography@metzdowd.com
In-Reply-To: <015e01c5ef52$8a813f10$6401a8c0@GQ7000>
* Joseph Ashwood <ashwood@msn.com> [2005-11-22 02:50 -0800]:
> ----- Original Message -----
> From: "Anton Stiglic" <astiglic@okiok.com>
> Subject: RE: Fermat's primality test vs. Miller-Rabin
>
>
> >-----Original Message-----
> >From: [Joseph Ashwood]
> >Subject: Re: Fermat's primality test vs. Miller-Rabin
> >>I think much of the problem is the way the number is being applied. Giving
> >>a stream of random numbers that have passed a single round of MR you will
> >>find that very close to 50% of them are not prime, this does not mean that
> >>it passes 50% of the numbers (the 2^-80 probability given above is of this
> >>type).
> >
> >Do you do an initial sieving to get rid of the more obvious primes?
>
> No I did not, since this was specifically to test the effectiveness of MR I
> determined that it would be better to test purely based on MR, and not use
> any sieving. The actual algorithm was:
>
>
> 16384 times
> {
> question = random 512-bit number
> //this is not the most efficient, but it should remove bias making this
> just MR
If I remember the proof of MR correctly it assumes an odd number. Were
all your questions odd?
If not, please try again with odd numbers only.
Nicolas
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
