13
$\begingroup$

In Manuel Blum's "Advice to a Beginning Graduate Student":

LEONID LEVIN believes as I do that whatever the answer to the P=NP? problem, it won't be like anything you think it should be. And he has given some wonderful examples. For one, he has given a FACTORING ALGORITHM that is proVably optimal, up to a multiplicative constant. He proves that if his algorithm is exponential, then every algorithm for FACTORING is exponential. Equivalently, if any algorithm for factoring is poly-time, then his algorithm is poly-time. But we haven't been able to tell the running time of his algorithm because, in a strong sense, it's running time is unanalyzable.

Levin's publications page returns a 404, DBLP shows nothing related to factoring, and a search for "leonid levin factoring" on Google Scholar returns nothing of interest that I could find. AFAIK the generalized sieve is the fastest algorithm known for factoring. What is Manuel Blum talking about? Can anyone link me to a paper?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

Manuel Blum is talking about applying Levin's universal search algorithm to the Integer Factorization problem. The idea of Levin's Universal search algorithm is equally applicable to any problem in $NP$.

Here is a quote from lectures notes given by Blum on SECURITY and CRYPTOGRAPHY:

Leonid LEVIN's OPTIMAL NUMBER-SPLITTING (FACTORING) ALGORITHM. Let SPLIT denote any algorithm that computes INPUT: a positive composite (i.e. not prime) integer n. OUTPUT: a nontrivial factor of n.

THEOREM: There exists an "optimal" number-splitting algorithm, which we call OPTIMAL-SPLIT. This algorithm is OPTIMAL in the sense that: for every number-splitting Algorithm SPLIT there is a (quite large but fixed) constant C such that for every positive composite integer input n, the "running time" of OPTIMAL-SPLIT on input n is at most C times the running time of SPLIT on input n.

Here is Levin's optimal factoring algorithm:

The OPTIMAL-SPLIT ALGORITHM: BEGIN Enumerate all algorithms in order of size, lexicographically within each size. Run all algorithms so that at any moment in time, t, the ith algorithm gets [1/(2^i)] fraction of the time to execute. Wnenever an algorithm halts with some output integer m in the range 1 < m < n, check if m divides n (i.e. if n mod m = 0). If so, return m. END

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can someone explain why the fraction needs to be 1/(2^i) but not something simpler like 1/i? $\endgroup$
    – netvope
    Commented Oct 2, 2011 at 5:08
  • 1
    $\begingroup$ @netvope: The infinite sum of 1/i diverges. You might be able to do it with 1/i^2 but 1/2^i is a lot simpler. $\endgroup$
    – Antimony
    Commented Feb 28, 2015 at 22:59
4
$\begingroup$

I am not sure if this is what Blum was talking about, but it is easy to make an optimal algorithm up to a constant factor for almost any $NP \cap coNP$ problem. Here is an sketch for factoring in particular.

Given a number we want to factor N.

Is N prime? If so output 'PRIME' else:

For $i = 1...\infty$

For $P = 1...i$

Run program P for i steps with input N

If P outputs two integers (L,M) and $L \neq 1$ and $M \neq 1$ and $N = L*M$ then output $(L,M)$

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ You cannot use a known primality test because it is not known to be faster than the optimal factoring. Besides this, I do not understand one point. To prove that this is optimal for factoring up to a constant factor, I think that we have to prove that the multiplication in the last step is not the dominant term in the time complexity. If I remember correctly, the fastest known multiplication algorithm in the asymptotic setting is based on the FFT and takes O(n log n log log n) time for n-bit integers. Is it possible to prove that the optimal factoring takes at least as long as this? $\endgroup$
    – Tsuyoshi Ito
    Commented Apr 28, 2011 at 11:52
  • $\begingroup$ @Tsuyoshi: I think you are right in that this algorithm fails to be optimal if the known multiplication/primality tests are harder than factoring. However, if you read Blum's quote above, he says only that Levin's algorithm is polynomial if and only if the optimal one is, which finesses this problem. Two other things: (1) how could you avoid using a known primality test in this algorithm? (2) I think this algorithm isn't formulated quite right in that the running time isn't partitioned properly among the different programs; see Al-Turkistany's answer for the right formulation. $\endgroup$
    – Peter Shor
    Commented Apr 28, 2011 at 14:21
  • $\begingroup$ @Peter: Well, Blum’s quote says “he [Levin] has given a FACTORING ALGORITHM that is provably optimal, up to a multiplicative constant.” But considering that we do not even know whether factoring takes more than linear time or not, the statement is hard to believe as is. $\endgroup$
    – Tsuyoshi Ito
    Commented Apr 29, 2011 at 0:09
  • $\begingroup$ @Tsuyoshi: I see, I was reading the wrong Blum quote. $\endgroup$
    – Peter Shor
    Commented Apr 29, 2011 at 0:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.