A deterministic algorithm for integer factorization

DOI10.1090/MCOM3037MaRDI QIDQ2796032zbMATH OpenOpenAlexFDO

Authors Ghaith A. Hiary

Publication date 23 March 2016

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycontinued fractionsdeterministic algorithminteger factorization

Mathematics Subject Classification ID

Factorization; primality (11A51) Continued fractions (11A55) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16)

Abstract: A deterministic algorithm for factoring $n$ using $n^{1/3+o(1)}$ bit operations is presented. The algorithm tests the divisibility of $n$ by all the integers in a short interval at once, rather than integer by integer as in trial division. The algorithm is implemented.

Review text

This paper proposes a new deterministic method for the factorization of an integer \(n\). It can be viewed as an improvement of the naive trial division method, since it can test the divisibility of \(n\) by all the integers in a short interval in basically one step. In fact the algorithm test the equation \(n/(x+h)\equiv 0 \bmod 1\), with \(h\in [-H,H]\).NEWLINENEWLINEThe Introduction gives a brief summary of the existing deterministic methods of factorization and Section 2 gives the proposed method (Algorithm 1) and its complexity (Theorem 2.1). As many other methods this complexity is \(n^{1/3+ o(1)}\). The author points out that this algorithm is mainly of theoretical interest. There are already probabilistic methods that far outperform it in practice and in ``heuristically subexponential time.NEWLINENEWLINESection 3 is devoted to the proof of Theorem 2.1 and Section 4 shows an implementation of Algorithm 1 in \texttt{Mathematica} and discusses some computational issues.

Recommendations

• Faster deterministic integer factorization
• An exponent one-fifth algorithm for deterministic integer factorisation
• An explicit factorization algorithm
• A deterministic algorithm for computing divisors in an interval
• An integer factoring algorithm based on elliptic divisibility sequences
• A Rigorous Time Bound for Factoring Integers
• scientific article; zbMATH DE number 1113841
• Schemes for deterministic polynomial factoring
• An introspective algorithm for the integer determinant
• Integer factoring using small algebraic dependencies

Cites work

• Divisors in Residue Classes
• Efficient Factoring Based on Partial Information
• Factoring Large Integers
• Faster deterministic integer factorization
• Finding a small root of a bivariate integer equation; factoring with high bits known
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Number-theoretic algorithms in cryptography. Transl. from the Russian by A. Martsinkovsky
• Some results on computational complexity
• The distribution of solutions to XN=N a with an application to factoring integers
• The higher arithmetic. An introduction to the theory of numbers. Editing and additional material by James H. Davenport.
• Turning Euler's Factoring Method into a Factoring Algorithm

Cited in

(25)

• A deterministic algorithm for finding \(r\)-power divisors
• On oracle factoring of integers
• A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
• An integer factoring algorithm based on elliptic divisibility sequences
• Faster deterministic integer factorization
• A one line factoring algorithm
• Sufficient conditions for factoring a class of large integers
• A babystep-giantstep method for faster deterministic integer factorization
• A deterministic version of Pollard's p-1 algorithm
• scientific article; zbMATH DE number 1113841 (Why is no real title available?)
• A design for a number theory package with an optimized trial division routine
• scientific article; zbMATH DE number 2068209 (Why is no real title available?)
• A deterministic algorithm for computing divisors in an interval
• Turning Euler's Factoring Method into a Factoring Algorithm
• An exponent one-fifth algorithm for deterministic integer factorisation
• A time-space tradeoff for Lehman's deterministic integer factorization method
• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• The South Caicos factoring algorithm
• Deterministic factorization of sums and differences of powers
• The Dixon algorithm: properties, modifications, and applications
• Computing prime divisors in an interval
• A reduction of integer factorization to modular tetration
• Analysis of some elementary algorithms for prime factorization
• A generalization of Lehman's method
• An algorithm for computing simple \(k\)-factors

Describes a project that uses

Uses Software

• Mathematica

This page was built for publication: A deterministic algorithm for integer factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796032)