Loading ...
Sorry, an error occurred while loading the content.

28892-digit KP proof

Expand Messages
  • djbroadhurst
    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
    • 0 Attachment
      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();}
    • mikeoakes2@aol.com
      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
      • 0 Attachment
        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]
      • djbroadhurst
        ... 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
        • 0 Attachment
          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.
          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
        • mikeoakes2@aol.com
          ... 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
          • 0 Attachment
            ---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]
          • Markus Frind
            ... What are you waiting for, this could be your claim to fame :)
            Message 5 of 5 , May 11, 2002
            • 0 Attachment
              >
              >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
              >
              >

              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.