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

Fermat+Euler+Fobenius

Expand Messages
  • paulunderwooduk
    Hi. Let M=[x,-1;1,0], which is the companion matrix of L^2-x*L+1. The characteristic equations of M+Id*a and M-Id*a, where Id is the 2x2 identity matrix, are:
    Message 1 of 24 , Jul 15 6:54 AM
    • 0 Attachment
      Hi.

      Let M=[x,-1;1,0], which is the companion matrix of L^2-x*L+1.

      The characteristic equations of M+Id*a and M-Id*a, where Id is the 2x2 identity matrix, are:
      L^2-(x+2*a)*L+1+a^2+a*x==0
      L^2-(x-2*a)*L+1+a^2-a*x==0

      Let x=2*a.

      Then the characteristic equations become:
      L^2-4*a*L+3*a^2+1==0
      L^2-(a^2-1)==0

      Let D=x^2-4==4*(a^2-1).

      Define the composite test for odd, non-square n, coprime to 3 and any suitable a:
      kronecker(a^2-1,n)==-1
      gcd(a,n)==1

      and do sub-tests:
      (a^2-1)^((n-1)/2)==-1 (mod n)
      (a^2-9)^(n-1)==1 (mod n)
      (L+a)^(n+1)==3*a^2+1 (mod n, L^2-2*a*L+1)

      In pari-speak:
      {tst(n,a)=kronecker(a^2-1,n)==-1&&
      gcd(a,n)==1&&
      Mod(a^2-1,n)^((n-1)/2)==-1&&
      Mod(a^2-9,n)^(n-1)==1&&
      Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

      I have currently searched Richard Pinch's list of Carmichael Numbers where n<=241242001 and for all n<1870001 (both with all possible a) without counterexamples to this composite test. However, since this test has only one Lucas Sequence component, I expect the Gremlins to be able to find a counterexample :-)

      I am running a hack of David's script:

      {tst(n,x)=kronecker((x)^2-1,n)==-1&&gcd(x,n)==1&&
      Mod(x^2-9,n)^(n-1)==1&&
      Mod(x^2-1,n)^((n-1)/2)==-1&&
      Mod(Mod(1,n)*(L+x),L^2-(2*x)*L+1)^(n+1)==3*x^2+1;}

      {tst1(p,q)=local(n=p*q,u=[]);
      for(a=3,p-3,if((n%(p-1)==1||(Mod(a^2-9,p)^(n-1)==1&&
      Mod(a^2-1,p)^(n-1)==1))&&
      Mod(Mod(1,p)*(L+a),L^2-(2*a)*L+1)^(n+1)==3*a^2+1,
      u=concat(u,a)));Mod(u,p);}

      {tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
      up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
      for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
      if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
      if(#V,print([n,V[1]]));V;}

      {forprime(p=7,40000,for(k=4,12,q=1+2*k*(p-1);
      if(ispseudoprime(q),tst2(p,q))));
      print("\\\\ "round(gettime/1000)" seconds");}

      Is it sane?

      I have also checked under* from http://physics.open.ac.uk/~dbroadhu/cert/ with another hack of one of David's scripts:

      {tst(n,x)=kronecker(x^2-1,n)==-1&&
      gcd(x,n)==1&&
      Mod(x^2-1,n)^((n-1)/2)==-1&&
      Mod(x^2-9,n)^(n-1)==1&&
      Mod(Mod(1,n)*(L+x),L^2-2*x*L+1)^(n+1)==3*x^2+1));}

      {tstfile(file)=local(c,n,x,v=readvec(file));
      for(k=1,#v,n=v[k][1];x=v[k][2];
      if(tst(n,x)&&!isprime(n),c++));
      print(c"/"#v" counterexamples left in "file);c;}

      {tstfile("underbh4.txt");}
      {tstfile("underbh6.txt");}
      {tstfile("underw97.txt");}
      {tstfile("underw297.txt");}
      {tstfile("underw65.txt");}
      {tstfile("underw65x.txt");}
      {tstfile("underwg.txt");}
      {tstfile("underwqd.txt");}

      Paul
    • paulunderwooduk
      Sorry about the typo in the title!
      Message 2 of 24 , Jul 15 7:06 AM
      • 0 Attachment
        'Sorry about the typo in the title!

        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        >
        > Hi.
        >
        > Let M=[x,-1;1,0], which is the companion matrix of L^2-x*L+1.
        >
        > The characteristic equations of M+Id*a and M-Id*a, where Id is the 2x2 identity matrix, are:
        > L^2-(x+2*a)*L+1+a^2+a*x==0
        > L^2-(x-2*a)*L+1+a^2-a*x==0
        >
        > Let x=2*a.
        >
        > Then the characteristic equations become:
        > L^2-4*a*L+3*a^2+1==0
        > L^2-(a^2-1)==0
        >
        > Let D=x^2-4==4*(a^2-1).
        >
        > Define the composite test for odd, non-square n, coprime to 3 and any suitable a:
        > kronecker(a^2-1,n)==-1
        > gcd(a,n)==1
        >
        > and do sub-tests:
        > (a^2-1)^((n-1)/2)==-1 (mod n)
        > (a^2-9)^(n-1)==1 (mod n)
        > (L+a)^(n+1)==3*a^2+1 (mod n, L^2-2*a*L+1)
        >
        > In pari-speak:
        > {tst(n,a)=kronecker(a^2-1,n)==-1&&
        > gcd(a,n)==1&&
        > Mod(a^2-1,n)^((n-1)/2)==-1&&
        > Mod(a^2-9,n)^(n-1)==1&&
        > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
        >
        > I have currently searched Richard Pinch's list of Carmichael Numbers where n<=241242001 and for all n<1870001 (both with all possible a) without counterexamples to this composite test. However, since this test has only one Lucas Sequence component, I expect the Gremlins to be able to find a counterexample :-)
        >
        > I am running a hack of David's script:
        >
        > {tst(n,x)=kronecker((x)^2-1,n)==-1&&gcd(x,n)==1&&
        > Mod(x^2-9,n)^(n-1)==1&&
        > Mod(x^2-1,n)^((n-1)/2)==-1&&
        > Mod(Mod(1,n)*(L+x),L^2-(2*x)*L+1)^(n+1)==3*x^2+1;}
        >
        > {tst1(p,q)=local(n=p*q,u=[]);
        > for(a=3,p-3,if((n%(p-1)==1||(Mod(a^2-9,p)^(n-1)==1&&
        > Mod(a^2-1,p)^(n-1)==1))&&
        > Mod(Mod(1,p)*(L+a),L^2-(2*a)*L+1)^(n+1)==3*a^2+1,
        > u=concat(u,a)));Mod(u,p);}
        >
        > {tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
        > up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
        > for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
        > if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
        > if(#V,print([n,V[1]]));V;}
        >
        > {forprime(p=7,40000,for(k=4,12,q=1+2*k*(p-1);
        > if(ispseudoprime(q),tst2(p,q))));
        > print("\\\\ "round(gettime/1000)" seconds");}
        >
        > Is it sane?
        >
        > I have also checked under* from http://physics.open.ac.uk/~dbroadhu/cert/ with another hack of one of David's scripts:
        >
        > {tst(n,x)=kronecker(x^2-1,n)==-1&&
        > gcd(x,n)==1&&
        > Mod(x^2-1,n)^((n-1)/2)==-1&&
        > Mod(x^2-9,n)^(n-1)==1&&
        > Mod(Mod(1,n)*(L+x),L^2-2*x*L+1)^(n+1)==3*x^2+1));}
        >
        > {tstfile(file)=local(c,n,x,v=readvec(file));
        > for(k=1,#v,n=v[k][1];x=v[k][2];
        > if(tst(n,x)&&!isprime(n),c++));
        > print(c"/"#v" counterexamples left in "file);c;}
        >
        > {tstfile("underbh4.txt");}
        > {tstfile("underbh6.txt");}
        > {tstfile("underw97.txt");}
        > {tstfile("underw297.txt");}
        > {tstfile("underw65.txt");}
        > {tstfile("underw65x.txt");}
        > {tstfile("underwg.txt");}
        > {tstfile("underwqd.txt");}
        >
        > Paul
        >
      • djbroadhurst
        ... {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&& Mod(a^2-1,n)^((n-1)/2)==-1&&Mod(a^2-9,n)^(n-1)==1&& Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
        Message 3 of 24 , Jul 15 6:13 PM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

          > In pari-speak:
          > {tst(n,a)=kronecker(a^2-1,n)==-1&&
          > gcd(a,n)==1&&
          > Mod(a^2-1,n)^((n-1)/2)==-1&&
          > Mod(a^2-9,n)^(n-1)==1&&
          > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

          {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
          Mod(a^2-1,n)^((n-1)/2)==-1&&Mod(a^2-9,n)^(n-1)==1&&
          Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

          {n=18716367291828127605803202146374280131174122610218950329243\
          75370060752249858742800088185928944839179221397424300401208101;

          a=46354990728672473357718750501279519419666866604904480070651\
          7441641353515300610340484778232167914470462548902372399325637;

          if(tst(n,a)&&!isprime(n),print(" Gremlins are happy"));}

          Gremlins are happy

          David (their minder)
        • paulunderwooduk
          ... Thanks very much for the counterexample! I was unhappy about the way the base x^2-9 Fermat PRP test was bolted on. I have revised the test, splitting a^2-1
          Message 4 of 24 , Jul 17 2:18 AM
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
            >
            >
            >
            > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
            >
            > > In pari-speak:
            > > {tst(n,a)=kronecker(a^2-1,n)==-1&&
            > > gcd(a,n)==1&&
            > > Mod(a^2-1,n)^((n-1)/2)==-1&&
            > > Mod(a^2-9,n)^(n-1)==1&&
            > > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
            >
            > {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
            > Mod(a^2-1,n)^((n-1)/2)==-1&&Mod(a^2-9,n)^(n-1)==1&&
            > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
            >
            > {n=18716367291828127605803202146374280131174122610218950329243\
            > 75370060752249858742800088185928944839179221397424300401208101;
            >
            > a=46354990728672473357718750501279519419666866604904480070651\
            > 7441641353515300610340484778232167914470462548902372399325637;
            >
            > if(tst(n,a)&&!isprime(n),print(" Gremlins are happy"));}
            >
            > Gremlins are happy
            >

            Thanks very much for the counterexample!

            I was unhappy about the way the base x^2-9 Fermat PRP test was bolted on. I have revised the test, splitting a^2-1 into two Euler PRP tests, and taking a base a Fermat PRP test:

            {tst(n,a)=kronecker(a^2-1,n)==-1&&
            gcd(a,n)==1&&
            Mod(a,n)^(n-1)==1&&
            Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
            Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
            Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

            Again, the Gremlins should be able to dispatch it with a counterexample,

            Paul
          • djbroadhurst
            ... {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&& Mod(a,n)^(n-1)==1&& Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&& Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
            Message 5 of 24 , Jul 17 4:26 AM
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

              > I have revised the test, splitting a^2-1 into
              > two Euler PRP tests, and taking a base a Fermat PRP test

              {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
              Mod(a,n)^(n-1)==1&&
              Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
              Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
              Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

              {n=31697716280285842787610420513509511868804379491893713448780\
              6358754802735691573982500580207945833235746240642215059880131;

              a=40853822175568028716278531675520419155854660549527670445689\
              819017030971582165228461513744662732756872644954382722169002;

              if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}

              Gremlins are still happy

              David (their minder)
            • paulunderwooduk
              ... Thanks for a quick counterexample. I am clutching at straws, but I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1. I am trying to figure out how to
              Message 6 of 24 , Jul 17 4:45 AM
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                >
                >
                >
                > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
                >
                > > I have revised the test, splitting a^2-1 into
                > > two Euler PRP tests, and taking a base a Fermat PRP test
                >
                > {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
                > Mod(a,n)^(n-1)==1&&
                > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
                >
                > {n=31697716280285842787610420513509511868804379491893713448780\
                > 6358754802735691573982500580207945833235746240642215059880131;
                >
                > a=40853822175568028716278531675520419155854660549527670445689\
                > 819017030971582165228461513744662732756872644954382722169002;
                >
                > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
                >
                > Gremlins are still happy
                >

                Thanks for a quick counterexample.

                I am clutching at straws, but I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1.

                I am trying to figure out how to strengthen the Frobenius PRP test...

                Paul
              • djbroadhurst
                ... Your latest wriggle is easily countered: {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&& Mod(a,n)^((n-1)/2)==kronecker(a,n)&& latest wriggle
                Message 7 of 24 , Jul 17 6:28 AM
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

                  > I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1.

                  Your latest wriggle is easily countered:

                  {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
                  Mod(a,n)^((n-1)/2)==kronecker(a,n)&& \\ latest wriggle
                  Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                  Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                  Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

                  {n=47391041614253942746775474638243609594331524373222569350310\
                  52914770672055547658535429075770110985428014024530096070179809;

                  a=23229351387100192392009446875150639001986809695144905977925\
                  121834927356460863740859375485138643249550235752142747141519;

                  if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}

                  Gremlins are still happy

                  David (their minder)
                • paulunderwooduk
                  ... Thanks very much. Transforming the Frobenius PRP test into Euler+Lucas: Mod(3*a^2+1,n)^((n-1)/2)==kronecker(3*a^2+1,n)&&
                  Message 8 of 24 , Jul 17 7:06 AM
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                    >
                    >
                    >
                    > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
                    >
                    > > I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1.
                    >
                    > Your latest wriggle is easily countered:
                    >
                    > {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
                    > Mod(a,n)^((n-1)/2)==kronecker(a,n)&& \\ latest wriggle
                    > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                    > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                    > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
                    >
                    > {n=47391041614253942746775474638243609594331524373222569350310\
                    > 52914770672055547658535429075770110985428014024530096070179809;
                    >
                    > a=23229351387100192392009446875150639001986809695144905977925\
                    > 121834927356460863740859375485138643249550235752142747141519;
                    >
                    > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
                    >
                    > Gremlins are still happy
                    >

                    Thanks very much.

                    Transforming the Frobenius PRP test into Euler+Lucas:

                    Mod(3*a^2+1,n)^((n-1)/2)==kronecker(3*a^2+1,n)&&
                    Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2)==kronecker(3*a^2+1,n)

                    I notice that for your counterexample (and the one before it):
                    gcd((13*a^2-1)*(7*a^2-3),n)>1,

                    Are the Gremlins now trapped?

                    Paul
                  • paulunderwooduk
                    ... I should have stipulated that gcd(3*x^2+1,n)==1 for the it s inversion. Also, in order to stop any more cyclotomic shenanigans, gcd(10*x^2-2,n)==1, Paul
                    Message 9 of 24 , Jul 17 9:29 AM
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
                      >
                      >
                      >
                      > --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@> wrote:
                      > >
                      > >
                      > >
                      > > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
                      > >
                      > > > I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1.
                      > >
                      > > Your latest wriggle is easily countered:
                      > >
                      > > {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
                      > > Mod(a,n)^((n-1)/2)==kronecker(a,n)&& \\ latest wriggle
                      > > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                      > > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                      > > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
                      > >
                      > > {n=47391041614253942746775474638243609594331524373222569350310\
                      > > 52914770672055547658535429075770110985428014024530096070179809;
                      > >
                      > > a=23229351387100192392009446875150639001986809695144905977925\
                      > > 121834927356460863740859375485138643249550235752142747141519;
                      > >
                      > > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
                      > >
                      > > Gremlins are still happy
                      > >
                      >
                      > Thanks very much.
                      >
                      > Transforming the Frobenius PRP test into Euler+Lucas:
                      >
                      > Mod(3*a^2+1,n)^((n-1)/2)==kronecker(3*a^2+1,n)&&
                      > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2)==kronecker(3*a^2+1,n)
                      >
                      > I notice that for your counterexample (and the one before it):
                      > gcd((13*a^2-1)*(7*a^2-3),n)>1,
                      >
                      > Are the Gremlins now trapped?
                      >

                      I should have stipulated that gcd(3*x^2+1,n)==1 for the it's inversion. Also, in order to stop any more cyclotomic shenanigans, gcd(10*x^2-2,n)==1,

                      Paul
                      Paul
                    • paulunderwooduk
                      ... gcd(3*a^2+1,n)==1 gcd(10*a^2-2,n)==1 I use the wrong variable. Sorry, Paul
                      Message 10 of 24 , Jul 17 9:32 AM
                      • 0 Attachment
                        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

                        > I should have stipulated that gcd(3*x^2+1,n)==1 for the it's inversion. Also, in order to stop any more cyclotomic shenanigans, gcd(10*x^2-2,n)==1,

                        gcd(3*a^2+1,n)==1
                        gcd(10*a^2-2,n)==1

                        I use the wrong variable. Sorry,

                        Paul
                      • djbroadhurst
                        ... I doubt it. But they will have to avoid linear terms in a^2. It appears that they are on strike, at present, in protest against your post-hoc wriggling,
                        Message 11 of 24 , Jul 17 11:45 AM
                        • 0 Attachment
                          --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

                          > I notice that for your counterexample (and the one before it):
                          > gcd((13*a^2-1)*(7*a^2-3),n)>1,
                          >
                          > Are the Gremlins now trapped?

                          I doubt it. But they will have to avoid linear terms in a^2.

                          It appears that they are on strike, at present, in protest
                          against your post-hoc wriggling, but I imagine that they
                          will retaliate, eventually :-)

                          David
                        • djbroadhurst
                          ... Decidedly not trapped. They now give you wriggle room, where you may invent all sorts of post-hoc evasions. Here is a counterexample to all your previous
                          Message 12 of 24 , Jul 17 5:55 PM
                          • 0 Attachment
                            --- In primenumbers@yahoogroups.com,
                            "paulunderwooduk" <paulunderwood@> wrote:

                            > Are the Gremlins now trapped?

                            Decidedly not trapped. They now give you wriggle room,
                            where you may invent all sorts of post-hoc evasions.
                            Here is a counterexample to all your previous wriggles:

                            {wriggle(a,n)=local(v=[a,3*a^2-1,5*a^2-1,13*a^2-1,3*a^2-7]);
                            sum(k=1,#v,gcd(v[k],n)>1)==0;}

                            {tst(n,a)=kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                            Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                            Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                            Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                            Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

                            {n=65886964889495717178571390281373531645585969659081927305601\
                            05227985819505433064526820837352190304323548383200875256409729;

                            a=28531673532383337956613397336948328674189469877146000735221\
                            4200436155528207860632250156996971542498419889463170302428920;

                            if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}

                            Gremlins are still happy

                            My comment: Gremlins are still being very generous; an
                            additional post-hoc wriggle, on your part, should not be
                            hard to find. Yet beware: Gremlins are cunning and if you
                            wriggle out of this counterexample, by invoking yet another
                            post-hoc gcd, they will quickly retaliate.

                            David (their minder)
                          • paulunderwooduk
                            ... Thanks again, but rules were not followed; The wriggle is slightly wrong, but the counterexample is good for the Gremlins. It should be:
                            Message 13 of 24 , Jul 18 2:29 AM
                            • 0 Attachment
                              --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                              >
                              >
                              >
                              > --- In primenumbers@yahoogroups.com,
                              > "paulunderwooduk" <paulunderwood@> wrote:
                              >
                              > > Are the Gremlins now trapped?
                              >
                              > Decidedly not trapped. They now give you wriggle room,
                              > where you may invent all sorts of post-hoc evasions.
                              > Here is a counterexample to all your previous wriggles:
                              >
                              > {wriggle(a,n)=local(v=[a,3*a^2-1,5*a^2-1,13*a^2-1,3*a^2-7]);
                              > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                              >
                              > {tst(n,a)=kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                              > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                              > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                              > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                              > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
                              >
                              > {n=65886964889495717178571390281373531645585969659081927305601\
                              > 05227985819505433064526820837352190304323548383200875256409729;
                              >
                              > a=28531673532383337956613397336948328674189469877146000735221\
                              > 4200436155528207860632250156996971542498419889463170302428920;
                              >
                              > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
                              >
                              > Gremlins are still happy
                              >
                              > My comment: Gremlins are still being very generous; an
                              > additional post-hoc wriggle, on your part, should not be
                              > hard to find. Yet beware: Gremlins are cunning and if you
                              > wriggle out of this counterexample, by invoking yet another
                              > post-hoc gcd, they will quickly retaliate.
                              >

                              Thanks again, but rules were not followed; The wriggle is slightly wrong, but the counterexample is good for the Gremlins. It should be:

                              {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                              sum(k=1,#v,gcd(v[k],n)>1)==0;}

                              The main test should have the Euler+Lucas instead of Frobenius, but I made an error in previous code. Thanks for correcting that. Now I notice that for the most recent counterexample:
                              Mod((3*a^2+1),n)^((n-1)/2) is neither 1 nor -1
                              and (equally?)
                              Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2) is neither 1 nor -1

                              Paul
                            • paulunderwooduk
                              David, sorry for the noise. Here is what I have in mind: {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]); sum(k=1,#v,gcd(v[k],n) 1)==0;} with
                              Message 14 of 24 , Jul 18 3:10 AM
                              • 0 Attachment
                                David, sorry for the noise. Here is what I have in mind:

                                {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                sum(k=1,#v,gcd(v[k],n)>1)==0;}

                                with

                                {tst(n,a)=kronecker(a^2-1,n)==-1&&
                                gcd(a,n)==1&&
                                Mod(a,n)^(n-1)==1&&
                                Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                Mod(3*a^2+1,n)^((n-1)/2)==kronecker(3*a^2+1,n)&&
                                Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2)==kronecker(3*a^2+1,n)
                                ;}

                                Paul
                              • paulunderwooduk
                                ... Oh dear, I meant {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&& gcd(a,n)==1&&Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                Message 15 of 24 , Jul 18 3:25 AM
                                • 0 Attachment
                                  --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
                                  >
                                  >
                                  > David, sorry for the noise. Here is what I have in mind:
                                  >
                                  > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                  > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                                  >
                                  > with
                                  >
                                  > {tst(n,a)=kronecker(a^2-1,n)==-1&&
                                  > gcd(a,n)==1&&
                                  > Mod(a,n)^(n-1)==1&&
                                  > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                  > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                  > Mod(3*a^2+1,n)^((n-1)/2)==kronecker(3*a^2+1,n)&&
                                  > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2)==kronecker(3*a^2+1,n)
                                  > ;}
                                  >

                                  Oh dear, I meant

                                  {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                  gcd(a,n)==1&&Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                  Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                  Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                  Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                  Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

                                  Paul -- suffering from error-after-posting syndrome
                                • djbroadhurst
                                  ... After tidying up your request, the Gremlims happily obliged: {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]); sum(k=1,#v,gcd(v[k],n) 1)==0;}
                                  Message 16 of 24 , Jul 18 5:10 AM
                                  • 0 Attachment
                                    --- In primenumbers@yahoogroups.com,
                                    "paulunderwooduk" <paulunderwood@...> wrote:

                                    > > David, sorry for the noise. Here is what I have in mind:
                                    > Oh dear, I meant ...
                                    > Paul -- suffering from error-after-posting syndrome

                                    After tidying up your request, the Gremlims happily obliged:

                                    {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]);
                                    sum(k=1,#v,gcd(v[k],n)>1)==0;}

                                    {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                    Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                    Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                    Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                    Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                    Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

                                    {if(tst(9526822969*133375521553,244578343630781166947),
                                    print(" Gremlins rule OK"));}

                                    Gremlins rule OK

                                    David (their minder)
                                  • paulunderwooduk
                                    ... They do indeed rule. I now present a puzzle: make all the tests strong i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas
                                    Message 17 of 24 , Jul 18 6:59 AM
                                    • 0 Attachment
                                      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                                      >
                                      >
                                      >
                                      > --- In primenumbers@yahoogroups.com,
                                      > "paulunderwooduk" <paulunderwood@> wrote:
                                      >
                                      > > > David, sorry for the noise. Here is what I have in mind:
                                      > > Oh dear, I meant ...
                                      > > Paul -- suffering from error-after-posting syndrome
                                      >
                                      > After tidying up your request, the Gremlims happily obliged:
                                      >
                                      > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]);
                                      > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                                      >
                                      > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                      > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                      > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                      > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                      > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                      > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}
                                      >
                                      > {if(tst(9526822969*133375521553,244578343630781166947),
                                      > print(" Gremlins rule OK"));}
                                      >
                                      > Gremlins rule OK
                                      >

                                      They do indeed rule. I now present a puzzle: make all the tests "strong" i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas test will be enough,

                                      With thanks,

                                      Paul
                                    • paulunderwooduk
                                      ... I mean check that square roots, where the exist, of all 1 are +-1, Paul
                                      Message 18 of 24 , Jul 18 7:09 AM
                                      • 0 Attachment
                                        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:



                                        > > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]);
                                        > > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                                        > >
                                        > > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                        > > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                        > > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                        > > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                        > > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                        > > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

                                        > I now present a puzzle: make all the tests "strong" i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas test will be enough,
                                        >

                                        I mean check that square roots, where the exist, of all 1 are +-1,

                                        Paul
                                      • djbroadhurst
                                        ... That s your job; not the Gremlins :-) To show that they can still work at 120 digits, even after all your wriggling, they invite you to find gcd s that
                                        Message 19 of 24 , Jul 18 8:06 AM
                                        • 0 Attachment
                                          --- In primenumbers@yahoogroups.com,
                                          "paulunderwooduk" <paulunderwood@...> wrote:

                                          > I now present a puzzle: make all the tests "strong"

                                          That's your job; not the Gremlins' :-)

                                          To show that they can still work at 120 digits,
                                          even after all your wriggling, they invite you to find
                                          gcd's that stop these pseudoprimes fooling your test:

                                          {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                          sum(k=1,#v,gcd(v[k],n)>1)==0;}

                                          {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                          Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                          Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                          Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                          Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                          Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

                                          {fooling=[

                                          [16212200212765236462624941301662595905969969921486185624581\
                                          42710646148264113979405459683534701445570403174269878228032843,

                                          148751952532863090430663215218366305961343757352250610518989\
                                          959178089757327365262627066765931489564753215534936293595719],

                                          [92856680188887785533016964629715768104484119019221599899820\
                                          26844918042826013874700027439880606063780672269637251932365051,

                                          246307830695230159344853971299085504661118671451065969332908\
                                          6522201134308546059459112977581864702729364124320490100075243]];

                                          for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];
                                          if(tst(n,a)&&!isprime(n),print(" Gremlins rule OK")));}

                                          Gremlins rule OK
                                          Gremlins rule OK

                                          They prefer to work around 120 digits, since then
                                          you have to be a little smarter to factor the semiprimes.
                                          I believe that Kermit will be able to factorize the two
                                          above, since he has been using other lists as practice.

                                          David
                                        • paulunderwooduk
                                          ... Well, I can t do what the Gremlins have done to refute my efforts so far, let alone to solve my own puzzle! But I will make a silver sub-puzzle by dropping
                                          Message 20 of 24 , Jul 18 10:23 AM
                                          • 0 Attachment
                                            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                                            >
                                            >
                                            >
                                            > --- In primenumbers@yahoogroups.com,
                                            > "paulunderwooduk" <paulunderwood@> wrote:
                                            >
                                            > > I now present a puzzle: make all the tests "strong"
                                            >
                                            > That's your job; not the Gremlins' :-)
                                            >

                                            Well, I can't do what the Gremlins have done to refute my efforts so far, let alone to solve my own puzzle! But I will make a silver sub-puzzle by dropping any PRP test on "a", but still insisting on strong tests for the other PRP sub-tests including the Lucas PRP test.

                                            > To show that they can still work at 120 digits,
                                            > even after all your wriggling, they invite you to find
                                            > gcd's that stop these pseudoprimes fooling your test:
                                            >

                                            I am unable to crack the gcd tricks and I am in the dark as to how Kermit factored the numbers in:
                                            http://tech.groups.yahoo.com/group/primenumbers/message/25227

                                            > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                            > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                                            >
                                            > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                            > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                            > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                            > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                            > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                            > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}
                                            >
                                            > {fooling=[
                                            >
                                            > [16212200212765236462624941301662595905969969921486185624581\
                                            > 42710646148264113979405459683534701445570403174269878228032843,
                                            >
                                            > 148751952532863090430663215218366305961343757352250610518989\
                                            > 959178089757327365262627066765931489564753215534936293595719],
                                            >
                                            > [92856680188887785533016964629715768104484119019221599899820\
                                            > 26844918042826013874700027439880606063780672269637251932365051,
                                            >
                                            > 246307830695230159344853971299085504661118671451065969332908\
                                            > 6522201134308546059459112977581864702729364124320490100075243]];
                                            >
                                            > for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];
                                            > if(tst(n,a)&&!isprime(n),print(" Gremlins rule OK")));}
                                            >
                                            > Gremlins rule OK
                                            > Gremlins rule OK
                                            >
                                            > They prefer to work around 120 digits, since then
                                            > you have to be a little smarter to factor the semiprimes.
                                            > I believe that Kermit will be able to factorize the two
                                            > above, since he has been using other lists as practice.
                                            >

                                            Paul
                                          • djbroadhurst
                                            ... When n = 3 mod 4, Euler is identical to Miller-Rabin, since (n-1)/2 is odd. Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1. Then the only
                                            Message 21 of 24 , Jul 18 12:06 PM
                                            • 0 Attachment
                                              --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

                                              > strong tests

                                              When n = 3 mod 4, Euler is identical to Miller-Rabin,
                                              since (n-1)/2 is odd.

                                              Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1.
                                              Then the only stengthening of Lucas is to show that
                                              L^((n+1)/4) (mod all that other stuff) is +1 or -1.
                                              since (n+1)/4 is odd.

                                              {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                              sum(k=1,#v,gcd(v[k],n)>1)==0;}

                                              {tst3mod8(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                              !isprime(n)&&n%8==3&&kronecker(Q,n)==1&& \\ just to keep Paul happy
                                              Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                              Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                              Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                              Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&(
                                              Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==+1||
                                              Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==-1);}

                                              {if(tst3mod8(1080534578729388602707,3487806307751356235),
                                              print(" Done!"));}

                                              Done!

                                              David
                                            • paulunderwooduk
                                              ... Wonderful! Thanks for the exposition. It is another example of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test can be counterexampled. Once
                                              Message 22 of 24 , Jul 18 12:34 PM
                                              • 0 Attachment
                                                --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                                                >
                                                >
                                                >
                                                > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
                                                >
                                                > > strong tests
                                                >
                                                > When n = 3 mod 4, Euler is identical to Miller-Rabin,
                                                > since (n-1)/2 is odd.
                                                >
                                                > Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1.
                                                > Then the only stengthening of Lucas is to show that
                                                > L^((n+1)/4) (mod all that other stuff) is +1 or -1.
                                                > since (n+1)/4 is odd.
                                                >
                                                > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                                > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                                                >
                                                > {tst3mod8(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                                > !isprime(n)&&n%8==3&&kronecker(Q,n)==1&& \\ just to keep Paul happy
                                                > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                                > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                                > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                                > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&(
                                                > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==+1||
                                                > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==-1);}
                                                >
                                                > {if(tst3mod8(1080534578729388602707,3487806307751356235),
                                                > print(" Done!"));}
                                                >
                                                > Done!
                                                >

                                                Wonderful! Thanks for the exposition. It is another example of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test can be counterexampled. Once again you and the Gremlins have rescued a core or two from inane computation,

                                                Paul
                                              • djbroadhurst
                                                ... That s what Gremlins are for. ... Here is one of many ways to evade your wriggles, which had trivial gcds. I give a pair of smarter gcds, which serve for
                                                Message 23 of 24 , Jul 19 6:35 AM
                                                • 0 Attachment
                                                  --- In primenumbers@yahoogroups.com,
                                                  "paulunderwooduk" <paulunderwood@...> wrote:

                                                  > Wonderful! Thanks for the exposition. It is another example
                                                  > of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test
                                                  > can be counterexampled.

                                                  That's what Gremlins are for.

                                                  > I am unable to crack the gcd tricks

                                                  Here is one of many ways to evade your wriggles, which had
                                                  trivial gcds. I give a pair of smarter gcds, which serve
                                                  for three small examples, But as soon as we include this trap
                                                  the Gremlins will find another smart way out.

                                                  {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                                                  sum(k=1,#v,gcd(v[k],n)>1)==0;}

                                                  {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                                                  Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                                                  Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                                                  Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                                                  Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                                                  Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

                                                  {smart(a,n)=local(v=[
                                                  581130733*a^18-1549681961*a^16+1598109492*a^14-815197364*a^12
                                                  +219605318*a^10-31108446*a^8+2189796*a^6-67524*a^4+693*a^2-1,
                                                  290565367*a^18-920123659*a^16+1150154588*a^14-728431196*a^12
                                                  +250797682*a^10-47124218*a^8+4637292*a^6-217740*a^4+4047*a^2-19]);
                                                  sum(k=1,#v,gcd(v[k],n)>1)>0;}

                                                  {fooling=[
                                                  [2972225251*112944559501,48957135643862669970],
                                                  [3047555083*115807093117,49017305561177450303],
                                                  [3130042291*118941607021,169666628495887666139]];

                                                  for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];if(tst(n,a)
                                                  &&smart(a,n),print(" fooled wriggle, trapped smartly")));}

                                                  fooled wriggle, trapped smartly
                                                  fooled wriggle, trapped smartly
                                                  fooled wriggle, trapped smartly

                                                  The derivation of the pair of polynomials, for
                                                  these particular cases, is left as an exercise.

                                                  David (spilling the Gremlins' secrets)
                                                • djbroadhurst
                                                  ... Maybe Kermit read http://selmer.warwick.ac.uk/onelinefactor.pdf {OLF(x)=;i=1;while(i
                                                  Message 24 of 24 , Jul 31 8:11 PM
                                                  • 0 Attachment
                                                    --- In primenumbers@yahoogroups.com,
                                                    "paulunderwooduk" <paulunderwood@...> wrote:

                                                    > I am in the dark as to how Kermit factored the numbers in:
                                                    > http://tech.groups.yahoo.com/group/primenumbers/message/25227

                                                    Maybe Kermit read
                                                    http://selmer.warwick.ac.uk/onelinefactor.pdf

                                                    {OLF(x)=;i=1;while(i<x,if(issquare(ceil(sqrt(i*x))^2%x),
                                                    return(gcd(x,floor(ceil(sqrt(i*x))-sqrt((ceil(sqrt(i*x))^2)%x)))));i++);}

                                                    {default(realprecision,130);gettime;
                                                    N1=16212200212765236462624941301662595905969969921486185624581
                                                    42710646148264113979405459683534701445570403174269878228032843;
                                                    N2=92856680188887785533016964629715768104484119019221599899820
                                                    26844918042826013874700027439880606063780672269637251932365051;
                                                    print(OLF(N1)" divides N1");
                                                    print(OLF(N2)" divides N2");
                                                    print("This took "gettime" millisecond(s)");}

                                                    5972172173345601078558810561451365062976970419888735246630677 divides N1
                                                    11401725845872759790535993230138294233298881744517681451802021 divides N2
                                                    This took 1 millisecond(s)

                                                    David
                                                  Your message has been successfully submitted and would be delivered to recipients shortly.