Finding small prime factors
Find a prime divisor p of an integer N; running time can depend on p independently of the bitlength of N.
Heuristic · dependence on smallest factor
Expected small-factor cost, including polynomial arithmetic overhead in log N
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Factoring integers with elliptic curvesAnnals of Mathematics 1987SourceBibTeX / details | Nov 1987 | Lp[1/2, sqrt(2)] (log N)2 | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Expected small-factor cost, including polynomial arithmetic overhead in log N
- Computation
- Classical randomized
- Rigor
- Heuristic
- Instances
- N with smallest prime divisor p
- Cost scale
- L_p[1/2,c] · poly(log N)
- Parameter
- p
- Description
- Expected cost is parameterised by the least prime factor p, not by N. Here L_X[α,c] = exp((c+o(1))(ln X)^α(ln ln X)^(1−α)); all logarithms in this definition are natural.
- Comparison rules
- Expected cost is parameterised by the least prime factor p, not by N. 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, small prime factors, heuristic