Worst-case analysis of Weber's GCD algorithm

DOI10.1016/S0020-0190(99)00143-XzbMATH Open0999.68266arXiv1311.7369OpenAlexW2041052011MaRDI QIDQ1607009FDOQ1607009

Authors: Christian Lavault, Sidi Mohamed Sedjelmaci 

Publication date: 25 July 2002

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Parallel implementation of the accelerated integer GCD algorithm
• Improvements on the accelerated integer GCD algorithm
• Title not available (Why is that?)
• Two Fast GCD Algorithms

Cited In (1)

• Title not available (Why is that?)

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)