Deterministic Integer Factorization Algorithms

2013/08/05 by N. A. Carella, Carella, N. A.
Computer Science · Engineering · #11Y51 #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Primary 11Y05 #Secondary 11Y16 #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1308.2891

openalex publication_date 2013/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A new integer deterministic factorization algorithm, rated at arithmetic operations to O(N^1/6+ε) arithmetic operations, is presented in this note. Equivalently, given the least (log N)/6 bits of a factor of the balanced integer N = pq, where p and q are primes, the algorithm factors the integer in polynomial time O(log(N)^c), with c ≥ 0 constant, and ε > 0 an arbitrarily small number. It improves the current deterministic factorization algorithm, rated at arithmetic operations to O(N^1/5+ε) arithmetic operations.

Related

• A deterministic algorithm for integer factorization
• Four Integer Factorization Algorithms
• Note on Integer Factoring Methods IV
• Note Integer Factoring Methods III
• Faster deterministic integer factorization