Browse Groups

• 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
Message 1 of 5 , May 10, 2002
View Source
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.

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:- ... Flattered as I am to be included in the credits by David, the fact is that I did little more than put the idea into his head, by asking for
Message 2 of 5 , May 10, 2002
View Source
David wrote:-
> Mike Oakes and I have a
> Konyagin-Pomerance proof
> at 28892 decimal digits.

Flattered as I am to be included in the credits by David, the fact is that I
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]
• ... 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
Message 3 of 5 , May 10, 2002
View Source
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.
> 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
• ... correction [so as not to cause confusion]: that should read: M- form. Mike [Non-text portions of this message have been removed]
Message 4 of 5 , May 11, 2002
View Source
---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 :)
Message 5 of 5 , May 11, 2002
View Source
>
>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.
>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
>
>

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

>
>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/
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.
SID:YHOO:groups.yahoo.com:bRpXKTuVRy2FlLci0nFDkw==