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

24826Re: mod quartic composite tests

Expand Messages
  • paulunderwooduk
    Jan 18, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
      >
      >
      >
      > > All are trapped by Paul's latest wriggle,
      > > which requires x^2-3 to be coprime to n.
      >
      > Exercise: Show that Paul's test
      > Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2
      > requires n to be a Fermat pseudoprime in base 1+(x^2-3)*(x^2-2)^3
      > and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.
      >

      ? M=[0,(x^2-2),0,-1;1,0,0,0;0,1,0,0;0,0,1,0];matdet(M+x^2-2)==1+(x^2-3)*(x^2-2)^3
      1

      Thanks for the insight.

      This can be split into 2 Fermat tests:

      ? M=[x,-1;1,0];matdet(M+x^2-2)
      x^4 + x^3 - 4*x^2 - 2*x + 5
      ? M=[-x,-1;1,0];matdet(M+x^2-2)
      x^4 - x^3 - 4*x^2 + 2*x + 5

      which are equal to:

      ? M=[x,-1;1,0];matdet(M+x^2-2)==(x^2-2)*(x+2)*(x-1)+1
      1
      ? M=[-x,-1;1,0];matdet(M+x^2-2)==(x^2-2)*(x-2)*(x+1)+1
      1

      Paul
    • Show all 26 messages in this topic