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

Re: A derived 5 selfridge test

Expand Messages
  • Paul Underwood
    This is a follow-up, but taking y=x+2. Redefine: x=a-1 y=a+1 where a is the mean of x and y . Redefine the matrices: X=[a-1,-1;1,0] Y=[a+1,-1;1,0] and
    Message 1 of 4 , Jun 9, 2009
      This is a follow-up, but taking y=x+2. Redefine:

      x=a-1
      y=a+1

      where "a" is the mean of "x" and "y".

      Redefine the matrices:

      X=[a-1,-1;1,0]
      Y=[a+1,-1;1,0]

      and

      L(X)=X-x
      L(Y)=Y-y

      The composite test is to choose any "a" such that jacobi(D,n)==-1 for both:

      D(X)=(a-1)^2-4
      D(Y)=(a+1)^2-4

      and check:

      2^n==2 (mod n)
      X^n==1/X (mod n)
      Y^n==1/Y (mod n)

      This will satisfy:

      X^n-L(X)^n+2^n==Y^n-L(Y)^n (mod n)

      I also need to do two gcd tests. The first is gcd(210,n), to cover N. The second is with "a" because if gcd(a,n)==d with d>1, then:

      X==[-1,-1;1,0] (mod d)
      Y==[+1,-1;1,0] (mod d)

      and so the exponent tests on X and Y would be identical due to symmetry, breaking the "5-selfridge rule".

      Note that "x" is a zero of D(Y) and "y" is a zero of D(X).

      I plan to run some tests on Richard Pinch's readily available list of fermat 2-PSPs, checking the composite test by the gcd tests and two lucas V sequences -- the traces of the matrices.

      Paul

      ps. apologies for not saying quadratic non-residue instead of non quadratic residue.
    Your message has been successfully submitted and would be delivered to recipients shortly.