Worst-Case Analysis of Weber's Algorithm

Christian Lavault, Sidi Mohamed Sedjelmaci

Recently, Ken Weber introduced an algorithm for finding the $(a,b)$-pairs satisfying $au+bv\equiv 0(\mathrm{mod}k)$, with $0<|a|,|b|<\sqrt{k}$, where $(u,k)$ and $(v,k)$ are coprime. It i…