3
$\begingroup$

Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns one of the prime factors of the number in Theta(n^2) time (note that I used a lowercase n in my theta notation.)

Using this algorithm, I want to find an efficient algorithm to factor an n-digit binary number into primes and print the prime factors. Moreover, I want to know how fast the algorithm runs as a function of n, and I also want to compute the approximate number of times my algorithm uses the one_factor(N) oracle in the worst case as a function of n.

Suppose we can add, subtract, divide, and multiply two n-digit binary numbers in Theta(n) time.


Here are my thoughts:

  • If the function one_factor(N) returns N, then I know that N is prime, and this can be my stopping condition.

  • If one_factor(N) returns a factor f, then I know that N/f is also a factor of N.

  • Thus, with each call to one_factor(N), I can find two factors of N, and I can divide out these factors from N. Then I can repeat the procedure.

I'm not exactly certain that this procedure always works. However, if it does, then I'll be finding two factors for every call to one_factor(N).I have no clue how to find the worst case number of times I call one_factor(N) or how fast my algorithm is though. It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.

$\endgroup$
2
$\begingroup$

This does work (see the fundamental theorem of arithmetic), and is exactly how some efficient factoring algorithms work, such as Pollard-Brent. However they use a weaker oracle, one that just returns a factor, not necessarily a prime one.

Since Pollard-Brent (and maybe others) runs very slowly and/or not at all when passed a prime, there is often another specific prime check in place as well.

A proper recursive routine under those assumptions would be (in Python):

def factorize(n):
    if n == 1: return []
    if is_prime(n): return [n]
    f = one_factor(n)
    return factorize(f) + factorize(n//f)

It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.

Analyzing it in terms of the number of prime factors is exactly right. You can then get an upper bound on the number of binary digits by noting that a $b$-bit number may have at most $b-1$ prime factors.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Okay, this is starting to make more sense. The f = one_factor(n) gets one prime factor of n, and it recursively finds the other prime factors by calling the function again on n/f. As you stated, a b-bit number has at most b - 1 prime factors, so in the worst case, we call the oracle n - 1 times. If it takes Theta(n) time to add, subtract, multiply, and divide two n-digit binary numbers, then how could I find the runtime of this algorithm? Intuitively, I think that the algorithm is O(n^3) since we'll enter the function at most n - 1 times? $\endgroup$ – oompa Feb 4 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.