3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is there a correction factor for repeatedly dividing primes? I imagine it would not be very significant, so the second would require about $O(2^{b/2} / \ln 2^{b/2})$ $\endgroup$ – qwr Apr 15 '16 at 21:35
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "...arithmetic operations on words of size $O(log (n))$" I once wrote something similar on a exam as a side note and my TA subtracted a point for it :(. $\endgroup$ – Auberon Apr 16 '16 at 9:49
-3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ That's false. It is conjectured that factoring numbers which are product of two distinct primes is the hardest case. In contrast, for any given prime it is very easy to find out how many times it divides the number. Just keep dividing the number by the prime until you get a non-zero remainder. $\endgroup$ – Yuval Filmus Apr 15 '16 at 20:56
  • $\begingroup$ @Yuval. I was just thinking how my explanation implied that what you're pointing out here. I will edit my answer to a correct one when I get my hands on a non-handheld device. If someone hasn't posted a correct one already. $\endgroup$ – Auberon Apr 15 '16 at 20:59
  • 1
    $\begingroup$ Furthermore, the real problem with the proposed algorithms is that they run in exponential time. $\endgroup$ – David Richerby Apr 15 '16 at 20:59
  • $\begingroup$ When I say: "how many times each prime will occur" I mean the problem essentially is finding a combination of exponents for the primes so that the factorization is correct. $\endgroup$ – Auberon Apr 15 '16 at 21:05
  • $\begingroup$ But I see that is not explicitly stated in my answer. $\endgroup$ – Auberon Apr 15 '16 at 21:06

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.