## Re: [PrimeNumbers] Proving a smooth number +/- 1 prime

Expand Messages
• ... Yes, this and more is true. Any number n can be proven prime/composite easily , in time O(d^2 * log d * log log d) where d = log n, _if_ enough of the
Message 1 of 5 , Nov 1, 2005
Ed Pegg Jr. wrote:

> Is the following true?
>
> 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.

Yes, this and more is true. Any number n can be proven prime/composite
"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
proven primes.

> 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
"classical tests".
See the Prime Pages for details: http://primes.utm.edu/prove/prove3.html

The popular flexible program PrimeForm/GW implements a BLS proof
(Brillhart-Lehmer-Selfridge).
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
n+/-1 factorization.
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
Your message has been successfully submitted and would be delivered to recipients shortly.