# Does Mathematica use the Elliptic Curve Method (ECM) in FactorInteger[]?

I'm not a mathematician, and I'm not even going to pretend that I understand anything of the ECM. But I know it can be a fast method for factorization.

I benchmarked the factorization of $$798645312654798147285393218574111453126547981472185139328574111781$$

by Mathematica against this online applet, where the applet was 75 % faster (16 seconds versus 65 for Mathematica). Other factorizations were up to 6 times faster.

Does Mathematica use ECM for factorization of certain cases? If yes, how comes performance is so different?

We can investigate in the above problem by calling FactorInteger[..,Automatic] on the large number:

FactorInteger[
798645312654798147285393218574111453126547981472185139328574111781,
Automatic] // AbsoluteTiming

(* {5.647210,
{{61, 1}, {67, 1}, {74729, 1},
{2614930428035201342411278280525965452621044417207937542347, 1}}}
*)


This takes only a fraction of the time, but finds only simple factors. So it seems the rest of the time Mathematic tries to factor the last big number. And in fact:

FactorInteger[2614930428035201342411278280525965452621044417207937542347] // AbsoluteTiming

(*
{43.717204,
{{97913387938680010938335707, 1}, {26706566722753457593818813677521, 1}}}
*)


(feel free to edit tags if needed)

-
@rm-rf Java applets use your own PC to operate, they are client-side technology and require Java to be installed on your machine. – Leonid Shifrin Sep 29 '12 at 18:23
@LeonidShifrin Ok, in that case I stand corrected :) – R. M. Sep 29 '12 at 18:24
@rm-rf - But do you see the same difference? – stevenvh Sep 29 '12 at 18:24
FactorInteger uses ECM and several other methods. Timings can vary for any of several reasons. I'll name the ones that come to mind. (1) Time spent on other methods earlier, e.g. Pollard p-1 and rho. (2) Weaker tuning and/or implementation of ECM. (3) Possibility that ECM is parallelized in the other implementation (it is not in Mathematica). (4) The heuristics might be such that ECM simply fails for this example and we move on to the quadratic sieve. Item (1) is not the issue for the example posted. Item (4) is implicated. Items (2) and (3) might also be involved here. – Daniel Lichtblau Sep 29 '12 at 20:17
reference.wolfram.com/mathematica/tutorial/… says FactorInteger switches between trial division, Pollard $p-1$, Pollard rho, elliptic curve, and quadratic sieve algorithms. – ziyuang Sep 30 '12 at 5:39