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

4 Fermat and 1 Lucas

Expand Messages
  • paulunderwooduk
    Hi, the product of [x^3,-1;1;x][x^3,-1;1,-x] is [x^6-1,-x^3+x;x^3+x;-1-x^2] Its char. eqn. is L^2-P*L+Q==0 where P=x^6-x^2-2 Q=1-x^8 Now define a test of n for
    Message 1 of 11 , Jul 19 9:18 AM
    • 0 Attachment
      Hi,

      the product of [x^3,-1;1;x][x^3,-1;1,-x] is [x^6-1,-x^3+x;x^3+x;-1-x^2]

      Its char. eqn. is L^2-P*L+Q==0 where
      P=x^6-x^2-2
      Q=1-x^8

      Now define a test of n for suitable x:
      {tst(n,x)=local(P=x^6-x^2-2,Q=1-x^8);kronecker(P^2-4*Q,n)==-1&&
      Mod(x-1,n)^((n-1)/2)==kronecker(x-1,n)&&
      Mod(x+1,n)^((n-1)/2)==kronecker(x+1,n)&&
      Mod(x^2+1,n)^((n-1)/2)==kronecker(x^2+1,n)&&
      Mod(x^4+1,n)^((n-1)/2)==kronecker(x^4+1,n)&&
      Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}

      The last expression can be broken into a Euler PRP test on Q, plus a the Lucas test:
      L^((n+1)/2)==kronecker(Q,n) (mod n, L^2-(P^2/Q-2)*L+1).
      So, in total, the test is 1+1+1+1+2 selfridge.

      I have done my usual tests, but found no counterexample.

      This got me thinking; What about the test based on [x^3,-1;1,-x]?:

      {tst(n,x)=local(P=x^3-x,Q=1-x^4);kronecker(P^2-4*Q,n)==-1&&
      Mod(x-1,n)^((n-1)/2)==kronecker(x-1,n)&&
      Mod(x+1,n)^((n-1)/2)==kronecker(x+1,n)&&
      Mod(x^2+1,n)^((n-1)/2)==kronecker(x^2+1,n)&&
      Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}

      This has a counterexample for n=162401 and x=478.

      Or in general on [x^(2^k-1),-1;1,-x]:

      {tst(n,x,k)=local(P=x^(2^k-1)-x,Q=1-x^(2^k);kronecker(P^2-4*Q,n)==-1&&
      Mod(x-1,n)^((n-1)/2)==kronecker(x-1,n)&&
      Mod(x+1,n)^((n-1)/2)==kronecker(x+1,n)&&
      Mod(x^2+1,n)^((n-1)/2)==kronecker(x^2+1,n)&&
      ...
      Mod(x^(2^(k-1))+1,n)^((n-1)/2)==kronecker(x^(2^(k-1))+1,n)&&
      Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}

      Or even a test based on [x^5;-1;1,-x^3] etc.,

      Paul
    • paulunderwooduk
      ... [17343, 5535, 369] [34279, 16849, 581] [34639, 5159, 737] The 3rd entry is gcd(n,x) {tst(n,x)=local(P=x^3*(x^2-1),Q=1-x^8);kronecker(P^2-4,n)==-1&&
      Message 2 of 11 , Jul 19 10:30 AM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        >

        > Or even a test based on [x^5;-1;1,-x^3] etc.,
        >

        [17343, 5535, 369]
        [34279, 16849, 581]
        [34639, 5159, 737]

        The 3rd entry is gcd(n,x)

        {tst(n,x)=local(P=x^3*(x^2-1),Q=1-x^8);kronecker(P^2-4,n)==-1&&
        Mod(x-1,n)^((n-1)/2)==kronecker(x-1,n)&&
        Mod(x+1,n)^((n-1)/2)==kronecker(x+1,n)&&
        Mod(x^2+1,n)^((n-1)/2)==kronecker(x^2+1,n)&&
        Mod(x^4+1,n)^((n-1)/1)==kronecker(x^4+1,n)&&
        Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}

        Paul
      • djbroadhurst
        ... Why, I wonder, does Paul keep posting these hopeless causes? He has already fully conceded that ... as was comprehensively demonstrated in my
        Message 3 of 11 , Jul 19 4:02 PM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "paulunderwooduk" <paulunderwood@...> wrote:

          > {tst(n,x)=
          <whatever>

          Why, I wonder, does Paul keep posting these hopeless causes?

          He has already fully conceded that

          > one parameter Lucas plus N Fermat/Euler/M-R PRP test
          > can be counterexampled

          as was comprehensively demonstrated in my patient and
          accurate responses to his last long series of postings,
          including all of his post-host and equally hopeless
          wriggling, as I had done so with several comparable cases in
          the past few years.

          Why, I wonder, does Paul expect me to programme the Gremlins
          to refute a claim that he already /admits/ to be hopeless?

          It seems to me that this is time to call a stop to filling
          up the PrimeNumbers list with conjectures that Paul has
          already publicly disavowed:

          > one parameter Lucas plus N Fermat/Euler/M-R PRP test
          > can be counterexampled

          David
        • paulunderwooduk
          ... I posted again, because I was pleased with finding a test where Q=2^(2^k)-1 has k+1 factors and allows k+1 Euler PRP tests with a Lucas PRP test. I should
          Message 4 of 11 , Jul 19 4:31 PM
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
            >
            >
            >
            > --- In primenumbers@yahoogroups.com,
            > "paulunderwooduk" <paulunderwood@> wrote:
            >
            > > {tst(n,x)=
            > <whatever>
            >
            > Why, I wonder, does Paul keep posting these hopeless causes?
            >
            > He has already fully conceded that
            >
            > > one parameter Lucas plus N Fermat/Euler/M-R PRP test
            > > can be counterexampled
            >
            > as was comprehensively demonstrated in my patient and
            > accurate responses to his last long series of postings,
            > including all of his post-host and equally hopeless
            > wriggling, as I had done so with several comparable cases in
            > the past few years.
            >
            > Why, I wonder, does Paul expect me to programme the Gremlins
            > to refute a claim that he already /admits/ to be hopeless?
            >

            I posted again, because I was pleased with finding a test where Q=2^(2^k)-1 has k+1 factors and allows k+1 Euler PRP tests with a Lucas PRP test. I should have added gcd(x*Q,n)==1. But I suspect my umpteen postings are tiresome. So I will hold my tongue for the time being. I will be trying out the many variations of PRP testing based on [x^a,-1;1,-x^b]. Without the Gremlin's aid, I have a hacked script of yours, GMP for a shallow n search, Richard Pinch's list of Carmichael numbers, and, most importantly, Francois Arnault's paper, which I must learn,

            > It seems to me that this is time to call a stop to filling
            > up the PrimeNumbers list with conjectures that Paul has
            > already publicly disavowed:
            >
            > > one parameter Lucas plus N Fermat/Euler/M-R PRP test
            > > can be counterexampled
            >

            Paul
          • djbroadhurst
            ... Here, as patiently as I am able, is how to fool any tst(n,a) with, at is heart, in general terms, a Lucas test of type L^((n+1)/2) = +/- 1 mod (n, L^2 -
            Message 5 of 11 , Jul 19 6:24 PM
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              "paulunderwooduk" <paulunderwood@...> wrote:

              > Francois Arnault's paper, which I must learn

              Here, as patiently as I am able, is how to fool any "tst(n,a)"
              with, at is heart, in general terms, a Lucas test of type

              L^((n+1)/2) = +/- 1 mod (n, L^2 - y*L +1)

              with y some rational function of the parameter 'a' in terms
              of which you have defined your effete additional
              Fermat/Euler/M-R tests and gcd wriggles.

              For some obscure reason, your last choice was
              y = 2*(5*a^2-1)/(3*a^2+1). Now you have made a new choice.
              But who cares? The fooling method would be the same.

              OK, Paul? Have you got that? All we care about,
              for Lucas, are powers of L mod (n, L^2 - y*L + 1).

              Then here is the trick.

              Chose some small odd number k > 1 (like k = 19 in my last hints)
              and semiprimes of the form n=p*q with primes p = -1 mod k
              and q = 1 + 2*k*m*(p-1), where m is small. (I usually choose m=1.)

              Then find the irreducible polynomial P(x), with degree
              eulerphi(k)/2, satisfied by 2*cos(2*Pi/k), and solve
              for P(+/-y) = 0 mod n. For k = 19, P(x) is

              ? print(algdep(2*cos(2*Pi/19),9))
              x^9 + x^8 - 8*x^7 - 7*x^6 + 21*x^5 + 15*x^4 - 20*x^3 - 10*x^2 + 5*x + 1

              Exercise: Show that with x = +/- 2*(5*a^2-1)/(3*a^2+1),
              the numerators give

              {smart(a,n)=local(v=[
              581130733*a^18-1549681961*a^16+1598109492*a^14-815197364*a^12
              +219605318*a^10-31108446*a^8+2189796*a^6-67524*a^4+693*a^2-1,
              290565367*a^18-920123659*a^16+1150154588*a^14-728431196*a^12
              +250797682*a^10-47124218*a^8+4637292*a^6-217740*a^4+4047*a^2-19]);
              ...

              as in the Gremlins latest totally successful attack.

              Now all we have to do, for a given prime pair (p,q), is to
              find the roots of these bizarre polys, mod n, using
              polrootsmod and the CRT.

              Up to effete signs, we have solved the Lucas problem.
              Up to effete signs, we have solved all the additional
              Fermat/Euler bolt-ons, mod p. All that is left are the
              Fermats mod q. As is clear from Arnault, you will
              not need to spend long looping on p, k, m, to solve
              Fermats mod q = 1 + 2*k*m*(p-1), for at least one
              of the many chinese roots.

              That's it. All that can happen is that the deviser of the
              hopeless test may wriggle with gcds, and arbitrarily bolt on
              additional Fermats/Euler/M-R's, thereby filling PrimeNumbers
              with lots of noise that cannot change the fact that she/he is
              bound to lose, because, in your own words:

              > one parameter Lucas plus N Fermat/Euler/M-R PRP test
              > can be counterexampled

              End of story? End of long repetitious posts?

              David
            • paulunderwooduk
              ... Once more unto the breach, dear friends, once more. I found a conterexample, [21488634019, 10045419357], to a test based on [x^4,-1;1,-1] using a
              Message 6 of 11 , Jul 20 1:18 PM
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                >
                > --- In primenumbers@yahoogroups.com,
                > "paulunderwooduk" <paulunderwood@> wrote:
                >
                > > one parameter Lucas plus N Fermat/Euler/M-R PRP test
                > > can be counterexampled
                >
                > End of story? End of long repetitious posts?
                >

                "Once more unto the breach, dear friends, once more."

                I found a conterexample, [21488634019, 10045419357],
                to a test based on [x^4,-1;1,-1] using a modification of:
                http://physics.open.ac.uk/~dbroadhu/cert/underw5x.gp

                I am trying [x^8,-1;1,-1] now, but I will button my lip :-)

                Paul
              • paulunderwooduk
                ... Breaking my Trappist vow... I have run the script: {tst(n,x)=local(P=x^8-1,Q=1-x^8);kronecker(P^2-4*Q,n)==-1&&gcd(x,n)==1&& Mod(x-1,n)^(n-1)==1&&
                Message 7 of 11 , Aug 1, 2013
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
                  >
                  >
                  >
                  > --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@> wrote:
                  > >
                  > > --- In primenumbers@yahoogroups.com,
                  > > "paulunderwooduk" <paulunderwood@> wrote:
                  > >
                  > > > one parameter Lucas plus N Fermat/Euler/M-R PRP test
                  > > > can be counterexampled
                  > >
                  > > End of story? End of long repetitious posts?
                  > >
                  >
                  > "Once more unto the breach, dear friends, once more."
                  >
                  > I found a conterexample, [21488634019, 10045419357],
                  > to a test based on [x^4,-1;1,-1] using a modification of:
                  > http://physics.open.ac.uk/~dbroadhu/cert/underw5x.gp
                  >
                  > I am trying [x^8,-1;1,-1] now, but I will button my lip :-)
                  >

                  Breaking my Trappist vow...

                  I have run the script:

                  {tst(n,x)=local(P=x^8-1,Q=1-x^8);kronecker(P^2-4*Q,n)==-1&&gcd(x,n)==1&&
                  Mod(x-1,n)^(n-1)==1&&
                  Mod(x+1,n)^(n-1)==1&&
                  Mod(x^2+1,n)^(n-1)==1&&
                  Mod(x^4+1,n)^(n-1)==1&&
                  Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}

                  {tst1(p,q)=local(n=p*q,u=[]);
                  for(a=3,p-3,if((n%(p-1)==1||(Mod(a^8-1,p)^(n-1)==1))&&
                  Mod(Mod(1,p)*L,L^2+(a^8+1)*L+1)^(n+1)==1,
                  u=concat(u,a)));Mod(u,p);}

                  {tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
                  up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
                  for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
                  if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
                  if(#V,print([n,V[1]]));V;}

                  {forprime(p=7,400000,for(k=1,17,q=1+2*k*(p-1);
                  if(ispseudoprime(q),tst2(p,q))));
                  print("\\\\ "round(gettime/1000)" seconds");}

                  Note the size of the parameters compared to the David's original.

                  I have also tested all Carmichael numbers < 2^32 with all possible "x". Similarly, I have tested all n < 7.5*10^6.

                  Also, note that the Fermat PRP tests are not bolted on since:
                  Q=(1-x)*(1+x)*(1+x^2)*(1+x^4).

                  Paul
                • djbroadhurst
                  ... Here are 10 counterexamples to your latest vain idea: {tst(n,x)=local(P=x^8-1,Q=1-x^8); kronecker(P^2-4*Q,n)==-1&&gcd(x,n)==1&& Mod(x-1,n)^(n-1)==1&&
                  Message 8 of 11 , Aug 1, 2013
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com,
                    "paulunderwooduk" <paulunderwood@...> wrote:

                    > Breaking my Trappist vow...

                    Why, Paul? You have freely admitted that there is no point:

                    > one parameter Lucas plus N Fermat/Euler/M-R PRP test
                    > can be counterexampled

                    Here are 10 counterexamples to your latest vain idea:

                    {tst(n,x)=local(P=x^8-1,Q=1-x^8);
                    kronecker(P^2-4*Q,n)==-1&&gcd(x,n)==1&&
                    Mod(x-1,n)^(n-1)==1&&
                    Mod(x+1,n)^(n-1)==1&&
                    Mod(x^2+1,n)^(n-1)==1&&
                    Mod(x^4+1,n)^(n-1)==1&&
                    Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}

                    {F=[
                    [7750135694869, 822096191222],
                    [23723039862349, 1323013054084],
                    [90273119893069, 5862741794270],
                    [264256506403909, 38817437399213],
                    [8955652979403079, 1851456656424086],
                    [4574665869143389, 885331489130492],
                    [5266652551034509, 988874992567097],
                    [8618233825140949, 584166437019905],
                    [9541864502273629, 720345160544763],
                    [10245855908959669, 226701623305716]];

                    c=0;for(k=1,#F,n=F[k][1];x=F[k][2];if(!isprime(n)&&tst(n,x),c++));
                    print(" fooled "c" times");}

                    fooled 10 times

                    NB: Please, Paul, no more wriggles, sign tests, gcds, extra Fermats,
                    new choices of [P,Q], this August. The Gremlins are sunning
                    themselves and find it irkesome to tool up for such vain tests.

                    David (their overheated minder)
                  • paulunderwooduk
                    ... Those are good counterexamples, with some passing Euler PRP tests. I notice all have kronecker(x^4-1,n)==-1, but I give up on this trail, knowing the
                    Message 9 of 11 , Aug 1, 2013
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                      >
                      >
                      >
                      > --- In primenumbers@yahoogroups.com,
                      > "paulunderwooduk" <paulunderwood@> wrote:
                      >
                      > > Breaking my Trappist vow...
                      >
                      > Why, Paul? You have freely admitted that there is no point:
                      >
                      > > one parameter Lucas plus N Fermat/Euler/M-R PRP test
                      > > can be counterexampled
                      >
                      > Here are 10 counterexamples to your latest vain idea:
                      >
                      > {tst(n,x)=local(P=x^8-1,Q=1-x^8);
                      > kronecker(P^2-4*Q,n)==-1&&gcd(x,n)==1&&
                      > Mod(x-1,n)^(n-1)==1&&
                      > Mod(x+1,n)^(n-1)==1&&
                      > Mod(x^2+1,n)^(n-1)==1&&
                      > Mod(x^4+1,n)^(n-1)==1&&
                      > Mod(Mod(1,n)*L,L^2-P*L+Q)^(n+1)==Q;}
                      >
                      > {F=[
                      > [7750135694869, 822096191222],
                      > [23723039862349, 1323013054084],
                      > [90273119893069, 5862741794270],
                      > [264256506403909, 38817437399213],
                      > [8955652979403079, 1851456656424086],
                      > [4574665869143389, 885331489130492],
                      > [5266652551034509, 988874992567097],
                      > [8618233825140949, 584166437019905],
                      > [9541864502273629, 720345160544763],
                      > [10245855908959669, 226701623305716]];
                      >
                      > c=0;for(k=1,#F,n=F[k][1];x=F[k][2];if(!isprime(n)&&tst(n,x),c++));
                      > print(" fooled "c" times");}
                      >
                      > fooled 10 times
                      >
                      > NB: Please, Paul, no more wriggles, sign tests, gcds, extra Fermats,
                      > new choices of [P,Q], this August. The Gremlins are sunning
                      > themselves and find it irkesome to tool up for such vain tests.
                      >

                      Those are good counterexamples, with some passing Euler PRP tests. I notice all have kronecker(x^4-1,n)==-1, but I give up on this trail, knowing the Gremlins will outwit me in any event,

                      Paul
                    • djbroadhurst
                      ... So, Paul, my old friend, you have a month to read my secret-spilling tutorial http://tech.groups.yahoo.com/group/primenumbers/message/25241 to understand
                      Message 10 of 11 , Aug 2, 2013
                      • 0 Attachment
                        --- In primenumbers@yahoogroups.com,
                        "paulunderwooduk" <paulunderwood@...> wrote:

                        > > fooled 10 times
                        > >
                        > > NB: Please, Paul, no more wriggles, sign tests, gcds, extra Fermats,
                        > > new choices of [P,Q], this August. The Gremlins are sunning
                        > > themselves and find it irkesome to tool up for such vain tests.
                        >
                        > Those are good counterexamples

                        So, Paul, my old friend, you have a month to read
                        my secret-spilling tutorial
                        http://tech.groups.yahoo.com/group/primenumbers/message/25241
                        to understand this one line forger's recipe:

                        print(subst(algdep(2*cos(2*Pi/5),2),x,x^8))
                        x^16 + x^8 - 1

                        Of course were you to add gcd(x^16+x^8-1,n)==1, in September,
                        the Gremlins would work with different cosines.

                        David
                      • WarrenS
                        Tao, Harcos, Englesma, et al seem to have stalled trying to improve Zhang s upper bound of 70,000,000. They claim to have confirmed they got it down to 5414
                        Message 11 of 11 , Aug 4, 2013
                        • 0 Attachment
                          Tao, Harcos, Englesma, et al seem to have stalled trying to improve Zhang's upper
                          bound of 70,000,000. They claim to have confirmed they got it down to 5414 but look
                          like they aren't going to be able to go much further (perhaps can push it a bit below 5000
                          if combine all their juice?).


                          http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes
                        Your message has been successfully submitted and would be delivered to recipients shortly.