Fermat's primality test vs. Miller-Rabin

[Nicolas Rachinsky]

* Joseph Ashwood <ashwood at msn.com> [2005-11-22 02:50 -0800]:
> ----- Original Message ----- 
> From: "Anton Stiglic" <astiglic at 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 at metzdowd.com