mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-05-31, 21:00   #1
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default 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
3.14159 is offline   Reply With Quote
Old 2010-05-31, 23:57   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67208 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2010-06-01, 00:01   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
philmoore is offline   Reply With Quote
Old 2010-06-01, 00:20   #4
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-06-01, 00:30   #5
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-06-01, 01:17   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24×13×17 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2010-06-01, 01:21   #7
axn
 
axn's Avatar
 
Jun 2003

132516 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
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?
axn is offline   Reply With Quote
Old 2010-06-01, 01:29   #8
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

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
3.14159 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java applet alternative a1call Programming 19 2019-11-08 22:31
New feature in my ECM applet alpertron Factoring 87 2014-11-21 21:23
New online applet for factorization ET_ Lone Mersenne Hunters 69 2014-06-01 17:34
GMP-ECM vs. Alpertron's factoring applet ixfd64 GMP-ECM 4 2006-01-02 13:13
Faster factorization applet alpertron Factoring 14 2006-01-01 04:00

All times are UTC. The time now is 20:48.

Mon Apr 12 20:48:18 UTC 2021 up 4 days, 15:29, 1 user, load averages: 2.88, 2.65, 2.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.