Open AccessOn acceleration of the k-ary GCD Algorithm
Author(s) -
Ismail F. Amer
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/734/1/012149
Subject(s) - greatest common divisor , acceleration , algorithm , cryptography , divisor (algebraic geometry) , mathematics , public key cryptography , computer science , discrete mathematics , encryption , physics , classical mechanics , operating system
In our paper we analyze a method of acceleration of the k -ary Algorithm of finding the greatest common divisor for long natural numbers. The k -ary GCD algorithm was invented in 1990 by J. Sorenson. We show that a small modification of Sorenson’s Algorithm gives a sufficient acceleration of its work. This is useful for applications using the GCD operation like calculations in finite fields, generation of Cryptography keys etc.