### Reducing a binary indefinite quadratic form using Henri Cohen's algorithm

Given an indefinite binary quadratic form ax^{2}+bxy+cy^{2}, 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=b^{2}-4ac > 0, d is not a perfect square and we assume d < 10^{6}.

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), (r^{2}(-b, c)- d)/4c).

Then

- if (a, b, c) is reduced, so is ρ(a, b, c);
- the unimodular transformation x = Y, y = -X - Y(b + b´)/2c converts ax
^{2} + bxy + cy^{2} into a´X^{2} + b´XY + c´Y^{2};
- 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.

*Last modified 12th December 2006*

Return to main page