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

24525Re: 1+1+1+2 selfridge composite test and a question

Expand Messages
  • paulunderwooduk
    Oct 4, 2012
    • 0 Attachment
      >
      > The characteristic equation of [x+2,-2;2,-x+2]
      > is L^2-4*L-x^2+8==0
      >
      > Let
      > P=4
      > Q=-(x^2-8)
      >
      > > Then
      > > v=P^2/Q-2 == -2*x^2/(x^2-8)
      > >
      > > For this new test of odd n, find x such that:
      > > gcd(x,n)==1
      > > gcd(x^2-8,n)==1
      > > kronecker(x^2-4)==-1
      > >
      > > and perform the sub-tests:
      > > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
      > > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
      > > x^(n-1)==1 (mod n)
      > > L^(n+1)==1 (mod n, L^2-v*L+1)
      > >
      > > I am testing all x against psp-2 n below 2^32.
      > >
      >
      > The gremlins score another goal with their counterexample:
      > n==741470549 and x==68216238.
      >

      I noticed:
      x^((n-1)/2)==593203119 (mod n)
      L^((n+1)/2)==593203119 (mod n)

      This got me thinking again...

      kronecker(v^2-4,n)
      ==kronecker((4*x^4-4*(-x^2+8)^2)/(-x^2+8)^2,n)
      ==kronecker(4*x^4-4*(x^4-16*(x^2-4)),n)
      ==kronecker(x^2-4,n)
      ==-1

      Hence L^((n+1)/2)==kronecker(v+2,n) (mod n, L^2-v*L+1)

      kronecker(v+2,n)
      ==kronecker(P^2/Q,n)
      ==kronecker(Q,n)

      Thus the Lucas test now becomes
      L^((n+1)/2)==kronecker(-x^2+8,n)

      I will continue testing psp-2s :-)

      Paul
    • Show all 14 messages in this topic