A generalization of the Hermite-Serret algorithm

Our algorithm takes an n > 2 for which the congruence x2 ≡ -1 (mod n) is soluble and for each such x, 1< x < n/2, performs Euclid's algorithm on r0 = n, r1 = x, to give an algorithm of even length 2c and a decreasing sequence of remainders r0 > r1 > ··· rc-1 > √n ≥ rc > ··· > r2c = 1. Then with r = rc+1, s = rc, we have (see note) with a = |sc|, b = |sc+1|,
  1. n = r2 + s2,
  2. 1 ≤ r < s,
  3. gcd(r,s) = 1,
  4. xr ≡ (-1)c+1s (mod n),
  5. x = ar + bs,
  6. br – as = (-1)c+1,
  7. 0 ≤ a ≤ b, a ≤ r/2, b ≤ r/2,
  8. x2 + 1 = (a2 + b2)n.
We find a and b from equations 5 and 6, avoiding the need to calculate |sc| and |sc+1|.

The mapping x → (r,s) is a 1-1 correspondence between the x satisfying x2 ≡ -1 (mod n), 1< x < n/2 and the (r,s) satisfying n = r2 + s2, 1 ≤ r < s, gcd(r,s) = 1.

Enter n (> 2):

Last modified 28th September 2012
Return to main page