Browse Groups

• 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
Message 1 of 7 , Apr 29, 2011
View Source
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?

Paul
• ... I should have said the matrices are equivalent mod n. Another thing I have noticed for numbers +-2 (mod 5) is the following: [3,-1;0,1]^((n+1)/2) ==
Message 2 of 7 , Apr 30, 2011
View Source
--- 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 should have said the matrices are equivalent mod n.

Another thing I have noticed for numbers +-2 (mod 5) is the following:

[3,-1;0,1]^((n+1)/2) == [-1,0;0,-1] (mod n)
[7,-1;0,1]^((n+1)/2) == [1,0;0,1] (mod n)

where n is prime.

Is this pattern of square roots -- one +I and one -I -- carried to all strong tests where the "a" differ by 4?

Paul
• ... 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. Jon Grantham, in his paper Frobenius
Message 3 of 7 , May 2, 2011
View Source
--- 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.

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 ... I imagine that it s the moment when you require a number-based measurement of strength, the kind with
Message 4 of 7 , May 2, 2011
View Source
On Mon, 02 May 2011 13:24:56 -0000, "paulunderwooduk"
<paulunderwood@...> wrote:
> 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"?

I imagine that it's the moment when you require a number-based
measurement
of strength, the kind with a stable base unit, like the Richter scale
:-)

> Paul
YG
• ... 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
Message 5 of 7 , May 3, 2011
View Source
--- 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
• ... 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:
Message 6 of 7 , May 26, 2011
View Source
--- 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
• ... 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 a-2==-1 and
Message 7 of 7 , May 31, 2011
View Source
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
>
> --- 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
>

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
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
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.