Browse Groups

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