2
$\begingroup$

Considering a home pc/laptop as machine used (Say typical 2.4 GHz, 16GB RAM, 4 core processor) for running any factorization algorithm. What would be the largest number that could be factored into its prime factors in milli seconds ? rather how many digits such number might have ?

$\endgroup$
  • $\begingroup$ Is the use of GNFS central to the question? If yes, an answer will be hard, for existing GNFS implementations are optimized for factorization efforts requiring 6 to 9 decimal order of magnitude more work than what you consider. Also, it seems more interesting in practice to ask the question prescribing the timeframe, but not the algorithm. Algorithms other than GNFS could well be faster (at least in practice) for numbers factorisable within these constraints. Argument: in GNFS as practiced, a significant portion of the time is spent factoring many auxiliary composites, with other algorithms. $\endgroup$ – fgrieu Dec 7 '15 at 17:46
  • 1
    $\begingroup$ @fgrieu am more interested in time frame than algo used , so rephrased the construction $\endgroup$ – sashank Dec 7 '15 at 17:49
  • 4
    $\begingroup$ A prime number can be factored very fast :) $\endgroup$ – mikeazo Dec 7 '15 at 19:37
  • 1
    $\begingroup$ @mikeazo, only if you can prove its prime-ness very fast... $\endgroup$ – SEJPM Dec 7 '15 at 19:41
  • $\begingroup$ @sashank: following mikeazo's remark, you might want to change the question on the line of: What would be the largest bound such that any lower integer could be factored into its prime factors in millseconds (or perhap: most lower integer) $\endgroup$ – fgrieu Dec 8 '15 at 7:59
3
$\begingroup$

We need a little bit of clarification or state some reasonable assumptions. For instance, 2^n can be factored very quickly for ludicrously large values of n. I assume that's not what you're asking. You're also probably not looking for a rigorous worst case, as that depends on the algorithms and implementations. Perhaps time taken for non-trivial random inputs.

"This can be yours for only pennies a day*" (*: approximately 64,000). By milliseconds, I'm assuming you mean something in the range 1-999.

On my computer, using Pari/GP or Perl/ntheory, looking at average time, 20 digit semiprimes take about 1ms, random input about 1/3 of that. Random input is about 10ms at 31 digits, semiprimes at 26-27 digits. Random input is about 100ms at 51 digits, semiprimes at about 38-39 digits. Random input hits 1000ms at ~60 digits.

Those programs are handy, but certainly not state of the art for factoring. Among other things, they only use 1 core. Something like yafu would probably be a better benchmark, as its SIQS is extremely fast and uses multiple cores. Last time I checked, the QS/NFS crossover was in the 100-110 digit range, and well over 1000 milliseconds.

As for algorithm, after simple things like trial division and maybe even a tiny bit of Rho/Brent, we're probably looking at ECM or QS. P-1 may be in there as well. SQUFOF is very nice for 64-bit inputs, but that's sub-millisecond timing for good implementations, and it doesn't work so well for larger inputs.

This is pretty old, but back in 2009 I did some tests on various factoring code. On page 18 of this presentation it shows the number of digits possible for factoring semiprimes in 1 second to be 55 digits with yafu. That was a Q6600, and yafu's latest code might be faster as well.

$\endgroup$
  • $\begingroup$ I second that SQUFOF is to consider; it think I remember that it has been used with success in the sieving phase of some optimized MPQS/GNFS factorization code, at least by Robert D. Silverman (aka Pubkeybreaker). $\endgroup$ – fgrieu Dec 8 '15 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.