A quantum algorithm for computing the Carmichael function

2021/11/03 by Juan Carlos García-Escartín, Garcia-Escartin, Juan Carlos
Computer Science · #Coding theory and cryptography #FOS: Mathematics #FOS: Physical sciences #Number Theory (math.NT) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2111.02488

openalex publication_date 2021/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Quantum computers can solve many number theory problems efficiently. Using the efficient quantum algorithm for order finding as an oracle, this paper presents an algorithm that computes the Carmichael function for any integer N with a probability as close to 1 as desired. The algorithm requires O((log n )³n³) quantum operations, or O(loglog n (log n)⁴ n²) operations using fast multiplication. Verification, quantum optimizations and applications to RSA and primality tests are also discussed.

Citations

• Approximate formulas for some functions of prime numbers
• Theorie des Fonctions Numeriques Simplement Periodiques

Related

• Carmichael Numbers on a Quantum Computer
• Quantum Algorithms
• Quantum Algorithms
• On the Complexity of Searching Maximum of a Function on a Quantum Computer
• Basic Quantum Algorithms