| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428220 | Information Processing Letters | 2007 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
