Referência para o algoritmo de fatoração ideal de Levin?

No " Conselho para um estudante de graduação iniciante ", de Manuel Blum :

LEONID LEVIN acredita, enquanto faço isso, qualquer que seja a resposta para P = NP? problema, não será como você pensa que deveria ser. E ele deu alguns exemplos maravilhosos. Por um lado, ele forneceu um algoritmo de fatoração que é comprovadamente ideal, até uma constante multiplicativa. Ele prova que, se seu algoritmo é exponencial, todo algoritmo para FACTORING é exponencial. Equivalentemente, se algum algoritmo de fatoração for poli-tempo, então seu algoritmo é poli-tempo. Mas não conseguimos dizer o tempo de execução de seu algoritmo porque, em um sentido forte, o tempo de execução não pode ser analisado.

A página de publicações de Levin retorna um 404, o DBLP não mostra nada relacionado ao fatoração e uma pesquisa por "leonid levin factoring" no Google Scholar não retorna nada de interesse que eu pudesse encontrar. AFAIK, a peneira generalizada, é o algoritmo mais rápido conhecido por fatoração. Do que Manuel Blum está falando? Alguém pode me vincular a um artigo?

Manuel Blum está falando sobre a aplicação do algoritmo de busca universal de Levin ao problema da Fatoração Inteira. A idéia do algoritmo de busca Universal de Levin é igualmente aplicável a qualquer problema na .$NP$

Aqui está uma citação das notas das palestras dadas por Blum sobre SEGURANÇA e CRIPTOGRAFIA:

O ALGORITMO ÓTIMO DE FACTORING DE NÚMERO DE LEVIN DE LEVIN. Deixe SPLIT denotar qualquer algoritmo que calcule INPUT: um número composto positivo (isto é, não primo) n. SAÍDA: um fator não trivial de n.

TEOREMA: Existe um algoritmo de divisão de número "ideal", que chamamos de OPTIMAL-SPLIT. Esse algoritmo é OPTIMAL no sentido de que: para todo SPLIT de algoritmo de divisão de números, existe uma constante C (bastante grande, mas fixa) tal que para cada entrada inteira composta positiva n, o "tempo de execução" de OPTIMAL-SPLIT na entrada n é no máximo C vezes o tempo de execução de SPLIT na entrada n.

Aqui está o algoritmo de fatoração ideal de Levin :

O ALGORITMO DE DIVISÃO OPTIMAL: INICIAR Enumere todos os algoritmos em ordem de tamanho, lexicograficamente em cada tamanho. Execute todos os algoritmos para que, a qualquer momento, t, o i-ésimo algoritmo obtenha [1 / (2 ^ i)] fração do tempo de execução. Sempre que um algoritmo pára com algum número inteiro de saída m no intervalo 1 <m <n, verifique se m divide n (isto é, se n mod m = 0). Nesse caso, retorne m. FIM

$NP \cap coNP$

Dado um número, queremos fatorar N.

N é primo? Se sim, imprima 'PRIME' else:

$i = 1...\infty$

$P = 1...i$

Execute o programa P para i etapas com a entrada N

$L \neq 1$$M \neq 1$$N = L*M$$(L,M)$