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|,
We find a and b from equations 5 and 6, avoiding the need to calculate |sc| and |sc+1|.
- n = r2 + s2,
- 1 ≤ r < s,
- gcd(r,s) = 1,
- xr ≡ (-1)c+1s (mod n),
- x = ar + bs,
- br – as = (-1)c+1,
- 0 ≤ a ≤ b, a ≤ r/2, b ≤ r/2,
- x2 + 1 = (a2 + b2)n.
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.
Last modified 28th September 2012
Return to main page