Algorithms for finite abelian groups
Johannes A Buchmann, Sachar Paulus · 1993
We study the complexity of the basic computational problems in a finite abelian group; i.e. we prove upper bounds for the number of operations necessary to compute the order of an element, discrete logarithms, the order of the group, the structure of the group, roots of an element. 1 The results Let G be a finite abelian group, jGj = h; elements of G are given in some representation which has the following properties: 1. for ff; fi 2 G we can compute \\Gammaff and ff + fi, 2. the "test on neutral element" 0G is known; i.e. for a given element ff we can decide whether ff = 0G or not and 3. we can choose elements fl of G "at random": p(fl) = 1 h 1+o(1) ` i.e. p(fl) = 1 h 1+e fl ; je fl j ! f(h); lim h!1 f(h) = 0 ' : Typical examples of groups for which such a representation exists (that is, to which we can apply our results) are: ffl the multiplicative group of a finite field, ffl the set of points of an elliptic curve over a finite field, Fachbereich Informatik, Universi...