- --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>

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.

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

>

Jon Grantham, in his paper Frobenius Pseudoprimes, calls this sort of test "Extra strong", which is a bit confusing. I am thinking of strength in terms of the jacobi symbol being -1 and the selfridge-lucas sense. Should I call it "Extra strong strong"?

Paul - On Mon, 02 May 2011 13:24:56 -0000, "paulunderwooduk"

<paulunderwood@...> wrote:> Jon Grantham, in his paper Frobenius Pseudoprimes, calls this sort of

I imagine that it's the moment when you require a number-based

> test "Extra strong", which is a bit confusing. I am thinking of

> strength in terms of the jacobi symbol being -1 and the

> selfridge-lucas sense. Should I call it "Extra strong strong"?

measurement

of strength, the kind with a stable base unit, like the Richter scale

:-)

> Paul

YG

- --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>

This extra step is trivial: The trace the square root, where it exists, of a -I is always zero regardless of primality.

>

>

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

>

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 - --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>

It is an interesting fact that:

>

>

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

>

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 - --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>

Further, if kronecker(-3,n)==-1, this can be reduced to 3 selfridges by dropping the Mod(7,n)^n==7 test because the composite test is based

>

>

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

>

a-2==-1 and a+2==3.

All in this thread will be added to the next release of my paper. I am still testing the ideas for small n, n<10^8,

Paul