On some computational problems in finite abelian groups |
| |
| Authors: | Johannes Buchmann Michael J. Jacobson Jr. Edlyn Teske. |
| |
| Affiliation: | Technische Hochschule Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10, 64283 Darmstadt, Germany ; Technische Hochschule Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10, 64283 Darmstadt, Germany ; Technische Hochschule Darmstadt, Institut für Theoretische Informatik, Alexanderstraße 10, 64283 Darmstadt, Germany |
| |
| Abstract: | We present new algorithms for computing orders of elements, discrete logarithms, and structures of finite abelian groups. We estimate the computational complexity and storage requirements, and we explicitly determine the  -constants and  -constants. We implemented the algorithms for class groups of imaginary quadratic orders and present a selection of our experimental results. Our algorithms are based on a modification of Shanks' baby-step giant-step strategy, and have the advantage that their computational complexity and storage requirements are relative to the actual order, discrete logarithm, or size of the group, rather than relative to an upper bound on the group order. |
| |
| Keywords: | |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
|
点击此处可从《Mathematics of Computation》下载全文 |
|
