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

24818Re: mod quartic composite tests

Expand Messages
  • paulunderwooduk
    Jan 15, 2013
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

      > {tst(n,x)=kronecker(x^2-4,n)==-1&&
      > gcd(x^3-x,n)==1&&
      > gcd(x^2-2,n)==1&&
      > gcd(x^2-3,n)==1&&
      > Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-2;}

      n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,n)==2672279.

      Since gcd(x^3-x,n)==1 is required I do not have to verify numbers divisible by 2 or 3, and with kronecker(x^2-4,n)==-1, I do not have to verify numbers divisible by 5. Also the squares modulo 7 are 0, 1, 4, and 2, and because I am checking gcd(x^3-x,n)==1, kronecker(x^2-4,n)==-1 and gcd(x^2-2,n)==1, I can skip numbers divisible by 7. All in all, I need only verify numbers co-prime to 210,

    • Show all 26 messages in this topic