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

24738Re: single frobenius and double fermat

Expand Messages
  • paulunderwooduk
    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
    • Show all 24 messages in this topic