1998/01/01 by Edlyn Teske · 1 citation
Computer Science · Mathematics · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Coding theory and cryptography #Algorithm #Annotation #Computer science #Mathematics #Artificial intelligence
paper · pdf · doi:10.1090/s0025-5718-98-00968-5
openalex publication_date 1998/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartRoot n EndRoot right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(√ n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denoting the group order), and we explicitly determine the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O"> <mml:semantics> <mml:mi>O</mml:mi> <mml:annotation encoding="application/x-tex">O</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.