       Re: Verifying PrimeQ for n >10^16

• To: mathgroup at smc.vnet.net
• Subject: [mg21526] Re: [mg21488] Verifying PrimeQ for n >10^16
• From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
• Date: Fri, 14 Jan 2000 02:43:42 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

```If you look at the PrattCertificate function in Stan Wagon's book
"Mathematica in Action" you will find that it has an option
AssumedPrimeBound, which you can set to 10^16. When you do that the function
assumes that PrimeQ is correct for numbers up to 10^16 (so it does not
bother to produce a prime certificate for them). However, the real
difficulty is that the Pratt certificate method requires one to factor n-1
(where n is the number being tested). In lucky cases this can be done for
extremly large numbers but may be impossible for  smaller ones. Thus the
idea of advancing inductively does not seem to be realistic. There are also
other methods, e.g. using elliptic functions, but I think one runs into
similar problems.

> From: "Ersek, Ted R" <ErsekTR at navair.navy.mil>
To: mathgroup at smc.vnet.net
> Date: Wed, 12 Jan 2000 08:35:34 -0500 (EST)
> To: mathgroup at smc.vnet.net
> Subject: [mg21526] [mg21488] Verifying PrimeQ for n >10^16
>
> The documentation for Mathematica 4 indicates PrimeQ has been
> proven correct for all (n<10^16), but there may be larger composite integers
> 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.
>
> 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 it
> 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 haven't
> 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 first
> 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").
>
> --------------------
> Regards,
> Ted Ersek
>
> On 12-18-99 Mathematica tips, tricks at
> http://www.dot.net.au/~elisha/ersek/Tricks.html