mersenneforum.org A strange applet:
 Register FAQ Search Today's Posts Mark Forums Read

2010-05-31, 21:00   #1
3.14159

May 2010
Prime hunting commission.

32208 Posts
A strange applet:

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

Quote:
 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

 2010-05-31, 23:57 #2 jasonp Tribal Bullet     Oct 2004 33·131 Posts 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.
2010-06-01, 00:01   #3
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts

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

2010-06-01, 00:20   #4
3.14159

May 2010
Prime hunting commission.

69016 Posts

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

Last fiddled with by 3.14159 on 2010-06-01 at 00:25

 2010-06-01, 00:30 #5 3.14159     May 2010 Prime hunting commission. 24×3×5×7 Posts 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.) 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. (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.) Last fiddled with by 3.14159 on 2010-06-01 at 01:17
 2010-06-01, 01:17 #6 jasonp Tribal Bullet     Oct 2004 33×131 Posts See here 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; } 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.
2010-06-01, 01:21   #7
axn

Jun 2003

135F16 Posts

Quote:
 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?

2010-06-01, 01:29   #8
3.14159

May 2010
Prime hunting commission.

24×3×5×7 Posts

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/4n or less.
n = 1: Chances of failing: 1 in 41, 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?

Last fiddled with by 3.14159 on 2010-06-01 at 01:55

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Programming 19 2019-11-08 22:31 alpertron Factoring 87 2014-11-21 21:23 ET_ Lone Mersenne Hunters 69 2014-06-01 17:34 ixfd64 GMP-ECM 4 2006-01-02 13:13 alpertron Factoring 14 2006-01-01 04:00

All times are UTC. The time now is 17:01.

Fri May 7 17:01:17 UTC 2021 up 29 days, 11:42, 0 users, load averages: 2.39, 2.43, 2.71

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.