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

Re: A derived 5 selfridge test

Expand Messages
  • Paul Underwood
    Message 1 of 4 , Jun 9, 2009
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "Paul Underwood" <paulunderwood@...> wrote:
      >
      > --- In primenumbers@yahoogroups.com, "Paul Underwood" <paulunderwood@> wrote:
      >
      > As usual, a few typos:
      > I meant of course discriminant where I wrote determinant.
      > I wrote L(Y)-L(X) whereas I should have written L(X)-L(Y)
      > and
      >
      > > Fortunately for computation speed, jacobi(D(X),n)==-1 implies "X" is a NQR.
      >
      > should read "...implies "D(X)" is a NQR."
      >
      > Paul
      >
      > > I will here derive a 5-selfridge composite test from another 6-selfridge one. Whether any are proper primailty tests is yet unknown. I will endeavour to use capital letters to represent 2-by-2 matrices and lower case letters for scalars. Note that in general A*B is not the same B*A, as matrices do not always commute under multiplication.
      > >
      > > Consider the classic Fermat Probable Prime Test (PRP): x^n==x (mod n). Cleary, the same is true for the matrix:
      > >
      > > [x,0;0,x]
      > >
      > > This martix may be decomposed into:
      > >
      > > [x,-1;1,0]-[0,-1;1,-x]
      > >
      > > The two matrices in this expression behave the same under individual exponentiation if we take into account the symmetry in the postions and the signs of the elements of the matrices. Let the first matrix be:
      > >
      > > X==[x,-1;1,0]
      > >
      > > This matrix has the characteristic equation:
      > >
      > > X^2-x*X+1==0
      > >
      > > with determinant:
      > >
      > > D(X)=x^2-4
      > >
      > > For for prime, p, any non-quadratic residue (NQR) "D(X)" will map:
      > >
      > > X^n==1/X (mod p)
      > >
      > > Fortunately for computation speed, jacobi(D(X),n)==-1 implies "X" is a NQR.
      > >
      > > Note that D(X)=(x-2)*(x+2). When x is either +2 or -2 then D(X)=0. Without loss of generality assume the zero is given by x=-2. NB: there is another such characteristic equation with this zero for its determinant. It is Y^2-y*Y+1=0 with y=x+4 and therefore D(Y)=(x+2)*(x+6). The gist of the initial basic 6-selfridge test is:
      > >
      > > Find any x and y=x+4 such that D(X) and D(Y) are NQR and after check:
      > > x^n==x (mod n)
      > > y^n==y (mod n)
      > > X^n==1/X (mod n)
      > > Y^n==1/Y (mod n)
      > >
      > > (I can can quickly enumerate n<=11, and check gcd(n,15)==1 for a full cover of n \in N.)
      > >
      > > I can reduce this by 1 selfridge. Let:
      > >
      > > L(X)==X-x (mod n)
      > > L(Y)==Y-y (mod n)
      > >
      > > The new test is done by finding NQR D(X) and D(Y) with:
      > >
      > > x+4-y==0 (mod n)
      > >
      > > and checking "term-wise" the nth powers of:
      > >
      > > X+4-Y==L(Y)-L(X) (mod n)
      > >
      > > by checking individually:
      > >
      > > 4^n==4 (mod n)
      > > X^n==1/X (mod n)
      > > Y^n==1/Y (mod n)
      > >
      > > Paul^(1-eps)
      > >
      >
    • 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 2 of 4 , Jun 9, 2009
      • 0 Attachment
        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.