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

25228Re: Fermat+Euler+Frobenius

Expand Messages
  • paulunderwooduk
    Jul 18, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- In primenumbers@yahoogroups.com,
      > "paulunderwooduk" <paulunderwood@> wrote:
      >
      > > I now present a puzzle: make all the tests "strong"
      >
      > That's your job; not the Gremlins' :-)
      >

      Well, I can't do what the Gremlins have done to refute my efforts so far, let alone to solve my own puzzle! But I will make a silver sub-puzzle by dropping any PRP test on "a", but still insisting on strong tests for the other PRP sub-tests including the Lucas PRP test.

      > To show that they can still work at 120 digits,
      > even after all your wriggling, they invite you to find
      > gcd's that stop these pseudoprimes fooling your test:
      >

      I am unable to crack the gcd tricks and I am in the dark as to how Kermit factored the numbers in:
      http://tech.groups.yahoo.com/group/primenumbers/message/25227

      > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
      > sum(k=1,#v,gcd(v[k],n)>1)==0;}
      >
      > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
      > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
      > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
      > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
      > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
      > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}
      >
      > {fooling=[
      >
      > [16212200212765236462624941301662595905969969921486185624581\
      > 42710646148264113979405459683534701445570403174269878228032843,
      >
      > 148751952532863090430663215218366305961343757352250610518989\
      > 959178089757327365262627066765931489564753215534936293595719],
      >
      > [92856680188887785533016964629715768104484119019221599899820\
      > 26844918042826013874700027439880606063780672269637251932365051,
      >
      > 246307830695230159344853971299085504661118671451065969332908\
      > 6522201134308546059459112977581864702729364124320490100075243]];
      >
      > for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];
      > if(tst(n,a)&&!isprime(n),print(" Gremlins rule OK")));}
      >
      > Gremlins rule OK
      > Gremlins rule OK
      >
      > They prefer to work around 120 digits, since then
      > you have to be a little smarter to factor the semiprimes.
      > I believe that Kermit will be able to factorize the two
      > above, since he has been using other lists as practice.
      >

      Paul
    • Show all 24 messages in this topic