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
  • 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 1 of 11 , Jul 20, 2013
    • 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 2 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 3 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 4 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 5 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 6 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.