Integer factorization
Find the prime factorization of a composite integer N; distinguish input length log N from the integer N itself.
6 variants · 13 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
IFPGeneral integers · proven deterministicClassical deterministic · ProvableUnconditional deterministic bit complexityarbitrary positive integers40.2 IFPGeneral integers · heuristic · L(1/3)Classical · HeuristicGeneral-purpose factorization; no special low-degree polynomial form suppliedgeneral composite integers31.901884 IFPQuantum · polynomial-time expressionsQuantum · source dependentLogical circuits plus classical post-processing; conditional and unconditional claims labelled separatelygeneral composite integers3— IFPGeneral integers · heuristic · L(1/2)Classical · HeuristicWorst dependence on N, including balanced semiprimesgeneral composite integers11 IFPGeneral integers · proven randomized · L(1/2)Classical randomized · ProvableUnconditional expected-time bounds; randomness allowedarbitrary composite integers11 IFPSpecial form · heuristic · L(1/3)Classical · HeuristicN = r^e ± s with r and |s| bounded; polynomial representation suppliedspecial-form composites11.526286