Generating the greatest common divisor, and limitations of primitive recursive algorithms

DOI10.1007/S10208-002-0061-YzbMath1019.03027OpenAlexW2111425413MaRDI QIDQ1405726

L. P. D. van den Dries

Publication date: 26 August 2003

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-002-0061-y

zbMATH Keywords

greatest common divisorintegers with transcendental ratiolimitations of primitive recursive algorithms

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Applications of model theory (03C98)

Related Items (6)

Henselian elements ⋮ On primitive recursive algorithms and the greatest common divisor function ⋮ A complete characterization of primitive recursive intensional behaviours ⋮ Axiomatization and characterization of BSP algorithms ⋮ Is the Euclidean Algorithm Optimal Among its Peers? ⋮ RRC-fields with small absolute Galois groups

This page was built for publication: Generating the greatest common divisor, and limitations of primitive recursive algorithms