Jebelean-Weber's algorithm without spurious factors |
| |
Authors: | Sidi Mohamed Sedjelmaci |
| |
Affiliation: | LIPN, CNRS UPRES-A 7030, Université Paris-Nord, Av. J.B.-Clément, 93430 Villetaneuse, France |
| |
Abstract: | Tudor Jebelean and Ken Weber introduced an algorithm for finding (a,b)-pairs satisfying au+bv≡0 (mod k), with . It is based on Sorenson's “k-ary reduction”. This algorithm does not preserve the GCD and its related GCD algorithm has an O(n2) time bit complexity in the worst case. We present a modified version which avoids this problem. We show that a slightly modified GCD algorithm has an O(n2/logn) running time in the worst case, where n is the number of bits of the larger input. |
| |
Keywords: | Integer greatest common divisor (GCD) Parallel GCD algorithm Extended GCD algorithm Algorithms Analysis of algorithms Number theory |
本文献已被 ScienceDirect 等数据库收录! |
|