- Mike Oakes and I have a

Konyagin-Pomerance proof

at 28892 decimal digits.

The prime in question is

N=-norm((u+1)^30091-1)

where u=4+sqrt(17) is the

fundamental unit of K(sqrt(17)),

with norm(u)=-1.

Multiplying out, one sees that

N=-((5+sqrt(17))^30091-1)*((5-sqrt(17))^30091-1)

=-8^30091+(5+sqrt(17))^30091+(5-sqrt(17))^30091-1

=-8^30091+lucasV(10,8,30091)-1

with F=2^30091 dividing N+1 and hence

giving a fraction

log(2)/log(5+sqrt(17))=0.3135

of the digits of N+1, which is insufficient

for a BLS proof but sufficient for KP.

The proof then goes in two stages.

First we use Pfgw in -tp mode:

Primality testing -8^30091+lucasV(10,8,30091)-1

[N+1, Brillhart-Lehmer-Selfridge]

Running N+1 test using discriminant 3, base 1+sqrt(3)

Calling Brillhart-Lehmer-Selfridge with factored part 31.35%

-8^30091+lucasV(10,8,30091)-1 is Lucas PRP! (1385.150000 seconds)

Morrison's theorem [CP 4.2.3] then proves

that every prime divisor d|N satisfies

d=Legendre(12,d) mod F.

If we had F^3>N, Pfgw could complete

the proof with square tests, showing

that N has no proper divisors.

But we do not have enough digits for that.

Hence the next step is to implement

Konyagin-Pomerance for N+1 [CP 4.2.9].

I append the Pari-GP code.

It performs 11 square tests,

evaluates a continued fraction,

computes a pair of cubics,

with integer coefficients,

and shows that these cubics

have no integer roots. The method is

to determine the number of real roots

of the cubics. In this case,

each has 3 real roots.

Then it is sufficient to find 6 pairs

of successive integers between which

the cubics change sign, thereby

establishing that the roots are not integers.

For this, 8000-digit precision was sufficient.

Finally, we note that

N=-norm((5+sqrt(17))^p-1)

is prime for

p=2,5,13,19,107,1117,8059,20411,30091

and for no other exponent p<80000.

David Broadhurst

KP source code:

n=30091;

\p8000

pzr(z,r)=sum(k=1,4,z[k]*r^(4-k));

lucasV(p,q,n)=2*polcoeff(lift(Mod((p+x)/2,x^2+4*q-p^2)^n),0);

{rc(z)= \\ real root(s) of cubic

local(d,ans,a2,a1,a0,q,r,s,c,th,eps);

d=z[1];

ans=[];

if(d==0,

print("not a cubic"),

a2=z[2]/d;

a1=z[3]/d;

a0=z[4]/d;

q=a1/3-a2^2/9;

r=(a1*a2-3*a0)/6-a2^3/27;

if(q==0,

if(r>=0,

ans=[(2*r)^(1/3)-a2/3],

ans=[-(-2*r)^(1/3)-a2/3]),

s=sqrt(abs(q));

c=r/s^3;

if(q>0,

ans=[2*s*sinh(1/3*asinh(c))-a2/3],

if(c>1,

ans=[2*s*cosh(1/3*acosh(c))-a2/3],

if(c<-1,

ans=[-2*s*cosh(1/3*acosh(-c))-a2/3],

th=acos(c);

ans=vector(3,k,2*s*cos((th+2*k*Pi)/3)-a2/3))))));

ans}

N=-8^n+lucasV(10,8,n)-1;

F=2^n;

{print(n);

R=(N+1)/F;

ok=1;

if(denominator(R)==1&&R%2==1,

print("fraction = "round(10^6*log(F)/log(N))"/10^6"));

if(denominator(R)!=1||N>F^4||F^3>N,print("Fail");ok=0);

c1=((N+1)/F)%F;

c2=((N+1-c1*F)/F^2)%F;

c3=((N+1-c1*F-c2*F^2)/F^3);

c4=c3*F+c2;

for(t=-5,5,if(issquare((c1+t*F)^2-4*(t-c4)),

print("Fail "t);ok=0,print("OK "t)));

b=contfrac(c1/F);

v=0;vn=1;u=1;un=b[1];n=1;

while(F^4>vn^2*N,n=n+1;bn=b[n];uo=u;u=un;vo=v;v=vn;

un=bn*un+uo;vn=bn*vn+vo);

d=round(c4*v/F);

zs=[

[v,-u*F+c1*v,-c4*v+d*F-u,d],

[v,+u*F-c1*v,-c4*v-d*F-u,d]];

for(j=1,2,print();print("Case "j);z=zs[j];rs=rc(z);lr=length(rs);

for(k=1,lr,r=rs[k];rr=round(r);

print();print("Round of root:");print(rr);

tst=0;

if(pzr(z,rr)*pzr(z,rr+1)<0,tst=+1;print("Root OK: above the round"));

if(pzr(z,rr)*pzr(z,rr-1)<0,tst=-1;print("Root OK: below the round"));

if(tst==0,print("Fail");ok=0));

if(lr==1,print();print("Other roots are complex")));

print();

if(ok==1,print("Proof completed"),print("Not yet

completed"));print();} - David wrote:-
> Mike Oakes and I have a

Flattered as I am to be included in the credits by David, the fact is that I

> Konyagin-Pomerance proof

> at 28892 decimal digits.

did little more than put the idea into his head, by asking for help when I

noticed that the smaller examples (with exponents of 8059 and 20411) were

nearly-but-not-quite BLS provable, i.e. were factorable to 31.35% instead of

the necessary 33.333%.

Not only did he discover this currently-biggest "F-" form of prime himself,

and use massive amounts of computer power to rule out any more up to 80K, but

much more significantly, he single-handedly constructed and pushed through

(as I'm sure you'd guess, knowing his reputation as a leader in the field)

this remarkable KP proof.

So let me join in the applause for a truly heroic (world-record, even?)

achievement.

Mike

[Non-text portions of this message have been removed] - Mike:
> single-handedly constructed and pushed through

is a bit unfair on Henri Cohen :-)

It sure helps to be able to pull down

a powerful continued fraction routine from Bordeaux..

The ironical thing was that I had to go

back to 1950s high-school cubic-solving memories,

for the 16th-century part of the proof.

These memories were better than practically

anything on the web. There are six essentially

different cases of the reduced cubic and almost

no-one has them all carefully laid out on a webpage;

instead they give you equations that will spit

out complex nonsense for real roots,

and/or divide by zero, in some of the cases.

Finally I found a decent handling, referenced to> Birkhoff, G. and Mac Lane, S.

amid a load of otherwise misleading dross at

> A Survey of Modern Algebra,

> 5th ed. New York: Macmillan,

> pp. 90-91, 106-107, and 414-417, 1996.

http://mathworld.wolfram.com/CubicEquation.html

The rest of Eric's page is worse than useless

to a programmer, but the B+M equations were

as good as my highschool memories.

We should have more textbooks written

by true mathematicians!

David - ---mikeoakes2@... wrote:-
>Not only did he discover this currently-biggest "F-" form of prime himself,

correction [so as not to cause confusion]: that should read: "M-" form.

Mike

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

What are you waiting for, this could be your claim to fame :)

>The ironical thing was that I had to go

>back to 1950s high-school cubic-solving memories,

>for the 16th-century part of the proof.

>These memories were better than practically

>anything on the web. There are six essentially

>different cases of the reduced cubic and almost

>no-one has them all carefully laid out on a webpage;

>instead they give you equations that will spit

>out complex nonsense for real roots,

>and/or divide by zero, in some of the cases.

>

>Finally I found a decent handling, referenced to

> > Birkhoff, G. and Mac Lane, S.

> > A Survey of Modern Algebra,

> > 5th ed. New York: Macmillan,

> > pp. 90-91, 106-107, and 414-417, 1996.

>amid a load of otherwise misleading dross at

>http://mathworld.wolfram.com/CubicEquation.html

>The rest of Eric's page is worse than useless

>to a programmer, but the B+M equations were

>as good as my highschool memories.

>We should have more textbooks written

>by true mathematicians!

>

>David

>

>

>

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

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

>

>

>

>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/