View Single Post
Old 2010-05-31, 21:00   #1
3.14159's Avatar
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default A strange applet:

I attempted to generate a pseudoprime: After 150 frustrated clicks, I had no luck. The odds of a number being a pseudoprime that passed only 1 base of the Miller-Rabin test are supposed to be only 1 in 4. Reasons I have thought of:
1. The odds beat me.
2. The applet excludes pseudoprimes, because the Miller-Rabin test here is actually a deterministic test (This is more likely.)

If you can generate a pseudoprime, feel free to post it and its factorization.

A base 2-SPRP: 2047: 23 * 89

Its original version, due to Gary L. Miller, is deterministic, but the determinism relies on the unproven generalized Riemann hypothesis.
-Wiki on Miller-Rabin test

But it apparently was later modified to a probabilistic test. It's unlikely that the app uses the deterministic test. I just can't see how 1 in 4 is dodged for 150 clicks. (Note: Tried it on small primes.).. Unless 1 in 4^n was being too generous for the appearance of pseudoprimes.

Update: Nevermind my not seeing how 1 in 4 is dodged for 150 clicks. Probable explanation: It uses random bases as well. But that does not close the possibility of a pseudoprime appearing...

Last fiddled with by 3.14159 on 2010-05-31 at 21:28
3.14159 is offline   Reply With Quote