Integer factorization
Find the prime factorization of a composite integer N; distinguish input length log N from the integer N itself.
General integers · proven deterministic
Unconditional deterministic bit complexity
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | An exponent one-fifth algorithm for deterministic integer factorisationMathematics of Computation 2021SourceBibTeX / details | 12 Oct 2020 | N1/5+o(1) bit operations | Not extracted from the source | PublishedSource checked |
| 1 | A log-log speedup for exponent one-fifth deterministic integer factorisationMathematics of Computation 2022SourceBibTeX / details | 24 May 2021 | O(N1/5 (log N)16/5 / (log log N)3/5) bit operations | Not extracted from the source | PublishedSource checked |
| 3 | A time-space tradeoff for Lehman's deterministic integer factorization methodMathematics of Computation 2021SourceBibTeX / details | 30 Jun 2020 | N2/9+o(1) bit operations | Not extracted from the source | PublishedSource checked |
| 4 | Faster deterministic integer factorizationMathematics of Computation 2014SourceBibTeX / details | 10 Jan 2012 | O(Mint(N1/4 log N) / sqrt(log log N)) | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Unconditional deterministic bit complexity
- Computation
- Classical deterministic
- Rigor
- Provable
- Instances
- arbitrary positive integers
- Cost scale
- N^{c+o(1)}
- Parameter
- N
- Description
- Exponent in the integer N itself, not in log N. Ties in c may still differ by logarithmic factors.
- Comparison rules
- Exponent in the integer N itself, not in log N. Ties in c may still differ by logarithmic factors. Only compare entries with this cost scale, input domain and computational model. Polynomial and quasi-polynomial expressions without an extracted scalar are not ranked.
- Tags
- deterministic, unconditional, bit complexity