2007/09/12 by Niels Christian Møller · 4 citations
Computer Science · #Cryptography and Residue Arithmetic #Coding theory and cryptography #Polynomial and algebraic computation
paper · pdf · doi:10.1090/s0025-5718-07-02017-0
openalex publication_date 2007/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We describe a new subquadratic left-to-right <sc>gcd</sc> algorithm, inspired by Schönhage’s algorithm for reduction of binary quadratic forms, and compare it to the first subquadratic <sc>gcd</sc> algorithm discovered by Knuth and Schönhage, and to the binary recursive <sc>gcd</sc> algorithm of Stehlé and Zimmermann. The new <sc>gcd</sc> algorithm runs slightly faster than earlier algorithms, and it is much simpler to implement. The key idea is to use a stop condition for <sc>hgcd</sc> that is based not on the size of the remainders, but on the size of the next difference. This subtle change is sufficient to eliminate the back-up steps that are necessary in all previous subquadratic left-to-right <sc>gcd</sc> algorithms. The subquadratic <sc>gcd</sc> algorithms all have the same asymptotic running time, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n left-parenthesis log n right-parenthesis squared log log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n (log n)^ 2 log log n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> .