Multiple GCDs. Probabilistic analysis of the plain algorithm

DOI10.1145/2465506.2465512zbMATH Open1360.68972OpenAlexW2101431603MaRDI QIDQ2963213FDOQ2963213

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

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

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)

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)