# Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?

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?

• How do you get from knowing a factor exists, to using Levin's search to find it efficiently?
– usul
Nov 2, 2022 at 4:01
• 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
Nov 3, 2022 at 3:47
• 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. Nov 4, 2022 at 23:25

• 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. Nov 4, 2022 at 16:12