Runtime complexity of a brute force factoring algorithm? (in terms of bits)

Question

Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the asymptotic running time for the brute force factoring algorithm?

Answer 1

It is $(\lfloor \sqrt{N} \rfloor-1) \cdot O(n^2) = O(\sqrt{N} \log^2 N) = O(2^{\frac{n}{2}} n^2)$ in the worst case: for each of the $O(\sqrt{N})$ choices of the dividend you perform a division of two numbers of at most $n$ bits.

(When you factor $N$ you might repeat some of the divisions, but these can be safely ignored since there can be at most $n$ repeated divisions, for a total complexity of $O(n^3) = o(2^{\frac{n}{2}} n^2)$.)

Notice that this is the best bound we can get for your question under reasonable hypotheses. Indeed, if the complexity of dividing two n-bit numbers is also $\Omega(n^2)$ and you apply the brute-force algorithm on a prime $N$:

$$ \sum_{i=2}^{\lfloor \sqrt{N} \rfloor} T(\log N, \log i) \ge \sum_{i=\lceil \sqrt{N}/2 \rceil}^{\lfloor \sqrt{N} \rfloor} T\left(\frac{1}{2}\log N - 1, \frac{1}{2}\log N - 1\right) = \Omega(\sqrt N) \cdot \Omega(\log^2 N) = \Omega(\sqrt{N} \log^2 N), $$

where $T(i,j)$ is the time it takes to divide a $i$-bit integer by a $j$-bit integer and I am assuming that $T(i,j)$ is non-decreasing w.r.t. $i$ and $j$.

Answer 2

Dividing a 128 bit number by a 64 bit number can be done in constant time. If N is a prime that doesn't fit into 128 bit then the algorithm won't finish in your life time :-) Dividing two n bit integers can be done in O (n log n) for large n.

But assuming that you use brute force division that does use $O (n^2)$ operations for a division, then you should just ask yourself how many divisions you will perform in the worst case (N is prime or the product of two primes close to $N^{1/2}$), and multiply by the number of operations per division.

You also need to be a bit more careful with the description of your algorithm: 121 is not divisible by any integer between 2 and the square root of 121. Similar, 86 is not divisible by any integer between 2 and the square root of 86.