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

1+1+2 selfridge composite test question

Expand Messages
  • paulunderwooduk
    Hi, let X=x+2 and Y=x-2 for an integer x: Let M=[X,-1;1,2] N=[Y,-1;1,-2] Form a new matrix: A=M^2-x*M+1 Then A=2*[X,-2;2,-Y]==[2*x+4,-4;4,-2*x+4] This has the
    Message 1 of 14 , Sep 29, 2012
    • 0 Attachment
      Hi,

      let X=x+2 and Y=x-2 for an integer x:

      Let
      M=[X,-1;1,2]
      N=[Y,-1;1,-2]

      Form a new matrix:
      A=M^2-x*M+1

      Then A=2*[X,-2;2,-Y]==[2*x+4,-4;4,-2*x+4]

      This has the characteristic equation:
      L^2-8*L-4*(x^2-8)==0

      Let
      P=8
      Q=-4*(x^2-8)
      R=Q/4

      Let v=P^2/Q-2==16/(-x^2+8)-2 (if gcd(Q,n)==1)

      Now form the 1+1+2 selfridge composite test for odd n with kronecker(D,n)==-1 where D=x^2-4:
      gcd(x,n)==1
      D^((n-1)/2)==-1 (mod n)
      R^((n-1)/2)==kronecker(R,n) (mod n)
      L^(n+1)==1 (mod n, L^2-v*L+1)

      Is a 2-prp test implied by this?

      Should I make the test on R "strong" with a negative kronecker symbol?

      Paul
    • paulunderwooduk
      ... I found a counterexample: n=5173601 (2-psp) and x=1630018. After a wriggle, the test becomes: kronecker(D,n)==-1 gcd(x,n)==1 X^((n-1)/2)==kronecker(X,n)
      Message 2 of 14 , Sep 29, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        >
        > Hi,
        >
        > let X=x+2 and Y=x-2 for an integer x:
        >
        > Let
        > M=[X,-1;1,2]
        > N=[Y,-1;1,-2]
        >
        > Form a new matrix:
        > A=M^2-x*M+1
        >
        > Then A=2*[X,-2;2,-Y]==[2*x+4,-4;4,-2*x+4]
        >
        > This has the characteristic equation:
        > L^2-8*L-4*(x^2-8)==0
        >
        > Let
        > P=8
        > Q=-4*(x^2-8)
        > R=Q/4
        >
        > Let v=P^2/Q-2==16/(-x^2+8)-2 (if gcd(Q,n)==1)
        >
        > Now form the 1+1+2 selfridge composite test for odd n with kronecker(D,n)==-1 where D=x^2-4:
        > gcd(x,n)==1
        > D^((n-1)/2)==-1 (mod n)
        > R^((n-1)/2)==kronecker(R,n) (mod n)
        > L^(n+1)==1 (mod n, L^2-v*L+1)
        >
        > Is a 2-prp test implied by this?
        >
        > Should I make the test on R "strong" with a negative kronecker symbol?
        >

        I found a counterexample: n=5173601 (2-psp) and x=1630018.

        After a wriggle, the test becomes:
        kronecker(D,n)==-1
        gcd(x,n)==1
        X^((n-1)/2)==kronecker(X,n)
        Y^((n-1)/2)==kronecker(Y,n)
        R^(n-1)==kronecker(R,n) (mod n)
        L^(n+1)==1 (mod n, L^2-v*L+1)

        This is 1+1+1+2 selfridges :-(

        My question remains: Is a 2-prp test implied by this?

        Paul
      • paulunderwooduk
        ... I meant: R^(n-1)==1 (mod n)
        Message 3 of 14 , Sep 29, 2012
        • 0 Attachment
          > R^(n-1)==kronecker(R,n) (mod n)

          I meant:
          R^(n-1)==1 (mod n)
        • djbroadhurst
          ... To err is human; to recant, divine. David
          Message 4 of 14 , Sep 29, 2012
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            "paulunderwooduk" <paulunderwood@...> wrote:

            > I found a counterexample...
            > After a wriggle, the test becomes...

            To err is human; to recant, divine.

            David
          • paulunderwooduk
            ... The gremlins win against the modified test; (psp-2) n=16070429 and x=6924798 is a counterexample. nuf said, Paul
            Message 5 of 14 , Sep 30, 2012
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
              >
              >
              >
              > --- In primenumbers@yahoogroups.com,
              > "paulunderwooduk" <paulunderwood@> wrote:
              >
              > > I found a counterexample...
              > > After a wriggle, the test becomes...
              >
              > To err is human; to recant, divine.
              >

              The gremlins win against the modified test; (psp-2) n=16070429 and x=6924798 is a counterexample.

              nuf said,

              Paul
            • paulunderwooduk
              ... ? n=16070429;x=6924798;R=-x^2+8;Mod(R,n)^((n-1)/2) Mod(12860271, 16070429) which is neither +-1. Maybe I should adhere to C&P 3.6.3. In the meantime I will
              Message 6 of 14 , Sep 30, 2012
              • 0 Attachment
                >
                > (psp-2) n=16070429 and x=6924798 is a counterexample.
                >

                ? n=16070429;x=6924798;R=-x^2+8;Mod(R,n)^((n-1)/2)
                Mod(12860271, 16070429)

                which is neither +-1.

                Maybe I should adhere to C&P 3.6.3.

                In the meantime I will carry on testing odd psp-2s to 2^32 -- this might help countering another test I have which has been tested for all odd n< 2.5*10^7

                Paul
              • paulunderwooduk
                Hi again, [x+2,-2;2,x-2] has the characteristic equation L^2-8*L-4*(x^2-8)==0 Let P=8 Q=-4*(x^2-8) Then v=P^2/Q-2 == -2*x^2/(x^2-8) For this new test of odd n,
                Message 7 of 14 , Sep 30, 2012
                • 0 Attachment
                  Hi again,

                  [x+2,-2;2,x-2] has the characteristic equation
                  L^2-8*L-4*(x^2-8)==0

                  Let
                  P=8
                  Q=-4*(x^2-8)

                  Then
                  v=P^2/Q-2 == -2*x^2/(x^2-8)

                  For this new test of odd n, find x such that:
                  gcd(x,n)==1
                  gcd(x^2-8,n)==1
                  kronecker(x^2-4)==-1

                  and perform the sub-tests:
                  (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
                  (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
                  x^(n-1)==1 (mod n)
                  L^(n+1)==1 (mod n, L^2-v*L+1)

                  I am testing all x against psp-2 n below 2^32.

                  Do I need to test non-psp-2s?

                  Paul
                • paulunderwooduk
                  ... The matrix should be [2*x+4,-4;4,-2*x+4] Paul
                  Message 8 of 14 , Sep 30, 2012
                  • 0 Attachment
                    > [x+2,-2;2,x-2] has the characteristic equation
                    > L^2-8*L-4*(x^2-8)==0

                    The matrix should be [2*x+4,-4;4,-2*x+4]

                    Paul
                  • paulunderwooduk
                    ... It make no difference to the test if [x+2,-2;2,-x+2] is used , with its characteristic equation L^2-4*L-(x^2-8)==0, Paul
                    Message 9 of 14 , Sep 30, 2012
                    • 0 Attachment
                      >
                      > > [x+2,-2;2,x-2] has the characteristic equation
                      > > L^2-8*L-4*(x^2-8)==0
                      >
                      > The matrix should be [2*x+4,-4;4,-2*x+4]
                      >

                      It make no difference to the test if [x+2,-2;2,-x+2] is "used", with its characteristic equation L^2-4*L-(x^2-8)==0,

                      Paul
                    • paulunderwooduk
                      The characteristic equation of [x+2,-2;2,-x+2] is L^2-4*L-x^2+8==0 Let P=4 Q=-(x^2-8) ... The gremlins score another goal with their counterexample:
                      Message 10 of 14 , Oct 4, 2012
                      • 0 Attachment
                        The characteristic equation of [x+2,-2;2,-x+2]
                        is L^2-4*L-x^2+8==0

                        Let
                        P=4
                        Q=-(x^2-8)

                        > Then
                        > v=P^2/Q-2 == -2*x^2/(x^2-8)
                        >
                        > For this new test of odd n, find x such that:
                        > gcd(x,n)==1
                        > gcd(x^2-8,n)==1
                        > kronecker(x^2-4)==-1
                        >
                        > and perform the sub-tests:
                        > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
                        > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
                        > x^(n-1)==1 (mod n)
                        > L^(n+1)==1 (mod n, L^2-v*L+1)
                        >
                        > I am testing all x against psp-2 n below 2^32.
                        >

                        The gremlins score another goal with their counterexample:
                        n==741470549 and x==68216238.

                        I refuse to take their bait of x^((n-1)/2)!=+-1 (mod n) and "recant"

                        Paul
                      • paulunderwooduk
                        ... I noticed: x^((n-1)/2)==593203119 (mod n) L^((n+1)/2)==593203119 (mod n) This got me thinking again... kronecker(v^2-4,n)
                        Message 11 of 14 , Oct 4, 2012
                        • 0 Attachment
                          >
                          > The characteristic equation of [x+2,-2;2,-x+2]
                          > is L^2-4*L-x^2+8==0
                          >
                          > Let
                          > P=4
                          > Q=-(x^2-8)
                          >
                          > > Then
                          > > v=P^2/Q-2 == -2*x^2/(x^2-8)
                          > >
                          > > For this new test of odd n, find x such that:
                          > > gcd(x,n)==1
                          > > gcd(x^2-8,n)==1
                          > > kronecker(x^2-4)==-1
                          > >
                          > > and perform the sub-tests:
                          > > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
                          > > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
                          > > x^(n-1)==1 (mod n)
                          > > L^(n+1)==1 (mod n, L^2-v*L+1)
                          > >
                          > > I am testing all x against psp-2 n below 2^32.
                          > >
                          >
                          > The gremlins score another goal with their counterexample:
                          > n==741470549 and x==68216238.
                          >

                          I noticed:
                          x^((n-1)/2)==593203119 (mod n)
                          L^((n+1)/2)==593203119 (mod n)

                          This got me thinking again...

                          kronecker(v^2-4,n)
                          ==kronecker((4*x^4-4*(-x^2+8)^2)/(-x^2+8)^2,n)
                          ==kronecker(4*x^4-4*(x^4-16*(x^2-4)),n)
                          ==kronecker(x^2-4,n)
                          ==-1

                          Hence L^((n+1)/2)==kronecker(v+2,n) (mod n, L^2-v*L+1)

                          kronecker(v+2,n)
                          ==kronecker(P^2/Q,n)
                          ==kronecker(Q,n)

                          Thus the Lucas test now becomes
                          L^((n+1)/2)==kronecker(-x^2+8,n)

                          I will continue testing psp-2s :-)

                          Paul
                        • paulunderwooduk
                          Hi, for odd n with minimal x such that kronecker(x^2-4,n)==-1, if x=0 then 2 selfridge: (L+2)^(n+1)==5 (mod n, L^2+1) if x=1 then 3 selfridge: gcd(7,n)==1
                          Message 12 of 14 , Oct 8, 2012
                          • 0 Attachment
                            Hi,

                            for odd n with minimal x such that kronecker(x^2-4,n)==-1,

                            if x=0 then 2 selfridge:
                            (L+2)^(n+1)==5 (mod n, L^2+1)

                            if x=1 then 3 selfridge:
                            gcd(7,n)==1
                            3^((n-1)/2)==kronecker(3,n) (mod n)
                            L^((n+1)/2)==kronecker(3,n) (mod n, L^2-(2/7)*L+1)

                            if x=3 then 4 selfridge:
                            gcd(3,n)==1
                            3^(n-1)==1 (mod n)
                            5^((n-1)/2)==-1 (mod n)
                            L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)

                            if n>x>3 then 4 selfridge:
                            (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
                            (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)

                            This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.

                            It is a mix of "section 10" of my paper in the file section of this group:
                            http://tech.groups.yahoo.com/group/primenumbers/files/Articles/
                            and of http://tech.groups.yahoo.com/group/primenumbers/message/24525

                            Paul
                          • paulunderwooduk
                            ... This should be L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)
                            Message 13 of 14 , Oct 9, 2012
                            • 0 Attachment
                              I need to report an of error:

                              > for odd n with minimal x such that kronecker(x^2-4,n)==-1,
                              >
                              > if x=0 then 2 selfridge:
                              > (L+2)^(n+1)==5 (mod n, L^2+1)
                              >
                              > if x=1 then 3 selfridge:
                              > gcd(7,n)==1
                              > 3^((n-1)/2)==kronecker(3,n) (mod n)
                              > L^((n+1)/2)==kronecker(3,n) (mod n, L^2-(2/7)*L+1)

                              This should be L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)

                              >
                              > if x=3 then 4 selfridge:
                              > gcd(3,n)==1
                              > 3^(n-1)==1 (mod n)
                              > 5^((n-1)/2)==-1 (mod n)
                              > L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)
                              >
                              > if n>x>3 then 4 selfridge:
                              > (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
                              > (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)
                              >
                              > This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.
                              >
                              > It is a mix of "section 10" of my paper in the file section of this group:
                              > http://tech.groups.yahoo.com/group/primenumbers/files/Articles/
                              > and of http://tech.groups.yahoo.com/group/primenumbers/message/24525
                              >
                              > Paul
                              >
                            • paulunderwooduk
                              I have changed the rules and added a puzzle. For odd n with x chosen in order from {0,1,6,3,all others} so that kronecker(x^2-4,n)==-1, ... if x=6 then 4
                              Message 14 of 14 , Oct 9, 2012
                              • 0 Attachment
                                I have changed the rules and added a puzzle.

                                For odd n with x chosen in order from {0,1,6,3,all others} so that kronecker(x^2-4,n)==-1,

                                > > if x=0 then 2 selfridge:
                                > > (L+2)^(n+1)==5 (mod n, L^2+1)
                                > >
                                > > if x=1 then 3 selfridge:
                                > > gcd(7,n)==1
                                > > 3^((n-1)/2)==kronecker(3,n) (mod n)
                                > L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)

                                if x=6 then 4 selfridge:
                                gcd(21,n)==1
                                6^(n-1)==1 (mod n) (*)
                                2^((n-1)/2)==kronecker(2,n) (mod n)
                                L^((n+1)/2)==kronecker(-7,n) (mod n, L^2+(18/7)*L+1)

                                > >
                                > > if x=3 then 4 selfridge:
                                > > gcd(3,n)==1
                                > > 3^(n-1)==1 (mod n)
                                > > 5^((n-1)/2)==-1 (mod n)
                                > > L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)
                                > >
                                > > if n>x>3 then 4 selfridge:
                                > > (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
                                > > (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)
                                > >
                                > > This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.
                                > >

                                Puzzle: find a counterexample for x==6 where (*) is dropped,

                                Paul
                              Your message has been successfully submitted and would be delivered to recipients shortly.