17121Re: [PrimeNumbers] Proving a smooth number +/- 1 prime
- Nov 1, 2005Ed Pegg Jr. wrote:
> Is the following true?Yes, this and more is true. Any number n can be proven prime/composite
> For any number n with less than 20000 digits, if n+1 or n-1 is
> an easily factorable smooth number, then the primality/non-primality
> of n can be established with certainty.
"easily", in time O(d^2 * log d * log log d) where d = log n, _if_ enough of
the prime factorization of n+1 or n-1 is known.
This time is much faster than the average time to find a probable prime.
The known prime factors of n+/-1 don't have to be small, they just have to be
> If so, what is the primality proof method called?There are different proof methods with different names, depending on the form
and factorization percentage of n+/-1. The methods are generally called
See the Prime Pages for details: http://primes.utm.edu/prove/prove3.html
The popular flexible program PrimeForm/GW implements a BLS proof
PrimeForm/GW can prove any n up to a million or more digits, if the product of
known factors of n-1 or n+1 is at least n^(1/3), or a little less for combined
n-1 and n+1 proofs.
Some BLS "extensions" not implemented in PrimeForm can prove numbers with less
David Broadhurst's KP (Konyagin-Pomerance) PARI script can handle n^0.3.
John Renze's CHG (Coppersmith-Howgrave-Graham) PARI script (currently being
debugged) can handle down to around n^0.27, depending on the size of n, the
used computer, and the acceptable time.
It is utterly hopeless to find enough n+/-1 factorization to easily prove
primality of a random n above 1000 digits.
If you get "lucky", you can find a large probable prime cofactor of n-1 or
n+1. You cannot prove primality of that cofactor significantly easier than of
n itself, so it doesn't help in practice.
The largest proven prime n without large n+/-1 factorization is the ECPP
record with 15071 digits: http://primes.utm.edu/top20/page.php?id=27
The top-20 for a publicly available program is all with the ECPP program Primo
with record at 7993 digits: http://www.ellipsa.net/primo/top20.html
Jens Kruse Andersen
- << Previous post in topic