Loading ...
Sorry, an error occurred while loading the content.

stronger than BPSW?

Expand Messages
  • paulunderwooduk
    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
    • 0 Attachment
      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
    • paulunderwooduk
      ... 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
      • 0 Attachment
        --- 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
      • paulunderwooduk
        ... 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 6:24 AM
        • 0 Attachment
          --- 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
        • whygee@f-cpu.org
          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 7:20 AM
          • 0 Attachment
            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
          • paulunderwooduk
            ... 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 10:43 AM
            • 0 Attachment
              --- 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
            • paulunderwooduk
              ... 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 4:29 PM
              • 0 Attachment
                --- 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
              • paulunderwooduk
                ... 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 6:56 AM
                • 0 Attachment
                  --- 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.