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

Re: 1+1+1+2 selfridge composite test -- errata

Expand Messages
  • 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 1 of 14 , Sep 30, 2012
      >
      > > [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 2 of 14 , Oct 4, 2012
        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 3 of 14 , Oct 4, 2012
          >
          > 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 4 of 14 , Oct 8, 2012
            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 5 of 14 , Oct 9, 2012
              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 6 of 14 , Oct 9, 2012
                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.