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/2)
Worst dependence on N, including balanced semiprimes
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Factoring integers with elliptic curvesAnnals of Mathematics 1987SourceBibTeX / details | Nov 1987 | LN[1/2, 1] | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Worst dependence on N, including balanced semiprimes
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- general composite integers
- Cost scale
- L_N[1/2,c]
- Parameter
- N
- Description
- Historical L(1/2) scale, kept separate from L(1/3). Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Historical L(1/2) scale, kept separate from L(1/3). 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
- elliptic curve method, balanced factors, heuristic