Algorithms for the Multiplication Table Problem

zbMath1492.11170arXiv1908.04251MaRDI QIDQ3390067

David Purdum, Richard P. Brent, Jonathan Webster, Carl B. Pomerance

Publication date: 24 March 2022

Full work available at URL: https://arxiv.org/abs/1908.04251

zbMATH Keywords

Monte Carlo algorithmmultiplication table problemsub-quadratic algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Other combinatorial number theory (11B75)

Uses Software

• Magma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a problem of Oppenheim concerning Factorisatio Numerorum
• Probabilistic algorithm for testing primality
• Sur la structure de la suite des diviseurs d'un entier. (On the structure of the séquence of divisors of an integer)
• Grandes déviations pour certaines fonctions arithmétiques. (Large deviations for certain arithmetic functions)
• On the number of restricted prime factors of an integer. I
• Riemann's hypothesis and tests for primality
• The Magma algebra system. I: The user language
• Primality testing with Gaussian periods
• PRIMES is in P
• Generating random factored numbers, easily
• The distribution of integers with a divisor in a given interval
• Improved error bounds for the Fermat primality test on random inputs
• How to Generate Factored Random Numbers
• The Area-Time Complexity of Binary Multiplication
• Detecting perfect powers in essentially linear time
• Further investigations with the strong probable prime test
• An improved sieve of Eratosthenes

This page was built for publication: Algorithms for the Multiplication Table Problem