22707Re: stronger than BPSW?
- Apr 30, 2011--- In firstname.lastname@example.org, "paulunderwooduk" <paulunderwood@...> wrote:
>I should have said the matrices are equivalent mod n.
> 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?
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?
- << Previous post in topic Next post in topic >>