Worst-case analysis of Weber's GCD algorithm

DOI10.1016/S0020-0190(99)00143-XMaRDI QIDQ1607009zbMATHOpenAlexFDO

Authors Christian Lavault, Sidi Mohamed Sedjelmaci

Publication date 25 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.7369

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Number-theoretic algorithms; complexity (11Y16)

Abstract: Recently, Ken Weber introduced an algorithm for finding the $(a,b)$-pairs satisfying $au+bvequiv0pmodk$, with $0<|a|,|b|<sqrtk$, 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.

Recommendations

• Jebelean-Weber's algorithm without spurious factors
• An extended Jebelean-Weber-Sedjelmaci GCD algorithm
• Improvements on the accelerated integer GCD algorithm
• The accelerated integer GCD algorithm
• scientific article; zbMATH DE number 2154292

Cites work

• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 1263309 (Why is no real title available?)
• Improvements on the accelerated integer GCD algorithm
• Parallel implementation of the accelerated integer GCD algorithm
• Two Fast GCD Algorithms

Cited in

(1)

• scientific article; zbMATH DE number 7368168 (Why is no real title available?)

This page was built for publication: Worst-case analysis of Weber's GCD algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1607009)