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

Re: single frobenius and double fermat

Expand Messages
  • paulunderwooduk
    ... Of course x could be 1. So the fermat tests should be: (x-1)^n==x-1 (mod n) (x+1)^n==x+1 (mod n) And the light of n=513629;x=128921 I am adding the
    Message 1 of 24 , Dec 5, 2012
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
      >
      > For odd n find x:
      > gcd(x,n)==1
      > kronecker(x^2-4,n)==-1
      >
      > and perform these sub-tests:
      > (x-1)^(n-1)==1 (mod n)
      > (x+1)^(n-1)==1 (mod n)
      > (L^2-1)^(n+1)==4-x^2 (mod n, L^2-x*L+1)
      >

      Of course x could be 1. So the fermat tests should be:
      (x-1)^n==x-1 (mod n)
      (x+1)^n==x+1 (mod n)

      And the light of n=513629;x=128921 I am adding the wriggle:
      gcd(x^3-x,n)==1

      Paul
    • paulunderwooduk
      ... I have found counterexamples in David s lists: ? {tstfile( underw65.txt );} 8120/12846 counterexamples left in underw65.txt ?
      Message 2 of 24 , Dec 8, 2012
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        >
        >
        >
        > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
        > >
        > > For odd n find x:
        > > gcd(x,n)==1
        > > kronecker(x^2-4,n)==-1
        > >
        > > and perform these sub-tests:
        > > (x-1)^(n-1)==1 (mod n)
        > > (x+1)^(n-1)==1 (mod n)
        > > (L^2-1)^(n+1)==4-x^2 (mod n, L^2-x*L+1)
        > >
        >
        > Of course x could be 1. So the fermat tests should be:
        > (x-1)^n==x-1 (mod n)
        > (x+1)^n==x+1 (mod n)
        >
        > And the light of n=513629;x=128921 I am adding the wriggle:
        > gcd(x^3-x,n)==1
        >

        I have found counterexamples in David's lists:

        ? {tstfile("underw65.txt");}
        8120/12846 counterexamples left in underw65.txt
        ? {tstfile("underw65x.txt");}
        10021/10220 counterexamples left in underw65x.txt

        Paul
      • paulunderwooduk
        Hi, here yet another composite test for a counterexample challenge, For n co-prime to 30 find x: gcd(x^3-x,n)==1 kronecker(x^2-4,n)==-1 and perform these
        Message 3 of 24 , Dec 8, 2012
          Hi,

          here yet another composite test for a counterexample challenge,

          For n co-prime to 30 find x:
          gcd(x^3-x,n)==1
          kronecker(x^2-4,n)==-1

          and perform these sub-tests:
          (x-2)^(n-1)==1 (mod n)
          (x+2)^(n-1)==1 (mod n)
          (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)

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

          Paul
        • paulunderwooduk
          ... n=396271;x=5042 is counterexample. I am now testing with the added wriggle: x^(n-1)==1 (mod n) Paul
          Message 4 of 24 , Dec 9, 2012
            --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
            >
            > Hi,
            >
            > here yet another composite test for a counterexample challenge,
            >
            > For n co-prime to 30 find x:
            > gcd(x^3-x,n)==1
            > kronecker(x^2-4,n)==-1
            >
            > and perform these sub-tests:
            > (x-2)^(n-1)==1 (mod n)
            > (x+2)^(n-1)==1 (mod n)
            > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
            >
            > Note: x*L^3+1==(x^3-x)*L-(x^2-1) (mod n, L^2-x*L+1)
            >
            n=396271;x=5042 is counterexample.

            I am now testing with the added wriggle:
            x^(n-1)==1 (mod n)

            Paul
          • paulunderwooduk
            ... I dropped the above wriggle. 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)
            Message 5 of 24 , Dec 9, 2012
              --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
              >
              >
              >
              > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
              > >
              > > Hi,
              > >
              > > here yet another composite test for a counterexample challenge,
              > >
              > > For n co-prime to 30 find x:
              > > gcd(x^3-x,n)==1
              > > kronecker(x^2-4,n)==-1
              > >
              > > and perform these sub-tests:
              > > (x-2)^(n-1)==1 (mod n)
              > > (x+2)^(n-1)==1 (mod n)
              > > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
              > >
              > > Note: x*L^3+1==(x^3-x)*L-(x^2-1) (mod n, L^2-x*L+1)
              > >
              > n=396271;x=5042 is counterexample.
              >
              > I am now testing with the added wriggle:
              > x^(n-1)==1 (mod n)
              >

              I dropped the above wriggle. 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)

              Paul
            • paulunderwooduk
              ... I edited the sign typo. Paul
              Message 6 of 24 , Dec 9, 2012
                > 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 edited the sign typo.

                Paul
              • 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 7 of 24 , Dec 9, 2012
                  --- 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 8 of 24 , Dec 10, 2012
                    --- 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 9 of 24 , Dec 10, 2012
                      --- 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 10 of 24 , Dec 10, 2012
                        > (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 11 of 24 , Dec 10, 2012
                          --- 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 12 of 24 , Dec 10, 2012
                            --- 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 13 of 24 , Dec 10, 2012
                              --- 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 14 of 24 , Dec 10, 2012
                                --- 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 15 of 24 , Dec 10, 2012
                                  --- 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 16 of 24 , Dec 11, 2012
                                    --- 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 17 of 24 , Dec 11, 2012
                                      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 18 of 24 , Dec 11, 2012
                                        --- 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 19 of 24 , Dec 11, 2012
                                          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 20 of 24 , Dec 11, 2012
                                            --- 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 21 of 24 , Dec 11, 2012
                                              --- 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 22 of 24 , Dec 11, 2012
                                                --- 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 23 of 24 , Dec 12, 2012
                                                  --- 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.