Sorry, an error occurred while loading the content.
Browse Groups

• ## Re: [PrimeNumbers] Nuutti Kuosa et al.'s Factorial Prime search.

(5)
• NextPrevious
• ... If you want old contents of a URL then try the Internet Archive: http://www.archive.org http://web.archive.org/web/20040922151554/http://powersum.dhis.org/
Message 1 of 5 , Nov 1, 2005
View Source
Phil Carmody wrote:

> Apparently I have the most complete mirror of Nuutti's site, and
> the most up-to-date information, but unfortunately some of it is
> contradictory. Does anyone have any information about completed
> ranges that is more up-to-date than the info at:
> http://fatphil.org/Nuutti/
> http://fatphil.org/Nuutti/minus/minus.html

If you want old contents of a URL then try the Internet Archive:
http://www.archive.org

http://web.archive.org/web/20040922151554/http://powersum.dhis.org/

--
Jens Kruse Andersen
• ... 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.