Four Integer Factorization Algorithms

2010/03/16 by Carella, N. A.
#FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1003.3261

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.

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