Recently, Ken Weber introduced an algorithm for finding the $(a,b)$-pairs satisfying $au+bv\equiv 0\pmod{k}$, with $0<|a|,|b|<\sqrt{k}$, where $(u,k)$ and $(v,k)$ are coprime. It is based on Sorenson's and Jebelean's ''$k$-ary reduction'' algorithms. We provide a formula for $N(k)$, the maximal number of iterations in the loop of Weber's GCD algorithm.
Publié le : 1999-07-05
Classification:
Number theory,
Integer greatest common divisor (GCD),
Complexity analysis,
Number theory.,
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC],
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC],
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00911130,
author = {Lavault, Christian and Sedjelmaci, Sidi Mohamed},
title = {Worst--Case Analysis of Weber's Algorithm},
journal = {HAL},
volume = {1999},
number = {0},
year = {1999},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00911130}
}
Lavault, Christian; Sedjelmaci, Sidi Mohamed. Worst--Case Analysis of Weber's Algorithm. HAL, Tome 1999 (1999) no. 0, . http://gdmltest.u-ga.fr/item/hal-00911130/