# General number field sieve is slower then exhaustive search for 'small' numbers?

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{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3},$$

So calculating the GNFS runtime... $$\approx \exp \sqrt{\frac{64}{9}} (\ln 247)^{1/3} (\ln \ln 247)^{2/3},$$ $$\approx \exp \sqrt{\frac{64}{9}} (5.5)^{1/3} (\ln 5.5)^{2/3},$$ $$\approx \exp \sqrt{\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?

• 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). Jul 19 '16 at 20:22