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

Re: Fermat+Euler+Frobenius

Expand Messages
  • djbroadhurst
    ... That s what Gremlins are for. ... Here is one of many ways to evade your wriggles, which had trivial gcds. I give a pair of smarter gcds, which serve for
    Message 1 of 24 , Jul 19 6:35 AM
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "paulunderwooduk" <paulunderwood@...> wrote:

      > Wonderful! Thanks for the exposition. It is another example
      > of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test
      > can be counterexampled.

      That's what Gremlins are for.

      > I am unable to crack the gcd tricks

      Here is one of many ways to evade your wriggles, which had
      trivial gcds. I give a pair of smarter gcds, which serve
      for three small examples, But as soon as we include this trap
      the Gremlins will find another smart way out.

      {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);}

      {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]);
      sum(k=1,#v,gcd(v[k],n)>1)>0;}

      {fooling=[
      [2972225251*112944559501,48957135643862669970],
      [3047555083*115807093117,49017305561177450303],
      [3130042291*118941607021,169666628495887666139]];

      for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];if(tst(n,a)
      &&smart(a,n),print(" fooled wriggle, trapped smartly")));}

      fooled wriggle, trapped smartly
      fooled wriggle, trapped smartly
      fooled wriggle, trapped smartly

      The derivation of the pair of polynomials, for
      these particular cases, is left as an exercise.

      David (spilling the Gremlins' secrets)
    • djbroadhurst
      ... Maybe Kermit read http://selmer.warwick.ac.uk/onelinefactor.pdf {OLF(x)=;i=1;while(i
      Message 2 of 24 , Jul 31 8:11 PM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "paulunderwooduk" <paulunderwood@...> wrote:

        > I am in the dark as to how Kermit factored the numbers in:
        > http://tech.groups.yahoo.com/group/primenumbers/message/25227

        Maybe Kermit read
        http://selmer.warwick.ac.uk/onelinefactor.pdf

        {OLF(x)=;i=1;while(i<x,if(issquare(ceil(sqrt(i*x))^2%x),
        return(gcd(x,floor(ceil(sqrt(i*x))-sqrt((ceil(sqrt(i*x))^2)%x)))));i++);}

        {default(realprecision,130);gettime;
        N1=16212200212765236462624941301662595905969969921486185624581
        42710646148264113979405459683534701445570403174269878228032843;
        N2=92856680188887785533016964629715768104484119019221599899820
        26844918042826013874700027439880606063780672269637251932365051;
        print(OLF(N1)" divides N1");
        print(OLF(N2)" divides N2");
        print("This took "gettime" millisecond(s)");}

        5972172173345601078558810561451365062976970419888735246630677 divides N1
        11401725845872759790535993230138294233298881744517681451802021 divides N2
        This took 1 millisecond(s)

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.