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

1 Answer 1

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

$\endgroup$
4
  • 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$
    – user100470
    Feb 4, 2020 at 21:06
  • $\begingroup$ Pollard-rho should find a prime factor p in about O(p^{1/2}) (but might find several together and will tell you only their product). If n is not prime, then it should find some factor in O(n^{1/4}) steps. So if no factor is found in c * n^{1/4} steps then you use Rabin-Miller for example to test if n is prime; the optimal c will not be very large. If Rabin-Miller proves that n is composite, then you'll continue running the Pollard-rho test. $\endgroup$
    – gnasher729
    Jul 10, 2021 at 18:02
  • $\begingroup$ Being told that n is composite isn't very useful, because n might have a factor 3 - and then you are left with n/3 which may or may not be prime. $\endgroup$
    – gnasher729
    Jul 10, 2021 at 18:04
  • $\begingroup$ @gnasher729 I would recommend trial factorization for small factors before bringing out the big guns regardless. But yes your scheme is more sophisticated and can be even faster. $\endgroup$
    – orlp
    Jul 10, 2021 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.