Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #13140 > unrolled thread
| Started by | johnfeth@gmail.com |
|---|---|
| First post | 2013-01-15 04:28 +0000 |
| Last post | 2013-01-23 04:18 +0000 |
| Articles | 5 — 3 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
Prime numbers and primality tests johnfeth@gmail.com - 2013-01-15 04:28 +0000
Re: Prime numbers and primality tests amzoti <amzoti@gmail.com> - 2013-01-19 06:14 +0000
Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-20 06:25 +0000
Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-21 05:06 +0000
Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-23 04:18 +0000
| From | johnfeth@gmail.com |
|---|---|
| Date | 2013-01-15 04:28 +0000 |
| Subject | Prime numbers and primality tests |
| Message-ID | <kd2lt4$co5$1@smc.vnet.net> |
A straightforward way to test a prime number candidate is the Miller-Rabin test (sometimes called the Rabin-Miller test). This well known and popular test is commonly executed 50 times on a candidate prime and has a proven probability of missing a non-prime of no more than 0.25 for each execution. Note that passing 50 Miller-Rabin tests (which is a de facto standard), the probability of non-primality is 0.25^50 ~ 7.9*10^-31, I'm satisfied that the number NextPrime gives me is "prime enough". Mathematica uses the Miller-Rabin test, although it is not clear how many iterations are used. As I understand it, Mathematica also the Lucas pseudo prime test on the Miller-Rabin output. It is interesting to note, however, that the Lucas pseudo prime method of primality testing apparently does not have the handy "feature" of the Miller-Rabin test, namely, the provable, and bounded low probability of a wrong answer, from whence an estimate of primality for any number can be made without finding a counter example! I've read that there are have been no counter-examples (viz., no non-primes that pass the the Lucas pseudo prime test) to numbers that pass the Lucas pseudo prime test, but then again, I've never found an oyster with a pearl inside. Is the Miller-Rabin a better test that the Lucas pseudo prime test? http://reference.wolfram.com/mathematica/tutorial/IntegerAndNumberTheoreticalFunctions.html http://reference.wolfram.com/mathematica/tutorial/SomeNotesOnInternalImplementation.html http://mathworld.wolfram.com/LucasPseudoprime.html
[toc] | [next] | [standalone]
| From | amzoti <amzoti@gmail.com> |
|---|---|
| Date | 2013-01-19 06:14 +0000 |
| Message-ID | <kdddj8$a1n$1@smc.vnet.net> |
| In reply to | #13140 |
On Monday, January 14, 2013 8:28:20 PM UTC-8, john...@gmail.com wrote: > A straightforward way to test a prime number candidate is the Miller-Rabin test (sometimes called the Rabin-Miller test). This well known and popular test is commonly executed 50 times on a candidate prime and has a proven probability of missing a non-prime of no more than 0.25 for each execution. Note that passing 50 Miller-Rabin tests (which is a de facto standard), the probability of non-primality is 0.25^50 ~ 7.9*10^-31, I'm satisfied that the number NextPrime gives me is "prime enough". Mathematica uses the Miller-Rabin test, although it is not clear how many iterations are used. As I understand it, Mathematica also the Lucas pseudo prime test on the Miller-Rabin output. > > > > It is interesting to note, however, that the Lucas pseudo prime method of primality testing apparently does not have the handy "feature" of the Miller-Rabin test, namely, the provable, and bounded low probability of a wrong answer, from whence an estimate of primality for any number can be made without finding a counter example! > > > > I've read that there are have been no counter-examples (viz., no non-primes that pass the the Lucas pseudo prime test) to numbers that pass the Lucas pseudo prime test, but then again, I've never found an oyster with a pearl inside. > > > > Is the Miller-Rabin a better test that the Lucas pseudo prime test? > > > > > > http://reference.wolfram.com/mathematica/tutorial/IntegerAndNumberTheoreticalFunctions.html > > > > http://reference.wolfram.com/mathematica/tutorial/SomeNotesOnInternalImplementation.html > > > > http://mathworld.wolfram.com/LucasPseudoprime.html How does your Miller-Rabin test fair against the following? 8038374574536394912570796143419421081388376882875581458374889175222974273765333652186502336163960045457915042023603208766569966760987284043965408232928738791850869166857328267761771029389697739470167082304286871099974399765441448453411558724506334092790222752962294149842306881685404326457534018329786111298960644845216191652872597534901 Using the two tests together make a better test and I wouldn't say that one is better than the other.
[toc] | [prev] | [next] | [standalone]
| From | RBaillie <bobbaillie@frii.com> |
|---|---|
| Date | 2013-01-20 06:25 +0000 |
| Message-ID | <kdg2kq$hf6$1@smc.vnet.net> |
| In reply to | #13140 |
I wouldn't use the Lucas pseudoprime test by itself. The key is to use a regular pseudoprime test a^(N-1) = 1 (mod N) (like Miller-Rabin) AND a Lucas test. The types of pseudoprimes that pass a regular test tend to have differ characteristics than those that pass a Lucas test. In other words, if you make a list of regular pseudoprimes (say, base 2) and another list of Lucas pseudoprimes, then the two lists tend to avoid each other and there is very little overlap, that is, few numbers that can survive both tests. This is explained in a paper, "Lucas Pseudoprimes", which you can find at http://mpqs.free.fr/LucasPseudoprimes.pdf Robert Baillie
[toc] | [prev] | [next] | [standalone]
| From | RBaillie <bobbaillie@frii.com> |
|---|---|
| Date | 2013-01-21 05:06 +0000 |
| Message-ID | <kdiicf$nbq$1@smc.vnet.net> |
| In reply to | #13221 |
I forgot to say: if a composite N passes the usual probable prime test b^(N-1) = 1 (mod N) for one base b, then it is more likely than the average number that size to pass another test, c^(N-1) = 1 (mod N). For example, N = 341 is a pseudoprime base 2, which means that 2^3401 (mod 341). There are 100 bases b between 1 and 340 such that b^340 = 1 (mod 341). On the other hand, if b^(N-1) = 1 (mod N), then this N seems (empirically and heuristically) to be LESS likely than average to pass a Lucas probable prime test. That's why I like to do one or more of EACH type of test, which I think is what PrimeQ does.
[toc] | [prev] | [next] | [standalone]
| From | RBaillie <bobbaillie@frii.com> |
|---|---|
| Date | 2013-01-23 04:18 +0000 |
| Message-ID | <kdnob4$72b$1@smc.vnet.net> |
| In reply to | #13140 |
The original post had this comment: "It is interesting to note, however, that the Lucas pseudo prime method of primality testing apparently does not have the handy "feature" of the Miller-Rabin test, namely, the provable, and bounded low probability of a wrong answer, from whence an estimate of primality for any number can be made without finding a counter example!" I just found this interesting article: "The Rabin-Monier Theorem for Lucas Pseudoprimes", by F. Arnault, in Mathematics of Computation, April, 1997. You can download it from http://www.ams.org/journals/mcom/1997-66-218/S0025-5718-97-00836-3 Theorem 1.3 in that article shows that the probability for each strong Lucas pseudoprime test is 4/15 (analogous to the probability 1/4 for a Miller-Rabin test). The key points, though, are these: First, if N is a strong pseudoprime base 2, it is more likely than the average number about that size to also be a strong pseudoprime base 3 (and other bases). So, if you make lists of strong pseudoprimes base 2 and base 3, those lists will overlap, meaning that there are composite numbers that are strong pseudoprimes bases 2 and 3 (and 5, and 7, ...). Second, if you use any of the algorithms in the "Lucas Pseudoprime" paper at http://mpqs.free.fr/LucasPseudoprimes.pdf to make a list of strong Lucas pseudoprimes, then this list has no known overlap with the list of strong pseudoprimes base 2. It has been checked that any number up to at least 10^16 that passes both types of these strong pseudoprime tests is a prime. This is why many prime-testing functions (e.g, PrimeQ) do at least one of each type of test, instead of just doing standard strong pseudoprime tests to a bunch of different bases 2, 3, ... .
[toc] | [prev] | [standalone]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web