1995/03/01 by Kenneth Weber · 3 citations
Computer Science · #Numerical Methods and Algorithms #Polynomial and algebraic computation #Coding theory and cryptography
paper · pdf · doi:10.1145/200979.201042
openalex publication_date 1995/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
Since the greatest common divisor (GCD) of two integers is a basic arithmetic operation used in many mathematical software systems, new algorithms for its computation are of widespread interest. The accelerated integer GCD algorithm discussed here is based on a reduction step proposed by Sorenson ( k -ary reduction), coupled with the dmod operation similar to Norton's smod. Some practical limitations of Sorenson's reduction have been eliminated. Worst-case complexity is still O (n 2 ) for n -bit input, but actual implementations given input about 4096 bits long perform over 5.5 times as fast as the binary GCD on one computer architecture having a multiply instruction. Independent research by Jebelean points to the same conclusions.