The probable primes

[TimSorbet]

(due to length limitations, instead of having the giant number here, I'm just going to link to its page at the FactorDB, and replace it throughout with 'm')

m is chosen as the odd number such that 2^21954+77899=m*2^n-1.
m=(2^21954+77900)/4

2^21954+77899=m*2^2-1

This has already been proven prime by conventional means, and is just being used as an example.
Here's what PFGW does with it, with this command: "-qm*2^2-1 -tp"

PFGW Version 3.3.1.20100111.Win_Dev [GWNUM 25.13]

Primality testing m*2^2-1 [N+1, Brillhart-Lehmer-Selfridge]
Running N+1 test using discriminant 5, base 1+sqrt(5)
Generic modular reduction using generic reduction FFT length 2048 on 2^21954+77899
Calling Brillhart-Lehmer-Selfridge with factored part 0.28%
m*2^2-1 is Lucas PRP! (9.3029s+0.0805s)

Done.

Why did it revert to a PRP test instead of being able to do a N+1 primality test? Read this from pfgwdoc.txt: (bold mine for emphasis)

A.3. More details/methods used

Pfgw can work with numbers from 2 up to almost 2^79700000 (about 24000000
digits). It can find probable primes with Fermat's method, with bases
from 2 to 256.
To be more precise: The largest FFT is 4 million elements long, with 19
bits per element. GFN's can be tested upto 24M digits, and generic numbers
upto 12M digits.
To prove a number prime, other methods need to be used.
Only a small percentage of all numbers can be easily proven prime.
Name a number N, then you must be able to factor N-1 or N+1 to 33.33% to
find a proof using PFGW.
If N-1 is factored deep enough, then Pocklington's test can be applied.
If N+1 is factored deep enough, then Morrison's test can be applied.
If N^2-1 is factored deep enough, a combined method can be used.

A.3.1 Fermat's method
Fermat's method is NOT a proof, but more like a quick indicator that a
number might be prime.

A.3.2 Pocklington's test
This test can be used whenever N-1 can be factored to 33.33% of the size
of N. (Actually, the factored part must be greater than the cube root of
N/1000000). This test is conclusive.

A.3.3 Morrison's test
This test can be used whenever N+1 can be factored to 33.33% of the size
of N. (Actually, the factored part must be greater than the cube root of
N/1000000). This test is conclusive.

A.3.4 F-Strong test
This test is used when you use the -t option, and your factors don't reach
the magic 33.33%. It is a strong-primality test, and gives more certainty
than a Fermat test, but still is NOT a proof!

So unless N+1 can be factored to 33.33% of the size of N, you can't do the conclusive N+1 test. (and same thing with N-1) It is, of course, possible to turn any number into k*b^n-1, and (I think) possible to use an N+1 test on any number, but unless the k is smaller than b^n, you probably won't meet that magic 33.33% size limit without factoring N+1.
So you can trade a difficult primality test for an easy one in addition to a difficult factoring. It is MUCH easier to do a primality test on a number with thousands of digits than to try to factor a number with thousands of digits. With current hardware and methods, and without extraordinary luck, it's basically impossible to factor m.

[Batalov]

Kenneth-

In addition to what Tim wrote, I can add that for some special forms we can use the "helper" primes. One of the larger examples that I found last summer was a 9016-digit PRP
N = (52*10^9015-43)/9 = 57777...77773 (many sevens in the middle).

Why is that? That's because N-1 factors to slightly more than 33.33%.
The rich collection of repunits is studied fairly well, and it turns out that
N-1 = (52*10^9015-43)/9 -1 =
= (52*10^9015-52)/9 =
= 2^2*13*(10^9015-1)/9 =
= 2^2*13*(10^3005-1)/9 * c6011
But (10^3005-1)/9 happens to be fully factored (which is lucky! because this is 33.33% of the N-1).

After proving primality of the 2379-digit cofactor with Primo, I provided these and a few small prime factors from the 6011-digit cofactor in a helper file, and voila - a proof by PFGW with 33.62% factored part. All less than in a day (including Primo).

Primality testing (52*10^9015-43)/9 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file ../h9015
Running N-1 test using base 2
Running N+1 test using discriminant 5, base 5+sqrt(5)
Calling N-1 BLS with factored part 33.62% and helper 0.05% (100.92% proof)
(52*10^9015-43)/9 is prime! (27.5956s+0.0014s)

There are much more elegant examples (see openpfgw yahoo group), but this is one is very simple to tell in one paragraph. (not bragging; this is not a very large number)

See PFGW's manual about the helper file.

-Serge

[philmoore]

A followup on the notice from Wilfrid Keller:

He has now confirmed that all primes (or prps) up to 2⁶¹⁷⁹²+21661 are indeed the smallest in their respective sequences, and has tested the remaining sequences out to n = 42000. I have independently confirmed all of his findings, and continued up to 2⁵⁵¹⁵⁴²+19249. This leaves only the six largest probable primes not confirmed to be the smallest in their sequences, so I will slowly continue this project. We did find one more error on Payam Samidoost's webpage, the prime 2¹⁶²²+32449 was apparently missed, as the prime listed for that sequence was 2¹⁸¹⁴+32449. Given that 2¹⁸⁸⁵+29777 was also missed, but later discovered, I suspect some errors in early versions of pfgw. Mark assures me that error checking is much more robust in the current version. Samidoost's webpage has disappeared, but I replaced the link with the cached version of Neil Sloane's:
http://www.research.att.com/~njas/se.../a076336c.html

I intend to prepare a file of Sloane sequence A067760 as far as (78557-1)/2soon and upload it to the Forum.

[Cybertronic]

Status:
Phase 1:TEST 200 (9879 digits left, 70 days to go)
Phase 2:TEST 1-159 done.

[Cybertronic]

Status:
Phase 1:TEST 250 (9365 digits left, 60 days to go)
Phase 2:TEST 1-209 done.

[Cybertronic]

Happy easter !

Now I'm below 30000 bits ! 60% done.

[Cybertronic]

Status:
Phase 1 TEST 300, 8895 digits left, 46 days left
Phase 2 252 TESTs done

Next report at TEST 400 in 14 days

[Cybertronic]

Status:
Phase 1 TEST 400, 8032 digits left, 32 days left
Phase 2 345 TESTs done

Next report at TEST 600 at May, 7th

[Cybertronic]

So people , new status.. not 600, but 566

Phase 1 at TEST 566 (6699 digits left)
Phase 2 TESTs 1-499 done.

May, 25th was calculated ... then the certificate is available.

[Cybertronic]

Status:
Phase 1 at TEST 800, 4916 digits left
Phase 2 1-720 done
Signing points 1-684 complete

[Cybertronic]

In PRIMO , I like this number !
http://www.sendspace.com/file/1un0wn