Half-GCD
المؤلف:
Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D
المصدر:
Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1987.
الجزء والصفحة:
...
19-8-2020
1220
Half-GCD
Given integers 
and 
with close to 
bits each, the half-GCD of 
and 
is a 
matrix
with determinant equal to 
or 1 such that 
and 
, where 
and 
each have a number of bits close to 
.
The half-GCD results by performing roughly half the Euclidean algorithm for computing the greatest common divisor 
. There is an efficient algorithm for computing the half-GCD of two large numbers which, when applied recursively, allows the greatest common divisor to be computed faster than using the Euclidean algorithm.
REFERENCES:
Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1987.
Sedjelmaci, S. M. "The Accelerated Euclidean Algorithm." Poster talk presented at ISAAC 2004, July 4-7, University of Cantabria, Santander, Spain. https://www.risc.uni-linz.ac.at/issac2004/poster-abstracts/abstract27.pdf.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
