--- 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)

Paul