On Schönhage's algorithm and subquadratic integer gcd computation
From MaRDI portal
Publication:5429518
DOI10.1090/S0025-5718-07-02017-0zbMath1165.11003WikidataQ55899112 ScholiaQ55899112MaRDI QIDQ5429518
Publication date: 30 November 2007
Published in: Mathematics of Computation (Search for Journal in Brave)
11Y16: Number-theoretic algorithms; complexity
11A05: Multiplicative structure; Euclidean algorithm; greatest common divisors
Related Items
An O(M(n) logn) Algorithm for the Jacobi Symbol, Phragmén's voting methods and justified representation, Complexity of computation in finite fields, Scheduling results applicable to decision-theoretic troubleshooting, Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms, Towards faster polynomial-time lattice reduction, Holonomic gradient method for two-way contingency tables, Statistics of Different Reduction Types of Fermat Curves, Faster deterministic integer factorization, ALGORITHMS TO IDENTIFY ABUNDANTp-SINGULAR ELEMENTS IN FINITE CLASSICAL GROUPS, A multimodular algorithm for computing Bernoulli numbers, The Erdős–Moser equation $1^{k}+2^{k}+\dots+(m-1)^{k}=m^{k}$ revisited using continued fractions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
- Computational problems associated with Racah algebra
- Fast computation of continued fraction expansions.
- Two Fast GCD Algorithms
- The accelerated integer GCD algorithm
- Acceleration of Euclidean algorithm and extensions
- Algorithmic Number Theory
- Euclid's Algorithm for Large Numbers