MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Verifying PrimeQ for n >10^16

  • To: mathgroup at
  • Subject: [mg21518] Re: Verifying PrimeQ for n >10^16
  • From: sniff <sniff at>
  • Date: Fri, 14 Jan 2000 02:43:34 -0500 (EST)
  • Organization: SBC Internet Services
  • References: <85i09v$>
  • Sender: owner-wri-mathgroup at

You could use the Lucas-Lehmer theorem to proof for Mersenne primes larger
than 10^16 that PrimeQ works or not. If you can find one case where PrimeQ
fails, you are done. Otherwise, ................

You can find more about the LL theorem on the Web or in Knuth's book about
"The Art of Computer Programming". I am not sure why PrimeQ is limited to
primes less than 10^16. Usually Mathematica does a good job as long as enough
virtual memory space is available. - One reason for this strange limitation
could be the fact that very large primes that are _not_ Mersenne primes are
held top secret. The are excellent seeds for encryption.


Ersek, Ted R wrote in message <85i09v$1o5 at>...
>The documentation for Mathematica 4 indicates PrimeQ has been
>proven correct for all (n<10^16), but there may be larger composite
>that PrimeQ indicates are prime.
>I have often wanted to write a program that would verify PrimeQ, starting
>with 10^16, for each integer that PrimeQ says is prime.
>The ProvablePrimeQ package goes about this in a way that is more rigorous
>than we need.  To prove that n is prime ProvablePrimeQ proves that certain
>numbers less than n are prime, and it goes on in a recursive manner until
>gets to 2 which is definitely prime.
>If we are going to efficiently prove that n is prime the program should
>assume that PrimeQ is correct for all integers less than n. So far I
>been successful in writing such a program. This is mostly due to the fact
>that I have very little background in number theory. I wonder if anyone
>could provide the needed program.
>Now to improve the rate of progress we could have a few hundred computers
>work on it at the same time.  One computer could verify PrimeQ for the
>100,000 numbers after 10^16 that PrimeQ says are prime.  Another computer
>could verify PrimeQ for the next 100,000 numbers PrimeQ says are prime, and
>so on.  Each computer could churn away on it over night when they would
>otherwise do nothing.  Does anyone have an estimate of how fast this would
>work? Rather slow I bet, but what do we have to loose.
>I understand there may be no case where PrimeQ is wrong.  The frustrating
>thing is that thanks to Kurt Godel's theorem it may be impossible to prove
>that PrimeQ is always right (that's Godel with two dots over the "o").
>Ted Ersek
>On 12-18-99 Mathematica tips, tricks at
>had a major update

  • Prev by Date: Problem with evaluation of delayed rules
  • Next by Date: Re: Limit problem from analysis
  • Previous by thread: Re: Problem with evaluation of delayed rules
  • Next by thread: Re: Verifying PrimeQ for n >10^16