A modular integer GCD algorithm |
| |
Authors: | Kenneth Weber Vilmar Trevisan Luiz Felipe Martins |
| |
Affiliation: | aDepartment of Computer Science and Information Systems, Mount Union College, Alliance, OH 44601, USA;bInstituto de Matemática, Universidade Federal do Rio Grande do Sul, Porto Alegre, RS 91509-900, Brazil;cDepartment of Mathematics, Cleveland State University, Cleveland, OH 44115, USA |
| |
Abstract: | 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 . 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. |
| |
Keywords: | Integer GCD Modular representation Residue arithmetic Parallel algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|