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

Re: 4 Fermat and 1 Lucas [freely admitted by its author to be hopeless]

Expand Messages
  • 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 1 of 11 , Jul 19, 2013
    View Source
    • 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 2 of 11 , Jul 20, 2013
      View Source
      • 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 3 of 11 , Aug 1, 2013
        View Source
        • 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 4 of 11 , Aug 1, 2013
          View Source
          • 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 5 of 11 , Aug 1, 2013
            View Source
            • 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 6 of 11 , Aug 2, 2013
              View Source
              • 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 7 of 11 , Aug 4, 2013
                View Source
                • 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.