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

single frobenius and double fermat

Expand Messages
  • paulunderwooduk
    Hi, my apology to the group and especially David Broadhurst if I have presented the following composite test before. For odd n find x: gcd(x,n)==1
    Message 1 of 24 , Dec 5, 2012
    • 0 Attachment
      Hi,

      my apology to the group and especially David Broadhurst if I have presented the following composite test before.

      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)

      I would expect David capable of demolishing this test which has only one Lucas component, perhaps with the gremlins' help,

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