Integer factorization
Find the prime factorization of a composite integer N; distinguish input length log N from the integer N itself.
Special form · heuristic · L(1/3)
N = r^e ± s with r and |s| bounded; polynomial representation supplied
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | The number field sieveSTOC 1990SourceBibTeX / details | 1990 | LN[1/3, (32/9)1/3] | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- N = r^e ± s with r and |s| bounded; polynomial representation supplied
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- special-form composites
- Cost scale
- L_N[1/3,c]
- Parameter
- N
- Description
- Factoring special-form integers; the algebraic representation is an essential input restriction. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Factoring special-form integers; the algebraic representation is an essential input restriction. 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
- special number field sieve, structured integers, heuristic