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

22739Re: stronger than BPSW?

Expand Messages
  • paulunderwooduk
    May 26, 2011
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
      >
      >
      >
      > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
      > >
      > >
      > >
      > > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
      > > >
      > > > Hi,
      > > >
      > > > Pari/GP implements Baillie-PSW with a strong 2-SPRP test and a strong -- where the jacobi symbol is -1 -- test on x^2-P*x-1 with minimal P.
      > > >
      > > > In my paper "quadratic composite tests", available in the files section of this group, I give another 3-selfridge test based on a strong a-SPRP test and a strong lucas test on x^2-a*x+1 with minimal a.
      > > >
      > > > In a way my test is stronger in that writing n+1 as 2^s*d, I can say
      > > >
      > > > V(a,1,<(n+1)/(2^r)-1,<(n+1)/(2^r)>) is either <a,2> for r=s; or is <-a,-2> for some r: 0<r<=s
      > > >
      > > > In matrix terms I am taking the successive square roots of
      > > >
      > > > [a,-1;1,0]^(n+1) == [1,0;0,1] (for a prime)
      > > >
      > > > Neat, eh?
      > > >
      > >
      > > I can go one step further: The trace of the square root of a [-1,0;0,-1], where it exists, is 0 (mod n) for prime n.
      > >
      >
      > This extra step is trivial: The trace the square root, where it exists, of a -I is always zero regardless of primality.
      >
      > One more thing I have noticed for primes +-2 (mod 5) and of the form 4*N+3 is:
      >
      > [3,-1;1,0]^(n+1)/2) == [-1,0;0,-1] (mod n)
      > [7,-1;1,0]^(n+1)/4) == [-1,0;0,-1] (mod n)
      >

      It is an interesting fact that:

      trace( [3,-1;1,0]^(2*N) ) = trace( [7,-1;1,0]^N )

      If, for my 6 selfridge test for {a-2;a+2}, I first find:

      Mod([3,-1;1,0],n)^(n+1)==I

      I can immediately deduce Mod([7,-1;1,0],n)^((n+1)/2) is also I. This deduction can be made since the traces are the same and the determinants are all 1, and remembering that gcd(30,n)==1. If:

      Mod([7,-1;1,0],n)^((n+1)/2) = [r,-s;s,-r+2] (for the trace condition) then the determinant is -r^2+2*r+s^2==1. Rearranging terms:

      r-1 == +-s

      Mod([7,-1;1,0],n)^((n+1)/2+1) = [7*r-s,-7*s+r-2;r,-s]

      The "non-trace" diagonal always sums to zero:

      -7*s+2*(r-1)==0 (mod n)

      Substituting:

      -7*s+-2*s == 0 (mod n)

      but gcd(30,n)==1. So s is 0 and consequently r is 1.

      So a 4-selfridge (PRP) test follows for numbers +-2 (mod 5)

      (i) gcd(30,n)==1
      (ii) Mod(3,n)^n==3
      (iii) Mod(7,n)^n==7
      (iv) Mod([3,-1;1,0],n)^(n+1)==1 (*)

      As David has pointed out, (*) can be more quickly calculated as:

      Mod(Mod(1,n)*l,l^2-3*l+1)^(n+1)==1

      Paul
    • Show all 7 messages in this topic