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?