Integer factorization
Find the prime factorization of a composite integer N; distinguish input length log N from the integer N itself.
General integers · heuristic · L(1/3)
General-purpose factorization; no special low-degree polynomial form supplied
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Modifications to the Number Field SieveJournal of Cryptology 1993SourceBibTeX / detailsmultiple number fields theoretical asymptotics | Mar 1993 | LN[1/3, (92+26 sqrt(13))1/3/3] | Not extracted from the source | PublishedSource checked |
| 2 | Factoring integers with the number field sieveThe Development of the Number Field Sieve 1993SourceBibTeX / details | 1993 | LN[1/3, (64/9)1/3] | Not extracted from the source | PublishedSource checked |
| 3 | The number field sieveSTOC 1990SourceBibTeX / details | 1990 | LN[1/3, 32/3] | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- General-purpose factorization; no special low-degree polynomial form supplied
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- general composite integers
- Cost scale
- L_N[1/3,c]
- Parameter
- N
- Description
- Heuristic subexponential general-purpose factoring bounds. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Heuristic subexponential general-purpose factoring bounds. 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
- number field sieve, general integers, heuristic