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

24810Re: mod quartic composite tests

Expand Messages
  • djbroadhurst
    Jan 9, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      Paul Underwood wrote:

      > (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*L+1)*(L^2+x*L+1))
      > This test is (1)+(1)+(2)+(2)+9 selfridge for small x

      I can do it in 6 selfridges for generic x.
      Where do your "9" selfridges come from, Paul?

      With kronecker(x^4-2,n) = -1 and prime n, we have

      (L+a)^n = a+x-L mod(n, L^2-L*x+1) ... [1]
      (L+a)^n = a-x-L mod(n, L^2+L*x+1) ... [2]

      and the two Frobenius tests cost 3+3=6 selfridges, generically.

      Now let f(x,L) = -L^3+(x^2-2)*L and observe
      from simple algebra (no modularity involved) that

      f(x,L) + a = (a+x-L) - (L+x)*(L^2-x*L+1)
      f(x,L) + a = (a-x-L) - (L-x)*(L^2+x*L+1)

      Hence [1] and [2] imply that

      (L+a)^n = f(x,L) + a mod(n, (L^2-x*L+1)*(L^2+x*L+1)) ... [3]

      and Paul has set a = 2 in [3].

      Since this is a double-Frobenius test, the gremlins
      reserve the right to choose /both/ parameters (a,x) in [3].

      David
    • Show all 26 messages in this topic