Reducing a binary indefinite quadratic form using Henri Cohen's algorithm
Given an indefinite binary quadratic form ax2+bxy+cy2, we use Algorithm 5.6.5 of Henri Cohen's book, A course in computational number theory, Edition 1, pp. 257-261, to construct a unimodular transformation taking the given form into a reduced form, i.e.,
0 < √d - b < 2|a| < √d + b.
The cycle starting at the reduced form is printed.
Note: Here d=b2-4ac > 0, d is not a perfect square and we assume d < 106.
Also see explanatory note.
Algorithm 5.6.5 (Henri Cohen, page 257) Assume c ≠ 0. Then r = r(-b, c) is the unique integer satisfying
r ≡ -b (mod 2c), where
|(i) -|c| < r ≤ |c|,|| if |c| > √d,|
|(ii) √d - 2|c| < r < √d,|| if |c| < √d.|
Next define ρ(a, b, c) = (a´, b´, c´) = (c, r(-b, c), (r2(-b, c)- d)/4c).
e=0 prints only the first reduced form met, while e=1 is verbose.
- if (a, b, c) is reduced, so is ρ(a, b, c);
- the unimodular transformation x = Y, y = -X - Y(b + b´)/2c converts ax2 + bxy + cy2 into a´X2 + b´XY + c´Y2;
- for some n ≥ 0, ρn(a, b, c) will eventually be reduced.
Last modified 12th December 2006
Return to main page