<p>In a practical sense, Levin search is not useful.  It has an enormous constant factor (exponential in the length/size of the optimal factoring algorithm).  This makes it of little use in practice.</p>
<p>In a theoretical sense, it is interesting but of little impact, because for theoretical reasons our primary interest is normally about what algorithms exist or not, and Levin search gives us no insight into that.</p>
<p>I'm not sure where you got the notion of a quadratic slowdown.  I don't believe that to be accurate.  See, e.g., <a href="http://www.scholarpedia.org/article/Universal_search" rel="nofollow noreferrer">http://www.scholarpedia.org/article/Universal_search</a>, <a href="https://cs.stackexchange.com/q/57179/755">https://cs.stackexchange.com/q/57179/755</a></p>

CC BY-SA 4.0
2022-11-04T16:12:21.237Z
I think it depends on the pairing function used, if it's $2^x \cdot (2 \cdot y + 1)$ then it's a constant slowdown, but if Cantor's, then quadratic.
Dan Brumleve
CC BY-SA 4.0
2023-04-13T15:14:24.883Z
As for impracticality, if the algorithm the Levin search ends up using is 40 bytes (a very small program!), the slowdown factor is about a googol.
Charles
CC BY-SA 4.0
2022-10-31T00:18:15.543Z
2022-10-31T00:18:15.543Z
D.W.
<p>It seems that there are many versions of this question that have answers when I look it up. But it seems quite clear that LUS should find a factor within an asymptotically quadratic transformation of the optimal run-time for factorization. So then it seems obvious to use the AKS primality test in P to efficiently determine the existence of some non-trivial factor and if it exists then we should be able to use Levin's Search, right? So that is essentially an efficient algorithm in theory for integer factorization? Why is this not widely known and taught then? So I'm probably mistaken and so I want to know why this is not theoretically valid. Since the AKS test is valid, why isn't LUS?</p>

CC BY-SA 4.0
2022-11-02T04:01:33.450Z
How do you get from knowing a factor exists, to using Levin's search to find it efficiently?
usul
CC BY-SA 4.0
2022-11-03T03:47:09.993Z
The key word being 'efficiently'. We know Levin's search will asymptotically match the fastest factorization algorithm, but we don't know if that algorithm is efficient (polynomial time) or not. And this is unrelated to AKS, so I am confused what connection is being drawn between existence of a factor and efficiency of the search.
usul
CC BY-SA 4.0
2022-11-04T23:25:33.767Z
A connection to AKS is that it can be used to recognize a full factorization when US outputs it.  But even without AKS we can wait for US to output a Pratt certificate for each factor along with the full factorization.  PRIMES in NP is all that is required.
Dan Brumleve
<factoring><search-problem><primes>
Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?
My Name
# Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?

(Asked by: username_0 on 2022-10-30)

It seems that there are many versions of this question that have answers when I look it up. But it seems quite clear that LUS should find a factor within an asymptotically quadratic transformation of the optimal run-time for factorization. So then it seems obvious to use the AKS primality test in P to efficiently determine the existence of some non-trivial factor and if it exists then we should be able to use Levin's Search, right? So that is essentially an efficient algorithm in theory for integer factorization? Why is this not widely known and taught then? So I'm probably mistaken and so I want to know why this is not theoretically valid. Since the AKS test is valid, why isn't LUS?

**Tags:** factoring, search-problem, primes

> **Comments:**
> **username_1**: How do you get from knowing a factor exists, to using Levin's search to find it efficiently?  
> **username_1**: The key word being 'efficiently'. We know Levin's search will asymptotically match the fastest factorization algorithm, but we don't know if that algorithm is efficient (polynomial time) or not. And this is unrelated to AKS, so I am confused what connection is being drawn between existence of a factor and efficiency of the search.  
> **username_2**: A connection to AKS is that it can be used to recognize a full factorization when US outputs it.  But even without AKS we can wait for US to output a Pratt certificate for each factor along with the full factorization.  PRIMES in NP is all that is required.  

---

## 1 answers

### Answer by username_3 on 2022-10-31. Score: 3 | Accepted answer

In a practical sense, Levin search is not useful. It has an enormous constant factor (exponential in the length/size of the optimal factoring algorithm). This makes it of little use in practice.

In a theoretical sense, it is interesting but of little impact, because for theoretical reasons our primary interest is normally about what algorithms exist or not, and Levin search gives us no insight into that.

I'm not sure where you got the notion of a quadratic slowdown. I don't believe that to be accurate. See, e.g., <http://www.scholarpedia.org/article/Universal_search>, <https://cs.stackexchange.com/q/57179/755>

> **Comments:**
> **username_2**: I think it depends on the pairing function used, if it's $2^x \cdot (2 \cdot y + 1)$ then it's a constant slowdown, but if Cantor's, then quadratic.  
> **username_4**: As for impracticality, if the algorithm the Levin search ends up using is 40 bytes (a very small program!), the slowdown factor is about a googol.  

---

