Re: Re: Verifying PrimeQ for n >10^16
- To: mathgroup at smc.vnet.net
- Subject: [mg21552] Re: [mg21518] Re: Verifying PrimeQ for n >10^16
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 15 Jan 2000 02:03:57 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
The reason why PrimeQ is limited to primes less that 10^16 has nothing do do with Mathematica, memory and any computer related factors. It's just mathematics. PrimeQ checks if a number is prime by applying three tests: the 2 and 3 strong pseudo-prime test (basicaly Fermat's little theorem) and the so called Lukas test. Any number that fails any of these is definitely composite but it is possible for a number to pass all the tests and not be prime. It's just that no such number has ever been found. In very few (if any) experts believe that these tests are sufficient but a "false prime" may be so large that it may never be encountered. > From: sniff <sniff at home.com> To: mathgroup at smc.vnet.net > Organization: SBC Internet Services > Date: Fri, 14 Jan 2000 02:43:34 -0500 (EST) > To: mathgroup at smc.vnet.net > Subject: [mg21552] [mg21518] Re: Verifying PrimeQ for n >10^16 > > 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. > > GTO > > > Ersek, Ted R wrote in message <85i09v$1o5 at smc.vnet.net>... >> 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. >> >> 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 > 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 >> had a major update >> >> >> > >