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

double frobenius with gcds

Expand Messages
  • paulunderwooduk
    Hi, I have a new composite test for odd n with any x and a: 2
    Message 1 of 8 , Dec 2, 2012
    • 0 Attachment
      Hi,

      I have a new composite test for odd n with any x and a:
      2<x<(n+1)/2
      1<a<(n+1)/2:
      kronecker(x^2-4,n)==-1
      gcd(a^3-a,n)==1
      gcd(a,x)==1

      with sub-tests:
      (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
      (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)

      (If x and a are small this is a 2+2 selfridge test.)

      I have done a shallow (triple loop) verification for n<4000

      Can you find a counterexample?

      a=x+1 can be verified with a double loop :-) True for n<42000

      Paul
    • djbroadhurst
      ... {tst(n,x,a)=2
      Message 2 of 8 , Dec 2, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "paulunderwooduk" <paulunderwood@...> wrote:

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

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

        {F=[[33877678503145357571, 3952030303250180277, 966200491166451083],
        [295057250504883381551, 127751371818177523954, 8822853390661898603],
        [429749641620836200211, 69208918734832269040, 200208504884456069347]];
        print(sum(k=1,#F,tst(F[k][1],F[k][2],F[k][3]))" counterexamples");}

        3 counterexamples

        David
      • paulunderwooduk
        ... I notice these 3 have kronecker(x,n)==1. So I wriggle with this test: kronecker(x^2-4,n)==-1 kronecker(x,n)==-1 gcd(a,n)==1 (L+a)^(n+1)==a*x+a^2+1 (mod n,
        Message 3 of 8 , Dec 3, 2012
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
          >
          >
          >
          > --- In primenumbers@yahoogroups.com,
          > "paulunderwooduk" <paulunderwood@> wrote:
          >
          > > 2<x<(n+1)/2
          > > 1<a<(n+1)/2:
          > > kronecker(x^2-4,n)==-1
          > > gcd(a^3-a,n)==1
          > > gcd(a,x)==1
          > > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
          > > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
          >
          > {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
          > kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
          > Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
          > Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}
          >
          > {F=[[33877678503145357571, 3952030303250180277, 966200491166451083],
          > [295057250504883381551, 127751371818177523954, 8822853390661898603],
          > [429749641620836200211, 69208918734832269040, 200208504884456069347]];
          > print(sum(k=1,#F,tst(F[k][1],F[k][2],F[k][3]))" counterexamples");}
          >
          > 3 counterexamples

          I notice these 3 have kronecker(x,n)==1. So I wriggle with this test:

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

          Putting a=1 with x small is most efficient,

          Paul
        • paulunderwooduk
          ... Last minute wriggle: gcd(a^3-a,n)==1 Paul
          Message 4 of 8 , Dec 3, 2012
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
            >
            >
            >
            > --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@> wrote:
            > >
            > >
            > >
            > > --- In primenumbers@yahoogroups.com,
            > > "paulunderwooduk" <paulunderwood@> wrote:
            > >
            > > > 2<x<(n+1)/2
            > > > 1<a<(n+1)/2:
            > > > kronecker(x^2-4,n)==-1
            > > > gcd(a^3-a,n)==1
            > > > gcd(a,x)==1
            > > > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
            > > > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
            > >
            > > {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
            > > kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
            > > Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
            > > Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}
            > >
            > > {F=[[33877678503145357571, 3952030303250180277, 966200491166451083],
            > > [295057250504883381551, 127751371818177523954, 8822853390661898603],
            > > [429749641620836200211, 69208918734832269040, 200208504884456069347]];
            > > print(sum(k=1,#F,tst(F[k][1],F[k][2],F[k][3]))" counterexamples");}
            > >
            > > 3 counterexamples
            >
            > I notice these 3 have kronecker(x,n)==1. So I wriggle with this test:
            >
            > kronecker(x^2-4,n)==-1
            > kronecker(x,n)==-1
            > gcd(a,n)==1
            > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
            > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
            >

            Last minute wriggle:
            gcd(a^3-a,n)==1

            Paul
          • paulunderwooduk
            ... n==3281 lead to the above wriggle. I could have used the following wriggle instead: gcd(x^2-1,n), which would allow a==1 Paul
            Message 5 of 8 , Dec 3, 2012
            • 0 Attachment
              > > kronecker(x^2-4,n)==-1
              > > kronecker(x,n)==-1
              > > gcd(a,n)==1
              > > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
              > > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
              > >
              >
              > Last minute wriggle:
              > gcd(a^3-a,n)==1

              n==3281 lead to the above wriggle. I could have used the following wriggle instead:

              gcd(x^2-1,n), which would allow a==1

              Paul
            • djbroadhurst
              ... {tst(n,x,a)=2
              Message 6 of 8 , Dec 3, 2012
              • 0 Attachment
                --- In primenumbers@yahoogroups.com,
                "paulunderwooduk" <paulunderwood@...> wrote:

                > I wriggle with this test:
                > kronecker(x,n)==-1

                {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
                kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
                kronecker(x,n)==-1&& \\ added wriggle
                Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
                Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}

                {if(tst(429749641620836200211,69208918734832269040,
                200208504884456069347),print("fooled"));}

                fooled

                David
              • paulunderwooduk
                ... Well done. Thanks, Paul
                Message 7 of 8 , Dec 3, 2012
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                  >
                  >
                  >
                  > --- In primenumbers@yahoogroups.com,
                  > "paulunderwooduk" <paulunderwood@> wrote:
                  >
                  > > I wriggle with this test:
                  > > kronecker(x,n)==-1
                  >
                  > {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
                  > kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
                  > kronecker(x,n)==-1&& \\ added wriggle
                  > Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
                  > Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}
                  >
                  > {if(tst(429749641620836200211,69208918734832269040,
                  > 200208504884456069347),print("fooled"));}
                  >
                  > fooled
                  >

                  Well done. Thanks,

                  Paul
                • djbroadhurst
                  ... After I worked out to how to forge one counterexample, the gremlins were able to find more than 21,000: {tst(n,x,a)=2
                  Message 8 of 8 , Dec 4, 2012
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com,
                    "paulunderwooduk" <paulunderwood@...> wrote:

                    > > {if(tst(429749641620836200211,69208918734832269040,
                    > > 200208504884456069347),print("fooled"));}
                    > > fooled
                    > Well done. Thanks

                    After I worked out to how to forge one counterexample,
                    the gremlins were able to find more than 21,000:

                    {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
                    kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
                    kronecker(x,n)==-1&& \\ added wriggle from Paul
                    Mod(2,n)^(n-1)==1&&n%12==11&& \\ by construction
                    Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
                    Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}

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

                    21728 counterexamples

                    It will be observed that, in each case, n = 11 mod 12 is a
                    base-2 Fermat pseudoprime. That was for convenience and
                    is not an intrinsic limitation.

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