Four Integer Factorization Algorithms

2010/03/16 by N. A. Carella, Carella, N. A.
Computer Science · Engineering · Mathematics · #Algorithm #Coding theory and cryptography #Combinatorics #Computational complexity theory #Computer science #Constant (computer programming) #Cryptography and Residue Arithmetic #Discrete mathematics #Dixon's factorization method #Exponential function #Exponential time hypothesis #FOS: Mathematics #Factorization #Factorization of polynomials #Focus (optics) #Heuristic #Integer (computer science) #Integer factorization #Logarithm #Mathematical optimization #Mathematics #Number Theory (math.NT) #Physics #Polynomial #Running time #Time complexity #graph theory and CDMA systems #math.NT

paper · pdf · doi:10.48550/arxiv.1003.3261

published in arXiv (Cornell University) (Cornell University) · Improvements in Theorem 14, 12 Pages

openalex publication_date 2010/03/16 · arxiv created 2010/08/31 · arxiv updated 2010/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The theoretical aspects of four integer factorization algorithms are discussed in details in this note. The focus is on the performances of these algorithms on the subset of hard to factor balanced integers N = pq, p < q < 2p. The running time complexity of these algorithms ranges from deterministic exponential time complexity O(N^(1/2)) to heuristic and unconditional logarithmic time complexity O((log N)^c), c > 0 constant.

Citations

• A Course in Computational Algebraic Number Theory
• Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities

Related

• Note on Integer Factoring Methods IV
• Note on Integer Factoring Algorithms II
• Note Integer Factoring Methods III
• Deterministic Integer Factorization Algorithms
• Digit Polynomials and their application to integer factorization