- **Miscellaneous Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=56*)

- - **A strange applet:**
(*https://www.mersenneforum.org/showthread.php?t=13469*)

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

All times are UTC. The time now is 21:55. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.