<p>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.</p>

<p>Given a number we want to factor N.</p>

<p>Is N prime? If so output 'PRIME' else:</p>

<p>For $i = 1...\infty$</p>

<p>For $P = 1...i$</p>

<p>Run program P for i steps with input N</p>

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

CC BY-SA 3.0
2011-04-28T11:52:13.847Z
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?
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-28T14:21:14.203Z
@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.
Peter Shor 
CC BY-SA 3.0
2011-04-29T00:09:17.483Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-29T00:20:44.550Z
@Tsuyoshi: I see, I was reading the wrong Blum quote.
Peter Shor 
CC BY-SA 3.0
2011-04-28T05:28:30.937Z
2011-04-28T05:28:30.937Z
Artem Kaznatcheev
<p>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$.</p>

<p>Here is a quote from <a href="http://www.cs.cmu.edu/~hopper/cs827-f01/lec4.txt">lectures notes</a> given by Blum on SECURITY and CRYPTOGRAPHY:</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

<p>Here is <a href="http://www.cs.cmu.edu/~hopper/cs827-f01/lec4.txt">Levin's optimal factoring algorithm</a>:</p>

<blockquote>
  <p>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 &lt; m
  &lt; n, check if m divides n (i.e. if n mod m = 0).
  If so, return m. 
  END</p>
</blockquote>

CC BY-SA 3.0
2011-10-02T05:08:25.463Z
Can someone explain why the fraction needs to be 1/(2^i) but not something simpler like 1/i?
netvope
CC BY-SA 3.0
2015-02-28T22:59:40.747Z
@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.
Antimony
CC BY-SA 3.0
2011-04-28T14:13:00.113Z
2011-04-28T14:23:48.257Z
2011-04-28T14:23:48.257Z
Mohammad Al-Turkistany
<p>In Manuel Blum's "<a href="http://www.cs.cmu.edu/~mblum/research/pdf/grad.html">Advice to a Beginning Graduate Student</a>":</p>

<blockquote>
  <p>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. </p>
</blockquote>

<p>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?</p>

<ds.algorithms><reference-request><factoring>
Reference for Levin's optimal factoring algorithm  ?
Christopher Monsanto
# Reference for Levin's optimal factoring algorithm  ?

(Asked by: username_0 on 2011-04-28)

In Manuel Blum's "[Advice to a Beginning Graduate Student](http://www.cs.cmu.edu/~mblum/research/pdf/grad.html)":

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

**Tags:** ds.algorithms, reference-request, factoring

---

## 2 answers

### Answer by username_4 on 2011-04-28. Score: 11 | Accepted answer

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](http://www.cs.cmu.edu/~hopper/cs827-f01/lec4.txt) 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](http://www.cs.cmu.edu/~hopper/cs827-f01/lec4.txt):

> 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

> **Comments:**
> **username_5**: Can someone explain why the fraction needs to be 1/(2^i) but not something simpler like 1/i?  
> **username_6**: @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.  

---

### Answer by username_1 on 2011-04-28. Score: 4

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

> **Comments:**
> **username_2**: 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?  
> **username_3**: @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.  
> **username_2**: @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.  
> **username_3**: @Tsuyoshi: I see, I was reading the wrong Blum quote.  

---

