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.
1 variants · 1 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
Small-factor IFPHeuristic · dependence on smallest factorClassical randomized · HeuristicExpected small-factor cost, including polynomial arithmetic overhead in log NN with smallest prime divisor p11.414214