Fast Ideal Arithmetic In Real Quadratic Fields
by
Reginald Sawilla
University of Calgary

Ideal multiplication and reduction are fundamental operations on ideals and are used extensively in class group and infrastructure computations; hence, the efficiency of these operations is extrememly important. Rickert developed a reduction algorithm for the closely related case of positive definite binary quadratic forms which is more efficient than the classical methods. Similarly, Schoenhage developed an algorithm that works for all binary quadratic forms. We will present adaptations of both of these methods to real quadratic fields that also compute the reducing number necessary for infrastructure computations. We also present a new method which combines the ideas of Shanks, Williams, et al. into a particularly simple algorithm. These three algorithms have been implemented and compared with classical reduction and the Jacobson-Scheidler-Williams adaptation of NUCOMP.

Date received: April 30, 2004