Integer factorization
Find the prime factorization of a composite integer N; distinguish input length log N from the integer N itself.
General integers · proven randomized · L(1/2)
Unconditional expected-time bounds; randomness allowed
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | A rigorous time bound for factoring integersJournal of the American Mathematical Society 1992SourceBibTeX / details | Jul 1992 | LN[1/2, 1] | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Unconditional expected-time bounds; randomness allowed
- Computation
- Classical randomized
- Rigor
- Provable
- Instances
- arbitrary composite integers
- Cost scale
- L_N[1/2,c]
- Parameter
- N
- Description
- Rigorously analysed randomized integer factorization. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Rigorously analysed randomized integer factorization. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural. 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
- unconditional, randomized, class groups