A deterministic algorithm for integer factorization
From MaRDI portal
Abstract: A deterministic algorithm for factoring using bit operations is presented. The algorithm tests the divisibility of by all the integers in a short interval at once, rather than integer by integer as in trial division. The algorithm is implemented.
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
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)
