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

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?

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$$.

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.

• I'm pretty sure 121 is divisible by $11 \le \lfloor \sqrt{121} \rfloor=11$ and 86 is divisible by $2 \le \lfloor \sqrt{86} \rfloor = 9$. – Steven Sep 22 '19 at 21:12