### A generalization of the Hermite-Serret algorithm

Our algorithm takes an n > 2 for which the congruence x^{2} ≡ -1 (mod n) is soluble and for each such x, 1< x < n/2, performs Euclid's algorithm on r_{0} = n, r_{1} = x, to give an algorithm of even length 2c and a decreasing sequence of remainders
r_{0} > r_{1} > ··· r_{c-1} > √n ≥ r_{c} > ··· > r_{2c} = 1.
Then with r = r_{c+1}, s = r_{c}, we have (see note) with a = |s_{c}|, b = |s_{c+1}|,
- n = r
^{2} + s^{2},
- 1 ≤ r < s,
- gcd(r,s) = 1,
- xr ≡ (-1)
^{c+1}s (mod n),
- x = ar + bs,
- br – as = (-1)
^{c+1},
- 0 ≤ a ≤ b, a ≤ r/2, b ≤ r/2,
- x
^{2} + 1 = (a^{2} + b^{2})n.

We find a and b from equations 5 and 6, avoiding the need to calculate |s_{c}| and |s_{c+1}|.
The mapping x → (r,s) is a 1-1 correspondence between the x satisfying
x^{2} ≡ -1 (mod n), 1< x < n/2 and the (r,s) satisfying n = r^{2} + s^{2}, 1 ≤ r < s, gcd(r,s) = 1.

*Last modified 28th September 2012*

Return to main page