Structure computation and discrete logarithms in finite abelian p-groups

Abstract

We present a generic algorithm for computing discrete logarithms in a finite abelian p-group H, improving the Pohlig-Hellman algorithm and its generalization to noncyclic groups by Teske. We then give a direct method to compute a basis for H without using a relation matrix. The problem of computing a basis for some or all of the Sylow p-subgroups of an arbitrary finite abelian group G is addressed, yielding a Monte Carlo algorithm to compute the structure of G using O(|G|^0.5) group operations. These results also improve generic algorithms for extracting pth roots in G.

23 pages, minor edits

Cited by in corpus (8)

• Sato-Tate distributions and Galois endomorphism modules in genus 2
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
• Accelerating the CM method
• Identifying supersingular elliptic curves
• Fast Jacobian arithmetic for hyperelliptic curves of genus 3
• Computing L-Polynomials of Picard curves from Cartier-Manin matrices
• Cryptographic multilinear maps using pro-p groups
• Computing Euler factors of genus 2 curves at odd primes of almost good reduction