Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 7 down vote favorite

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?

Additional information

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)

share|improve this question
@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 :) – rm -rf♦ Sep 29 '12 at 18:24
@rm-rf - But do you see the same difference? – stevenvh Sep 29 '12 at 18:24
5  
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
1  
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
show 5 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.