Search

In this paper, we present novel algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. For these problems, we obtain improved heuristic complexity results in almost all cases and significantly improved performance in practice. The speed-up is especially high in situations where the ideal class group can be computed in advance.

Differential difference algebras were introduced by Mansfield and Szanto, which arose naturally from differential difference equations. In this paper, we investigate the Gelfand-Kirillov dimension of differential difference algebras. We give a lower bound of the Gelfand-Kirillov dimension of a differential difference algebra and a sufficient condition under which the lower bound is reached; we also find an upper bound of this Gelfand-Kirillov dimension under some specific conditions and construct an example to show that this upper bound can not be sharpened any more., Comment: 12 pages