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