One way to find a nontrivial divisor of n is Fermat’s factorization method:
Suppose that we have an odd number n > 1 which we know is composite and not a perfect square.
- Calculate $\lfloor \sqrt{n} \rfloor$, the largest integer less than or equal to √n.
- Letting a run over $\lfloor \sqrt{n} \rfloor$+ 1, $\lfloor \sqrt{n} \rfloor$+ 2, $\lfloor \sqrt{n} \rfloor$+ 3, ··· in turn:
- Calculate $\sqrt{a^2-n}$ and see whether it is an integer;
- Once we have $\sqrt{a^2-n}=b$ for some integer b, we know that $n = a^2 −b^2 = (a −b)(a + b)$, so we finish.
In assessing the time taken by Fermat’s method, it is natural to compare it against “reverse trial division”, where instead of testing divisibility of n by 2,3,4,···, we test divisibility of n by $\lfloor \sqrt{n} \rfloor, \lfloor \sqrt{n} \rfloor -1, \lfloor \sqrt{n} \rfloor-2,$ ···.
Explain why there are some values of n for which Fermat’s method would find a nontrivial divisor more quickly than reverse trial division.
Attempt
Let g(n) denote the largest divisor of n which is less than $\sqrt{n}$, and let $h(n) = \frac{n}{g(n)}$.
Fermat’s method will try exactly $$\frac{1}{2}(g(n) + h(n))-\lfloor \sqrt{n} \rfloor$$ values of a before finishing, see Fermat method for factorization - upper bound
“reverse trial division” takes $\lfloor \sqrt{n} \rfloor - g(n) + 1$ steps to find g(n)