Complexity of finding factors of a number

Question

I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:

1. For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ then add $d$ and $n/d$ to the factor list. Assuming division and appending to a list are $O(1)$ operations for a CPU, this seems to be $O(\sqrt n)$.

The second is to use trial division with prime factors:

1. Sieve all primes up to $\sqrt n$. The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$, so this is $O(\sqrt n \log \log \sqrt n)$?

2. From that list of primes, repeatedly try to divide by $p$ and move on to the next prime if the current prime will not divide evenly anymore. If it does divide, add $p$ and $n/p$ to the factor list. The density of primes is $n / \ln n$, and since primes go up to $\sqrt n$ the supposed time complexity is $O(\sqrt n / \ln \sqrt n)$. However, this does not take into account dividing by primes more than once.

I would like to know if my analysis is correct. It seems counter-intuitive that trial division only takes $O(\sqrt n)$ time, but $n$ is integer size, not input length. I don't think the time complexity of the second method is correct, but I am sure it must be faster than the first (trying primes instead of all numbers within a range).

Answer 1

When you assume that arithmetic operations can be done in time $O(1)$, you're assuming that the numbers you're dealing with have a constant maximum number of digits. That's not a reasonable assumption when you're dealing with factorization: for any number $d$ of digits, there are a fixed, finite number of integers with at most $d$-digits and you can compute their factorizations in constant time.

In reality, the cost of performing arithmetic operations on numbers depends on the size of those numbers. A $b$-bit number can be anything between $0$ and $2^b$ (strictly, $2^b-1$ but that makes no real difference). As such, you're proposing to do $\sqrt{2^b} = 2^{b/2}$ trial divisions to determine the factors of a $b$-bit number. That's not polynomial in the input length; rather, it's polynomial in the magnitude of the numbers represented in the input. So what you have is a "pseudopolynomial-time algorithm". (Another way of looking at this is that your algorithm would run in polynomial time if you represented numbers in unary instead of in binary).

Answer 2

The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model only allows you to perform an operation involving a constant number of bits; and the second model allows you to perform a constant number of arithmetic operations (addition, subtraction, multiplication, division) on registers of length $C\log n$, where $C$ is some constant which you can use but must depend only on the algorithm.

In both models, the division operation itself won't take $O(1)$; indeed, the CPU cannot divide a large number $N$ by a prime $p$ in $O(1)$. So the running time is really $O(\sqrt{N}(\log N)^{O(1)})$ (where $N$ is the number you're trying to factor). We usually don't care about these logarithmic factors, so we use the notation $\tilde{O}(\sqrt{N})$, and we explain that it hides logarithmic factors.

Answer 3

this does not take into account dividing by primes more than once.

But that is exactly why the problem of integer factorization is hard. It can not be decided efficiently (I.e. in polynomial time) how many times each prime occurs in the factorization. Both your analysis' assume each prime occurs either once or not.

In other words. The hardness doesn't lie in the fact of finding out which primes are part of the factorization (i.e. at least once or not) , but how many times each prime occurs (not, once, twice, ...?).

In even other words. You can, using your algorithms, decide which primes will be part of the factorization but now how many times they will occur.

The wikipedia article on this problem is pretty extensive