Problemas (criptográficos) solucionáveis ​​em um número polinomial de etapas aritméticas

9

No artigo de Adi Shamir [1], de 1979, ele mostra que esse fatoramento pode ser feito em um número polinomial de etapas aritméticas . Esse fato foi reafirmado e, portanto, me chamou a atenção no artigo recente de Borwein e Hobart [2] no contexto de programas de linha reta (SLP).

Como fiquei surpreso ao ler isso, tenho a seguinte pergunta: Existem outros problemas criptográficos ou talvez também outros problemas relevantes que possam ser resolvidos em um número polinomial de etapas com um SLP e que atualmente não são conhecidos por serem solucionáveis eficientemente em um computador clássico "normal"?

[1] Adi Shamir, fatorando números em etapas aritméticas de O(log⁡n) . Cartas de processamento de informações 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, O Poder Extraordinário da Divisão em Programas de Linha Reta , The American Mathematical Monthly Vol. 119, nº 7 (agosto a setembro de 2012), pp. 584-592

cc.complexity-theory cr.crypto-security algebraic-complexity Etsch
fonte
O que significa "solucionável em número polinomial de etapas aritméticas"? Os melhores algoritmos de fatoração atualmente disponíveis levam tempo subexponencial (mas super polinomial). Não encontro o papel de Shamir em lugar nenhum.
Mikeazo #
Sugiro postar isso no Crypto.SE, pois você não obteve muita resposta aqui.
Mikeazo 14/05
Há uma entrada de blog relacionada de Lipton: rjlipton.wordpress.com/2012/10/16/… Esse modelo de computação é meio trapaceiro, porque você está permitindo cálculos com precisão longa arbitrária. Não conheço outros problemas relacionados a criptografia que foram abordados neste modelo. Mas o modelo é tão poderoso que vale a pena tentar.
minar 6/07/2013
@ minar o problema da trapaça não é com precisão arbitrária. a trapaça aqui é com operações de piso e teto.
T ....

Respostas:

-2

Também não li o artigo, mas o resumo parece dizer que é necessário um número exponencial de operações de bits.

O trabalho de Chebyshev sobre congruências e sua reformulação no algoritmo AKS mostra que a geração principal está em P. Portanto, a divisão experimental produz fatores não triviais. Nesse caso, para algum número N, você pode esperar uma densidade de números primos de 1 / ln (N).

Além disso, você pode dar uma olhada na tese de doutorado de Turing em 1937 sobre o assunto.

Phil
fonte
3
Oi Phil. Bem-vindo à história. Você postou respostas para muitas perguntas em pouco tempo, o que não é comum aqui. As postagens que são realmente comentários e não respostas à pergunta não devem ser postadas como respostas. Você pode dar uma olhada e verificar outras perguntas e como as coisas funcionam aqui antes de postar mais respostas.
Kaveh