Compact representation in real quadratic congruence function fields

Quadratic extensions (11R11) Arithmetic theory of algebraic function fields (11R58) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Analysis of algorithms and problem complexity (68Q25)

Review text

Starting point for the article is the (old) observation that the fundamental unit of a real quadratic (function) field tends to be of the size \(\sqrt D\) with \(D\) the discriminant (if the unit is written with respect to the usual basis). Therefore to have ``fast algorithms dealing with units, it is necessary to have a compact (read smaller) representation of this unit or of field elements. Following the ideas in [\textit{J. Buchmann, C. Thiel} and \textit{H. Williams}, Short representation of quadratic integers. Math. Appl., Dordr. 325, 159-185 (1995; Zbl 0833.11060)] the author develops a compact representation for field elements of size bounded in terms of the norm of the element and the logarithm of the discriminant. She constructs a finite sequence of small field elements and exponents allowing her to represent large elements as a power product involving only small quantities. She applies her results to show the following complexity results: Testing for principality of ideals, equivalence and discrete logarithm problem for ideal classes belong to (NP), i.e. there is a proof running in polynomial time. For the entire collection see [Zbl 0852.00023].

Recommendations

Cited in

(5)

This page was built for publication: Compact representation in real quadratic congruence function fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375623)