Type: Article
Publication Date: 2010-12-01
Citations: 13
DOI: https://doi.org/10.1216/rmj-2010-40-6-1979
where dj ∈ Z, αj = (aj+bj √ d) 2 ∈ Q( √ d), aj , bj ∈ Z, j = 1, . . . , k. Bounds on k, α and dj are given in [Mau], and all depend polynomially on log d. Compact representations are used to store the fundamental unit of the quadratic order OK . The reason for doing this is that, as is shown in [Lag], there is an infinite set of quadratic orders, such that the binary length of the fundamental unit is exponential in log d. This makes it impossible to create an algorithm for solving the Pell equation with complexity less than exponential. Compact representations are polynomial in log d, and allow faster algorithms for solving the Pell equation. This representation is an extension of a compact representation as defined in [BTW] from algebraic integers to all elements of Q∗( √ d). It is often useful to do modular arithmetic on compact representations, for example for determening the solvability of certain Diophantine equations, as seen in [JW]. We present an algorithm for computing the value of a quadratic integer represented by a compact representation as defined in [Mau]. In [BTW] and [JW] there are algorithms for doing modular arithmetic on compact representations as defined in [BTW], but to our knowledge there are no algorithms for doing modular arithmetic on compact representations as defined in [Mau]. The main problem is that the [BTW] representation requires that the partial products