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

24706double frobenius with gcds

Expand Messages
  • paulunderwooduk
    Dec 2, 2012
      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
    • Show all 8 messages in this topic