Arithmetic in quadratic fields with unique factorization.

*(English)*Zbl 0596.12001
Computer algebra, EUROCAL ’85, Proc. Eur. Conf., Linz/Austria 1985, Vol. 2, Lect. Notes Comput. Sci. 204, 279-288 (1985).

[For the entire collection see Zbl 0568.00019.]

The author gives two algorithms for computing the greatest common divisor of two elements a, b in the ring of integers of a quadratic field K of class number 1 and discriminant d. Since the Euclidean algorithm does not work for many of those fields other algorithms have to be used. Both algorithms presented have polynomial running time for fixed d.

The first algorithm uses frequently the continued fraction approximation of an approximation of a/b\(\in K\) up to a given bound. The new approximation of a/b is computed. A precondition is that for all rational integers less than \(\sqrt{| d|}\) the complete factorization in \({\mathfrak O}(K)\) is known.

The second algorithm computes the complete factorization of an integer a in \({\mathfrak O}(K)\). This algorithm can subsequently be used to precompute the factorizations in the first algorithm. This factorization uses the factorization in \({\mathbb{Z}}\) of the norm of a.

The last algorithm finds the shortest vector in a 4-dimensional lattice, depending on the two given elements of which we want to compute the GCD. The shortest vector corresponds to this GCD. Using some properties of the lattice it can be shown that the almost shortest vector that the algorithm of Lenstra, Lenstra and LovĂˇsz computes is in fact the shortest vector. The running time of the algorithm is polynomial in the input length if the discriminant of the field is fixed.

The author gives two algorithms for computing the greatest common divisor of two elements a, b in the ring of integers of a quadratic field K of class number 1 and discriminant d. Since the Euclidean algorithm does not work for many of those fields other algorithms have to be used. Both algorithms presented have polynomial running time for fixed d.

The first algorithm uses frequently the continued fraction approximation of an approximation of a/b\(\in K\) up to a given bound. The new approximation of a/b is computed. A precondition is that for all rational integers less than \(\sqrt{| d|}\) the complete factorization in \({\mathfrak O}(K)\) is known.

The second algorithm computes the complete factorization of an integer a in \({\mathfrak O}(K)\). This algorithm can subsequently be used to precompute the factorizations in the first algorithm. This factorization uses the factorization in \({\mathbb{Z}}\) of the norm of a.

The last algorithm finds the shortest vector in a 4-dimensional lattice, depending on the two given elements of which we want to compute the GCD. The shortest vector corresponds to this GCD. Using some properties of the lattice it can be shown that the almost shortest vector that the algorithm of Lenstra, Lenstra and LovĂˇsz computes is in fact the shortest vector. The running time of the algorithm is polynomial in the input length if the discriminant of the field is fixed.

Reviewer: F.J.van der Linden

##### MSC:

12-04 | Software, source code, etc. for problems pertaining to field theory |

11R11 | Quadratic extensions |

11R04 | Algebraic numbers; rings of algebraic integers |

11R27 | Units and factorization |

11A05 | Multiplicative structure; Euclidean algorithm; greatest common divisors |

68Q25 | Analysis of algorithms and problem complexity |