Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #13140 > unrolled thread

Prime numbers and primality tests

Started byjohnfeth@gmail.com
First post2013-01-15 04:28 +0000
Last post2013-01-23 04:18 +0000
Articles 5 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  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

#13140 — Prime numbers and primality tests

Fromjohnfeth@gmail.com
Date2013-01-15 04:28 +0000
SubjectPrime 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]


#13203

Fromamzoti <amzoti@gmail.com>
Date2013-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]


#13221

FromRBaillie <bobbaillie@frii.com>
Date2013-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]


#13240

FromRBaillie <bobbaillie@frii.com>
Date2013-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]


#13251

FromRBaillie <bobbaillie@frii.com>
Date2013-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