Complexity of finding factors of a number

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

• 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:

-
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)$?

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

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

StackExchange Computer Science Q#55998, answer score: 6