Multiple GCDs. Probabilistic analysis of the plain algorithm

DOI10.1145/2465506.2465512MaRDI QIDQ2963213zbMATH OpenOpenAlexFDO

Authors Valérie Berthé, Jean Creusefond, Loïck Lhote, Brigitte Vallée

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

generating functionsaverage-case analysisanalytic combinatoricsdynamical analysisGCD algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• Probabilistic analyses of the plain multiple gcd algorithm
• Probabilistic computation of integer polynomial GCDs
• Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
• Gaussian laws for the main parameters of the Euclid algorithms
• Analysis of fast versions of the Euclid algorithm

Cited in

(3)

• Probabilistic analyses of the plain multiple gcd algorithm
• Probabilistic computation of integer polynomial GCDs
• Algorithms and Computation

This page was built for publication: Multiple GCDs. Probabilistic analysis of the plain algorithm

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