0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Steven Sep 22 '19 at 21:12

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.