N=2^64695-2^15-1 is prime.

Paul Underwood discovered that N is

probably prime, as part of a large trawl

of candidates of his favourite form

f(a,b)=2^a-2^b-1

with large a and small b.

Bouk de Water observed that

N+1=2^15*(2^64680-1)

is highly composite, since

64680=2*2*2*3*5*7*7*11

has 96 divisors.

Moreover he found the 1012-digit prime

p1012=gcd(phi(4*8085,2),2^8085-2^4043+1)

which divides N+1.

By late July, David Broadhurst had used ecm-gmp on

all of 11 remaining composite cofactors of

{Phi(d,2);d|64680} (and their Aurifeuillian parts,

when d=4 mod 8) which had less than 600 digits,

making 1800 attempts on each of these 11 at B1=10^6,

i.e. p35 level. This took O(100) GHz-days of effort.

Working on largest cofactor,

Paul Leyland found that

p26=13304801278785221502712801

divides Phi(64680,2) with more than 4000 digits.

At this stage we lacked 221 digits of factorization,

and Paul Leyland contemplated using NFS on the

smallest composite, with 162 digits, if another

50 digits could be found with ECM.

In the event, NFS was not needed.

Paul Underwood used prime95 to find 2 large

factors of N+1=2^15*(2^64680-1), namely

p43=1974132723329736593062151838364049346634561

p41=37131299037462589694325096898604106162577

with the second leaving a 154-digit prime

in the now completed factorization of the

Aurifeuillian factor

gcd(phi(4*1617,2),2^1617+2^809+1)=

6469*1346555145625865869*p38*p41*p154

where

p38=10816328089875303012806778969765211273

had already been found by ecm-gmp.

We now had 30.08% factorization of the

digits of N+1, sufficient for a

Konyagin-Pomerance proof.

The actual primality proving was easy:

about a quarter of an hour of pfgw,

for the Lucas tests,

Primality testing 2^15*(2^64680-1)-1

[N+1, Brillhart-Lehmer-Selfridge]

Calling Brillhart-Lehmer-Selfridge

with factored part 30.08%

2^15*(2^64680-1)-1 is Lucas PRP!

(1060.780000 seconds)

and then a few minutes of Pari-GP to complete

the proof using the pair of Konyagin-Pomerance

cubics of Theorem 4.2.9 of the book by

Crandall and Pomerance. The code for this

was written by David Broadhurst and had been

checked by Andy Steward in the course of

proving primality of (3048^3121-1)/3047.

We also used 90 minutes of Primo to prove primality

of the prime factors of N+1, the largest known

being p1012, above.

By no stretch of the imagination is

N=2^64695-2^15-1

an "ordinary" prime. It is extraordinary

by the circumstance that it _just_ permitted

a Konyagin-Pomerance proof by factorization of N+1,

using cyclotomic and Aurifeuillian theory and

the best factoring engines available.

At 19476 decimal digits, it holds the record

for a very special type of proof:

"easy after much difficult factoring".

The previous record of this type was held

by Fibonacci(81839) with 17103 digits.

The record for proving a _truly_ ordinary prime

still stands at 5020 digits:

http://www.znz.freesurf.fr/pages/primotop20.html
David Broadhurst