Portal de Periódicos da CAPES

The accelerated integer GCD algorithm

1995; Association for Computing Machinery; Volume: 21; Issue: 1 Linguagem: Inglês

10.1145/200979.201042

1557-7295

Kenneth Weber,

Coding theory and cryptography

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.