- Good projects never die, they simply reserve the right to take

a rest every so often. However, I, and others, think the factorial

prime seach has rested quite long enough!

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

I have re-written my factorial sieve, it's now much faster (maybe

somewhere close to the speed of Mark's excellent multisieve), and

have been running it for a week or so, and will be making acceptably-

sieved ranges available for reservation in the next few weeks.

(My p=6G sieving limit last time was pretty pathetic to be honest!)

I'll keep sieving for months, obviously.

Anyway, this was just a little bit of an pre-announcement, so that

those who are coming to the end of projects, or are between projects,

can perhaps plan what to do with their CPUs in 2006.

I'll post again when ranges are available for automatic reservation

and download, which will be after I am fairly sure that I know

exactly what has been tested and what hasn't.

Thanks to Thommy for giving me a kick, I've been meaning to do this

for a long time.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________

Yahoo! Mail - PC Magazine Editors' Choice 2005

http://mail.yahoo.com - 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.

If so, what is the primality proof method called?

Ed Pegg Jr. - ed pegg wrote:

> Is the following true?

The Prime Pages contain all sorts of useful knowledge about prime

>

> 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.

>

> If so, what is the primality proof method called?

>

> Ed Pegg Jr.

>

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

numbers. For your question, yes, it's true, it can be established with

certainty, and it's not just limited to 20,000 digits. In fact, by

modifying the tests, you don't have to completely factor 'N-1' or 'N+1'

... you just have to factor them 'enough'. See

http://primes.utm.edu/prove/index.html for more information on the 'N-1'

tests and the 'N+1' tests. These pages will also give you references to

find more detailed information.

Jonathan Zylstra

>

[Non-text portions of this message have been removed]

>

> SPONSORED LINKS

> Mathematics education

> <http://groups.yahoo.com/gads?t=ms&k=Mathematics+education&w1=Mathematics+education&w2=Mathematics+and+computer+science&c=2&s=65&.sig=b8LsamuyXOKzvph6maOt9A>

> Mathematics and computer science

> <http://groups.yahoo.com/gads?t=ms&k=Mathematics+and+computer+science&w1=Mathematics+education&w2=Mathematics+and+computer+science&c=2&s=65&.sig=upRd0RlEZqv_h9-dxultrg>

>

>

>

> ------------------------------------------------------------------------

> YAHOO! GROUPS LINKS

>

> * Visit your group "primenumbers

> <http://groups.yahoo.com/group/primenumbers>" on the web.

>

> * To unsubscribe from this group, send an email to:

> primenumbers-unsubscribe@yahoogroups.com

> <mailto:primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe>

>

> * Your use of Yahoo! Groups is subject to the Yahoo! Terms of

> Service <http://docs.yahoo.com/info/terms/>.

>

>

> ------------------------------------------------------------------------

>

- Phil Carmody wrote:

> Apparently I have the most complete mirror of Nuutti's site, and

If you want old contents of a URL then try the Internet Archive:

> 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

http://www.archive.org

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

--

Jens Kruse Andersen - Ed 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

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