20100531, 21:00  #1  
May 2010
Prime hunting commission.
1680_{10} 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 MillerRabin 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 MillerRabin 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 2SPRP: 2047: 23 * 89 Quote:
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 20100531 at 21:28 

20100531, 23:57  #2 
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
There is a cottage industry in turning RabinMiller into a deterministic test. For example, passing RabinMiller with the first 5 bases is enough to guarantee primality for any 64bit number, with a small number (less than 10) of exceptions that can be explicitly tested for.
Also, the 1in4 odds of passing one RabinMiller test is worstcase, and for large classes of inputs the odds of failure are much smaller. 
20100601, 00:01  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
2×13×43 Posts 
Look up the theorem of Damgard, Landrock, and Pomerance. The conclusions are described in Crandall and Pomerance, Prime Numbers, A Computational Perspective.

20100601, 00:20  #4  
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
Quote:
*goes to test SPRP pseudoprimes* Last fiddled with by 3.14159 on 20100601 at 00:25 

20100601, 00:30  #5 
May 2010
Prime hunting commission.
2^{4}×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 MillerRabin on 8753: (Required for primality: Passing for base 2, 3) 8752 = 2^s * d 8752 = 2^4 * 547 a^(2^(04) * 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. MillerRabin 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 MillerRabin that act similarly to Carmichael numbers? (The natural enemy of Fermat's primality test.) Last fiddled with by 3.14159 on 20100601 at 01:17 
20100601, 01:17  #6 
Tribal Bullet
Oct 2004
2·3·19·31 Posts 
See here for a list of exceptions to multiple RabinMiller tests. From the GMPECM source:
Code:
if (SP_NUMB_BITS <= 32) { /* 32bit 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); /* 64bit 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; } 
20100601, 01:21  #7 
Jun 2003
1001011111000_{2} Posts 

20100601, 01:29  #8  
May 2010
Prime hunting commission.
2^{4}×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:
@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 223, 29, 31 and 237: 3825123056546413051 = 149491 * 747451 * 34233211 318665857834031151167461 = 399165290221 * 798330580441 To make up for the flaws.. A combination of tests should be performed. It might have failed MillerRabin, but maybe Lucas/Fermat's would detect this? Last fiddled with by 3.14159 on 20100601 at 01:55 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java applet alternative  a1call  Programming  19  20191108 22:31 
New feature in my ECM applet  alpertron  Factoring  87  20141121 21:23 
New online applet for factorization  ET_  Lone Mersenne Hunters  69  20140601 17:34 
GMPECM vs. Alpertron's factoring applet  ixfd64  GMPECM  4  20060102 13:13 
Faster factorization applet  alpertron  Factoring  14  20060101 04:00 