In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes. The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n. For example: suppose I want to factor the number 247 (ie 13 * 19).

To do this I can just check all the numbers (exhaustive search) below $$ \sqrt{247} \approx 16$$ to see if they divide 247.

The General number field sieve has a runtime of $$ \approx \exp \sqrt[3]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3}, $$

So calculating the GNFS runtime... $$ \approx \exp \sqrt[3]{\frac{64}{9}} (\ln 247)^{1/3} (\ln \ln 247)^{2/3}, $$ $$ \approx \exp \sqrt[3]{\frac{64}{9}} (5.5)^{1/3} (\ln 5.5)^{2/3}, $$ $$ \approx \exp \sqrt[3]{\frac{64}{9}} (5.5)^{1/3} (1.7)^{2/3}, $$ $$ \approx \exp (1.9 * 1.8 * 1.4), $$ $$ \approx \exp (4.87) \approx 120 $$

This is obviously bigger than 16. What am I missing here?

  • $\begingroup$ This is somewhat tangential, but practical implementations generally don't use GNFS until ~ 100 digits, as it is slower than other methods below that point. Full trial division (exhaustive search) typically beats other methods with input under 6 or 7 digits (until 1M or so). $\endgroup$
    – DanaJ
    Jul 19 '16 at 20:22

First of all, the number 120 that you got is completely meaningless. There is a scaling factor that can only be determined experimentally. Even worse, there are lower order factors which are probably very significant for such small numbers. Finally, the running time you quote is heuristic – it's just an educated guess.

You are correct that GNFS is a lot less efficient than trivial methods for small numbers. That's why you don't use it for small numbers. The better asymptotics kick in only for large enough numbers.

  • 1
    $\begingroup$ Even for larger numbers, you would first check for some small prime factors. You would calculate: How much does it calculate if n is divisible by p (for some small p). What is the probability that it is divisible? (That would be 1/p). How much time do I save if I make use of the fact that n is divisible by p? And if the expected total time is smaller if you test divsibility by p, then that's what you test first. $\endgroup$
    – gnasher729
    Jul 21 '16 at 0:07

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.