A strange applet:

[3.14159]

http://computerscience.jbpub.com/cry...atorApplet.cfm

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...

[jasonp]

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.

[philmoore]

Originally Posted by jasonp

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.

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

[3.14159]

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.

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*

[3.14159]

Hmm.. It's not SPRP pseudoprimes. The test is so excellent, there is no list of pseudoprimes collected for it. ! (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.)

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.

(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.)

[jasonp]

See here for a list of exceptions to multiple Rabin-Miller tests. From the GMP-ECM source:

  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;
    }

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.

[axn]

Originally Posted by 3.14159

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.)

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

[3.14159]

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:

If n multiple independent tests are performed on a composite number, then the probability that it passes each test is 1/4ⁿ or less.

n = 1: Chances of failing: 1 in 4¹, 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?