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?
3
-
$\begingroup$ How do you get from knowing a factor exists, to using Levin's search to find it efficiently? $\endgroup$– usulCommented Nov 2, 2022 at 4:01
-
$\begingroup$ 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. $\endgroup$– usulCommented Nov 3, 2022 at 3:47
-
1$\begingroup$ 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. $\endgroup$– Dan BrumleveCommented Nov 4, 2022 at 23:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
-
1$\begingroup$ 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. $\endgroup$ Commented Nov 4, 2022 at 16:12
-
$\begingroup$ 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. $\endgroup$– CharlesCommented Apr 13, 2023 at 15:14