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

Re: double frobenius with gcds

Expand Messages
  • 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 1 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 2 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 3 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 4 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.