2
$\begingroup$

There are many ways of factorization available, e.g. trial division, Pollard rho, elliptic curve factorisation, the general number field sieve. But for what ranges of numbers are such algorithms appropriate? Obviously, using the general number field sieve to factor 15 is using a sledgehammer to crack a walnut, and using trial division to factorise a large Mersenne prime would take longer than the age of the universe, but at what points should one stop using one algorithm and use another?

My current understanding is as follows:

$\underline{2 \leq n \leq 100000}$

Use trial division

$\underline{10^5 \leq n \leq 10^{10}}$

Use Pollard rho, or Pollard $p-1$

$\underline{10^{10} \leq n \leq 10^{20}}$

Elliptic curve factorisation

$\underline{10^{20} \leq n}$

The general number field sieve

Of course, this is all very dependent of your algorithm implementation, but roughly speaking, is this analysis correct, or should I be considering other special subcases/using other algorithms? If I list a bunch of algorithms, like the ones above, we can give their known computational complexities, but in practise, when do they start to outperform each other?

$\endgroup$
  • $\begingroup$ Regarding your last sentence, that's roughly what I was trying to get at with this question. I'll try and rephrase it as such. $\endgroup$ – MadMonty Dec 23 '15 at 1:33
  • 1
    $\begingroup$ You'll always want to do a little trial division. Under 64 bits it's a bit more complicated for optimal performance, but consider SQUFOF. p-1 and ecm are good at all sizes to find small factors, and all you need for ~40 digits. QS is good for roughly 30 to 100 digits. GNFS is quite a bit more complicated than the rest, and typically the crossover with QS will be 90-110 digits. While it's quite old now, I wrote up some practical experiments with crossover graphs at diamond.boisestate.edu/~liljanab/BOISECRYPTFall09/Jacobsen.pdf. $\endgroup$ – DanaJ Jan 3 '16 at 8:25
0
$\begingroup$

Well it is very dependent on what hardware you have, but two categories of algorithm need to be distinguished.

Deterministic

These are algorithms that will, eventually, always find the factors. They will systematically search for them. At one end you have trial division and at the other GNFS.

Probabilistic

These are algorithms that are designed to be quick for most numbers, but are never guaranteed to find a solution. They might run forever, for longer than trial division, and never find a solution. In practice they'll probably work faster than that, but they're typically not fast for the most difficult factoring problems ( products of large primes ).

Special Numbers

There are some algorithms for special types of numbers. For example, there are algorithms for checking if a Fermat number is prime. These allow the discovery of factors that are absolutely enormous, well beyond what would be workable with even GNFS.

Typically you would employ basic trial division "for a while", then move to a good probabilistic method "for a while", then move to something heavyweight like GNFS when your patience is exhausted.

Implementation difficulty

Another factor in deciding what to use is how difficult it is to code, bug free, maintain and refine an algorithm.

Another practical consider is that complex, highly tuned algorithms like GNFS are very difficult to write. If a library is available, it may, for particular purposes, be better to use something pre-packaged that doesn't require you to make your entire career factoring theory just to debug it, than try and take on the task of maintaining your own.

There is no one way to build an approach.

$\endgroup$

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.