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).

Then

  1. if (a, b, c) is reduced, so is ρ(a, b, c);
  2. the unimodular transformation x = Y, y = -X - Y(b + b´)/2c converts ax2 + bxy + cy2 into a´X2 + b´XY + c´Y2;
  3. for some n ≥ 0, ρn(a, b, c) will eventually be reduced.
e=0 prints only the first reduced form met, while e=1 is verbose.

Enter a:
Enter b:
Enter c:
Enter e (0 or 1:

Last modified 12th December 2006
Return to main page