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

Re: single frobenius and double fermat

Expand Messages
  • paulunderwooduk
    ... I think the frobenius sub-test can be simplified to: ((x^2-1)*L)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1) Paul
    Message 1 of 24 , Dec 9, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
      >
      >
      > > The test I am now verifying is:
      > >
      > > gcd(x^3-x,n)==1
      > > kronecker(x^2-4,n)==-1
      > > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
      > > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
      > > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
      > >
      >

      I think the frobenius sub-test can be simplified to:

      ((x^2-1)*L)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)

      Paul
    • djbroadhurst
      ... {tst(n,x)=gcd(x^3-x,n)==1&&kronecker(x^2-4,n)==-1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
      Message 2 of 24 , Dec 10, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "paulunderwooduk" <paulunderwood@...> wrote:

        > gcd(x^3-x,n)==1
        > kronecker(x^2-4,n)==-1
        > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
        > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
        > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)

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

        {v=readvec("underwg.txt");
        \\ http://physics.open.ac.uk/~dbroadhu/cert/underwg.txt.gz
        print(sum(k=1,#v,tst(v[k][1],v[k][2]))" counterexamples");}

        19959 counterexamples

        David
      • paulunderwooduk
        ... Thanks again, David. I had an mistake in one of my equations that caused erroneous checking of your files. I have another test. For small x, and choosing
        Message 3 of 24 , Dec 10, 2012
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
          >
          >
          >
          > --- In primenumbers@yahoogroups.com,
          > "paulunderwooduk" <paulunderwood@> wrote:
          >
          > > gcd(x^3-x,n)==1
          > > kronecker(x^2-4,n)==-1
          > > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
          > > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
          > > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
          >
          > {tst(n,x)=gcd(x^3-x,n)==1&&kronecker(x^2-4,n)==-1&&
          > Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
          > Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
          > Mod(Mod(1,n)*(x*L^3+1),L^2-x*L+1)^(n+1)==(x^2-1)^2;}
          >
          > {v=readvec("underwg.txt");
          > \\ http://physics.open.ac.uk/~dbroadhu/cert/underwg.txt.gz
          > print(sum(k=1,#v,tst(v[k][1],v[k][2]))" counterexamples");}
          >
          > 19959 counterexamples
          >

          Thanks again, David. I had an mistake in one of my equations that caused erroneous checking of your files.

          I have another test. For small x, and choosing where possible x==3 or x==6, the test is on average 3.25 selfridge. For n co-prime to 30 find any x:

          gcd(x^3-x,n)==1
          kronecker(x^2-4,n)==-1
          (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
          (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
          (x^3-x)*(L^2-4)^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)

          I this tested against your files:

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

          {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");}
          0/33445 counterexamples left in underbh4.txt
          ? {tstfile("underbh6.txt");}
          0/308619 counterexamples left in underbh6.txt
          ? {tstfile("underw97.txt");}
          0/97 counterexamples left in underw97.txt
          ? {tstfile("underw297.txt");}
          0/297 counterexamples left in underw297.txt
          ? {tstfile("underw65.txt");}
          0/12846 counterexamples left in underw65.txt
          ? {tstfile("underw65x.txt");}
          0/10220 counterexamples left in underw65x.txt
          ? {tstfile("underwg.txt");}
          0/100000 counterexamples left in underwg.txt

          Paul
        • paulunderwooduk
          ... should be: ((x^3-x)*(L^2-4))^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1) Paul
          Message 4 of 24 , Dec 10, 2012
          • 0 Attachment
            > (x^3-x)*(L^2-4)^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)

            should be:

            ((x^3-x)*(L^2-4))^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)

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

              > gcd(x^3-x,n)==1
              > kronecker(x^2-4,n)==-1
              > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
              > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
              > (x^3-x)*(L^2-4)^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)

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

              {if(tst(115886944289,3692152318),print("fooled"));}

              fooled

              David
            • paulunderwooduk
              ... Thanks. Here is another composite test: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&kronecker(x^2-1,n)==-1&&
              Message 6 of 24 , Dec 10, 2012
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                >
                >
                >
                > --- In primenumbers@yahoogroups.com,
                > "paulunderwooduk" <paulunderwood@> wrote:
                >
                > > gcd(x^3-x,n)==1
                > > kronecker(x^2-4,n)==-1
                > > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
                > > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
                > > (x^3-x)*(L^2-4)^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)
                >
                > {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&
                > Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
                > Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
                > Mod(Mod(1,n)*(x^3-x)*(L^2-4),L^2-x*L+1)^(n+1)==
                > (x^3-x)^2*(25-4*x^2);}
                >
                > {if(tst(115886944289,3692152318),print("fooled"));}
                >
                > fooled
                >

                Thanks. Here is another composite test:

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

                It's on average about 5 selfridge for carefully chosen x,

                Paul
              • djbroadhurst
                ... Generically, that is 7 selfridges: 4 Euler tests and one Frobenius. However, it s reasonably easy to fool:
                Message 7 of 24 , Dec 10, 2012
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com,
                  "paulunderwooduk" <paulunderwood@...> wrote:

                  > Here is another composite test
                  > It's on average about 5 selfridge

                  Generically, that is 7 selfridges: 4 Euler tests
                  and one Frobenius. However, it's reasonably easy to fool:

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

                  {if(tst(312432294658994604401,2805168083964928859),
                  print(fooled));}

                  fooled

                  David


                  > It's on average about 5 selfridge for carefully chosen x,
                  >
                  > Paul
                  >
                • paulunderwooduk
                  ... Thanks once more. Now a last ditch test: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&& kronecker(x^2-1,n)==-1&&
                  Message 8 of 24 , Dec 10, 2012
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                    >
                    > --- In primenumbers@yahoogroups.com,
                    > "paulunderwooduk" <paulunderwood@> wrote:
                    >
                    > > Here is another composite test
                    > > It's on average about 5 selfridge
                    >
                    > Generically, that is 7 selfridges: 4 Euler tests
                    > and one Frobenius. However, it's reasonably easy to fool:
                    >
                    > {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&
                    > kronecker(x^2-1,n)==-1&&
                    > Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
                    > Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
                    > Mod(x-1,n)^((n-1)/2)==kronecker(x-1,n)&&
                    > Mod(x+1,n)^((n-1)/2)==kronecker(x+1,n)&&
                    > Mod(Mod(1,n)*x*(L^2-4),L^2-x*L+1)^(n+1)==x^2*(25-4*x^2);}
                    >
                    > {if(tst(312432294658994604401,2805168083964928859),
                    > print(fooled));}
                    >
                    > fooled
                    >

                    Thanks once more. Now a last ditch test:

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

                    Paul
                  • djbroadhurst
                    ... That s 5 + 3 = 8 selfrideges, but still easy to fool: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&& kronecker(x^2-1,n)==-1&&
                    Message 9 of 24 , Dec 10, 2012
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com,
                      "paulunderwooduk" <paulunderwood@...> wrote:

                      > Now a last ditch test

                      That's 5 + 3 = 8 selfrideges, but still easy to fool:

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

                      {if(tst(28928708996670209,9176237087918226),
                      print(fooled));}
                    • djbroadhurst
                      ... Moreover, we may allow 7 Euler tests before the Frobenius test and still obtain a counterexample: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&
                      Message 10 of 24 , Dec 11, 2012
                      • 0 Attachment
                        --- In primenumbers@yahoogroups.com,
                        "djbroadhurst" <d.broadhurst@...> wrote:

                        > > Now a last ditch test
                        > That's 5 + 3 = 8 selfridges, but still easy to fool

                        Moreover, we may allow 7 Euler tests before the
                        Frobenius test and still obtain a counterexample:

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

                        {if(tst(500813768599682335601,104655233442347018047),
                        print(fooled));}

                        fooled

                        David
                      • paulunderwooduk
                        I have another new composite test for odd n: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
                        Message 11 of 24 , Dec 11, 2012
                        • 0 Attachment
                          I have another new composite test for odd n:

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

                          Since for x==1,3 or 6 it is 3 selfridge, a single test with carefully chosen small x is on average 3.125 selfridge,

                          Paul
                        • djbroadhurst
                          ... {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
                          Message 12 of 24 , Dec 11, 2012
                          • 0 Attachment
                            --- In primenumbers@yahoogroups.com,
                            "paulunderwooduk" <paulunderwood@...> wrote:

                            > I have another new composite test

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

                            {quote=" Vain are the thousand creeds that move men's hearts,
                            unutterably vain, worthless as wither'd weeds.";
                            if(tst(10538495213,2237176843),print(quote));}

                            Vain are the thousand creeds that move men's hearts,
                            unutterably vain, worthless as wither'd weeds.

                            David (per proxy Emily)
                          • paulunderwooduk
                            Here yet another new composite test. This time there is a sneaky use of 2: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
                            Message 13 of 24 , Dec 11, 2012
                            • 0 Attachment
                              Here yet another new composite test. This time there is a sneaky use of 2:

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

                              Paul
                            • djbroadhurst
                              ... But still easy to fool: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
                              Message 14 of 24 , Dec 11, 2012
                              • 0 Attachment
                                --- In primenumbers@yahoogroups.com,
                                "paulunderwooduk" <paulunderwood@...> wrote:

                                > Here yet another new composite test.
                                > This time there is a sneaky use of 2

                                But still easy to fool:

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

                                {if(tst(37423804289,10332300710),print(fooled));}

                                fooled

                                David
                              • paulunderwooduk
                                ... Thanks David. However, I am going to be even more devious with this 3.5 selfridge test for small x: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
                                Message 15 of 24 , Dec 11, 2012
                                • 0 Attachment
                                  --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:

                                  > fooled

                                  Thanks David. However, I am going to be even more devious with this 3.5 selfridge test for small x:

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

                                  Paul
                                • paulunderwooduk
                                  ... Maybe I can make this 3.125 selfridge for small x by removing the first multiplier 4 and using x=1,3 and 6 where possible Paul
                                  Message 16 of 24 , Dec 11, 2012
                                  • 0 Attachment
                                    --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
                                    >
                                    >
                                    >
                                    > --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@> wrote:
                                    >
                                    > > fooled
                                    >
                                    > Thanks David. However, I am going to be even more devious with this 3.5 selfridge test for small x:
                                    >
                                    > {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
                                    > Mod(4*(x-2),n)^((n-1)/2)==kronecker(x-2,n)&&
                                    > Mod(4*(x+2),n)^((n-1)/2)==kronecker(x+2,n)&&
                                    > Mod(Mod(1,n)*2*(L^2-4),L^2-x*L+1)^(n+1)==4*(25-4*x^2);}
                                    >

                                    Maybe I can make this 3.125 selfridge for small x by removing the first multiplier 4 and using x=1,3 and 6 where possible

                                    Paul
                                  • djbroadhurst
                                    ... Not really. Sticking in powers of 2 does not make forgery any harder. {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
                                    Message 17 of 24 , Dec 12, 2012
                                    • 0 Attachment
                                      --- In primenumbers@yahoogroups.com,
                                      "paulunderwooduk" <paulunderwood@...> wrote:

                                      > I am going to be even more devious

                                      Not really. Sticking in powers of 2 does not
                                      make forgery any harder.

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

                                      {if(tst(115886944289,3692152318),print(fooled));}

                                      fooled

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