کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657021 | 687197 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A modular integer GCD algorithm
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A modular integer GCD algorithm A modular integer GCD algorithm](/preview/png/9657021.png)
چکیده انگلیسی
This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111-116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111-122] when U and V are close to the same size, that replaces U by (UâbV)/p, where p is one of the prime moduli and b is the unique integer in the interval (âp/2,p/2) such that bâ¡UVâ1(modp). When the algorithm is executed on a bit common CRCW PRAM with O(nlognlogloglogn) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/logn) time on the same number of processors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 54, Issue 2, February 2005, Pages 152-167
Journal: Journal of Algorithms - Volume 54, Issue 2, February 2005, Pages 152-167
نویسندگان
Kenneth Weber, Vilmar Trevisan, Luiz Felipe Martins,