A strange applet:
 

[url]http://computerscience.jbpub.com/cryptography/TestPrimeGeneratorApplet.cfm[/url]

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

[QUOTE]Its original version, due to Gary L. Miller, is deterministic, but the determinism relies on the unproven generalized Riemann hypothesis.[/QUOTE]
-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...

There is a cottage industry in turning Rabin-Miller into a deterministic test. For example, passing Rabin-Miller with the first 5 bases is enough to guarantee primality for any 64-bit number, with a small number (less than 10) of exceptions that can be explicitly tested for.

Also, the 1-in-4 odds of passing one Rabin-Miller test is worst-case, and for large classes of inputs the odds of failure are much smaller.

[QUOTE=jasonp;216867]Also, the 1-in-4 odds of passing one Rabin-Miller test is worst-case, and for large classes of inputs the odds of failure are much smaller.[/QUOTE]

Look up the theorem of Damgard, Landrock, and Pomerance. The conclusions are described in Crandall and Pomerance, [I]Prime Numbers, A Computational Perspective.[/I]

[QUOTE]There is a cottage industry in turning Rabin-Miller into a deterministic test. For example, passing Rabin-Miller with the first 5 bases is enough to guarantee primality for any 64-bit number, with a small number (less than 10) of exceptions that can be explicitly tested for.[/QUOTE]

10 pseudoprimes that pass the Miller-Rabin at 5 bases? If you have them, feel free to post factorizations of them. Shouldn't it be 1 in 1024 that's a pseudoprime? Mersennewiki did say the odds of 100 iterations landing a pseudoprime would be less than 1 in 10^60. (1 in 4^100). I tried searching for a quick list of pseudoprimes that passed Miller-Rabin. Are those the SPRP pseudoprimes?
*goes to test SPRP pseudoprimes*

Hmm.. It's not SPRP pseudoprimes. The test is so excellent, there is no list of pseudoprimes collected for it. :lol:! (Or is there? If there is, link me?) Update: Found some.
Listed here:
2047 (Base 2) = 23 * 89
1373653 (Bases 2 and 3) = 829 * 1657
25326001 (Bases 2, 3, 5) = 2251 * 11251
3215031751 (Bases 2, 3, 5, 7) = 151 * 751 * 28351
2152302898747 (Bases 2, 3, 5, 7, 11) = 6763 * 10627 * 29947
3474749660383 (Bases 2, 3, 5, 7, 11, 13) = 1303 * 16927 * 157543
341550071728321 (Bases 2, 3, 5, 7, 11, 13, 17) + (Bases 2, 3, 5, 7, 11, 13, 17, 19) ? = 10670053 * 32010157
Could not find failures for 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, etc.. (I'm guessing there are an infinite amount of failures.)

[CODE]Attempting Miller-Rabin on 8753: (Required for primality: Passing for base 2, 3)
8752 = 2^s * d
8752 = 2^4 * 547
a^(2^(0-4) * 547) mod 8753 = -1
Try on primes 2, 3 for a:
2^547 mod 8753 = 3109
2^1094 mod 8753 = 2569
2^2188 mod 8753 = 8752 = -1
Passed for base 2
Attempting on base 3:
3^547 mod 8753 = 4465
3^1094 mod 8753 = 5644
3^2188 mod 8753 = 2569
2^4376 mod 8753 = 8752 = -1
Passed for base 3
8753 is prime. QED. [/CODE]

(Reversal of 4465 on 3^547 and 3^1094 mod 8753. Interesting coincidence.)

Miller-Rabin test: Simple, yet effective, and not requiring hundreds of trials. (By "hundreds of trials", I am referring to trial division and its many variations, along with Fermat's and Dixon's.)

Which brings a random question: Are there, say, any pseudoprime numbers that pass Miller-Rabin that act similarly to Carmichael numbers? (The natural enemy of Fermat's primality test.)

See [url="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html"]here[/url] for a list of exceptions to multiple Rabin-Miller tests. From the GMP-ECM source:
[code]
if (SP_NUMB_BITS <= 32)
{
/* 32-bit primality test
* See http://primes.utm.edu/prove/prove2_3.html */

if (!sp_spp (2, x, d) || !sp_spp (7, x, d) || !sp_spp (61, x, d))
return 0;
}
else
{
ASSERT (SP_NUMB_BITS <= 64);
/* 64-bit primality test
* follows from results by Jaeschke, "On strong pseudoprimes to several
* bases" Math. Comp. 61 (1993) p916 */

if (!sp_spp (2, x, d) || !sp_spp (3, x, d) || !sp_spp (5, x, d)
|| !sp_spp (7, x, d) || !sp_spp (11, x, d) || !sp_spp (13, x, d)
|| !sp_spp (17, x, d) || ! sp_spp (19, x, d) || !sp_spp (23, x, d)
|| !sp_spp (29, x, d))
return 0;
}
[/code]
There is no Rabin-Miller version of Carmichael numbers; the asymptotic probability of failure is the same for any input. This makes R-M nice for cryptographic applications that need large random primes in a fixed time with fixed chance of an error.

[QUOTE=3.14159;216871]Which brings a random question: Are there, say, any pseudoprime numbers that pass Miller-Rabin that act similarly to Carmichael numbers? (The natural enemy of Fermat's primality test.)[/QUOTE]

HINT:- Where did that 1-in-4 figure come from?

Based it on Mersennewiki's saying that the chances of 100 iterations yielding a pseudoprime at random were 1 in 4^100, or less than 1 in 10^60. I then just applied some (probably misleading} deductive reasoning, and concluded that the chances of it failing were 1 in 4^n, when n is the amount of bases tested for. Or is that an outdated figure?


Support from the source Jasonp listed: [QUOTE]If n multiple independent tests are performed on a composite number, then the probability that it passes each test is 1/4[SUP]n[/SUP] or less.[/QUOTE]

n = 1: Chances of failing: 1 in 4[SUP]1[/SUP], or 0.25, or 1/4. This is where I got the 1 in 4 figure from.

@Jasonp: In fact, the test gets better as the integers n become larger, because pseudoprimes become more and more rare, on average. (Trying to source this one.)

Alright: I found the fails for bases 2-23, 29, 31 and 2-37:
3825123056546413051 = 149491 * 747451 * 34233211
318665857834031151167461 = 399165290221 * 798330580441

To make up for the flaws.. A combination of tests should be performed. It might have failed Miller-Rabin, but maybe Lucas/Fermat's would detect this?