A lower bound for integer greatest common divisor computations

DOI10.1145/103516.103522zbMath0819.11066OpenAlexW2156516305MaRDI QIDQ4302842

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Publication date: 31 August 1995

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/103516.103522

zbMATH Keywords

complexityalgorithmsgreatest common divisorlower boundfloor operationmod operation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items (8)

Fast exponentiation using the truncation operation ⋮ P-RAM vs. RP-RAM ⋮ Does indirect addressing matter? ⋮ Arbitrary sequence RAMs ⋮ Lower bounds on algebraic random access machines ⋮ A problem that is easier to solve on the unit-cost algebraic RAM ⋮ Is the Euclidean Algorithm Optimal Among its Peers? ⋮ Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings

This page was built for publication: A lower bound for integer greatest common divisor computations