P com oráculo de fatoração inteira

18

Acabei de ler a pergunta " A fatoração inteira é um problema NP-completo? " ... então decidi gastar parte da minha reputação :-) fazendo outra pergunta com P ( Q é trivial ) 1 :QP(Q is trivial)1

Se é um oráculo que resolve inteiro fatoração, o que é o poder da P A ? APA

Eu acho que isso torna a criptografia de chave pública baseada em RSA insegura ... mas, além disso, existem outros resultados notáveis?

Marzio De Biasi
fonte
3
@ Essa parte P(Q is trivial)=1é uma piada, não é?
Pratik Deoghare
Essa questão sugere uma questão relacionada e (talvez) mais natural: se R é um oráculo que retorna f _ (_ M , n ) como o tempo de execução máximo de uma máquina de Turing de tempo polinomial M sobre todas as entradas de comprimento n , qual é o poder de P ^ R?
John Sidles
2
@Vor: Isso não é o mesmo que perguntar "Quais problemas podem ser polinomiais em tempo de Turing reduzir a fatoração inteira?" Ou você pretendeu perguntar outra coisa?
Joshua Grochow
Sou novato, então minha pergunta é quase uma curiosidade. Tudo começou com um simples pensamento: fora "no mundo real", vejo muitos problemas NP-completos (um carteiro tentando reservar suas forças, uma família que está se movendo e quer colocar seus móveis em um caminhão, ...: - ))). Mas não vejo "problemas de fatoração" ... embora PODEM ser mais simples (entre P e NPC). ... talvez odeia reality multiplicações :-D :-D
Marzio De Biasi
11
Veja também Consequências do fatoramento em P?
Jukka Suomela

Respostas:

11

Não tenho uma resposta para sua pergunta, mas sei que uma noção semelhante foi estudada muito recentemente, sob o nome de "segurança baseada em anjo".

O primeiro artigo que estuda esse conceito é Prabhakaran & Sahai (STOC '04) . Em particular, eles escreveram no resumo:

[...] damos ao adversário acesso a algum poder computacional super-polinomial.

Outro artigo importante que discute essa noção é o de Canetti, Lin, & Pass (FOCS 2010) . Eu assisti algumas partes da apresentação da conferência (em techtalks ) e, se bem me lembro, elas começam com um exemplo semelhante ao que você mencionou na pergunta.

MS Dousti
fonte
13

Obviamente, qualquer problema de decisão que possa ser reduzido a fatoração pode ser resolvido com um oráculo de fatoração. Mas como temos a capacidade de fazer várias consultas, tentei pensar em um problema não trivial para o qual alguém desejaria fazer várias consultas.

O problema de calcular a função totiente de Euler parece ser um problema. Não sei como resolver a versão de decisão desse problema com uma redução de Karp na versão de decisão do fatoramento. Mas com as reduções de Turing, é fácil reduzir isso ao fatoramento.

Robin Kothari
fonte
3
Aqui está um post relacionado no MO sobre a complexidade da computação da função totiente.
Hsien-Chih Chang,
Pequena adição: também há reduções de tempo polinomiais na outra direção, calculando a função Totient de Euler -> Factoring. Não verifiquei se as reduções conhecidas funcionam para a versão de decisão desses problemas. Ainda assim, poder calcular a função Totient (ou mesmo um múltiplo fixo) permite a fatoração. O livro de Shoup dedica um capítulo a isso.
Juan Bermejo Vega
9

Elaborando sobre resposta anterior Joe: nota que . O último é o segundo mais baixo na classe "baixo" hierarquia : o que quer dizer que N P N P C O N P = N P . Isto implica, em particular, que P FATORAÇÃON P FATORAÇÃON P . Podemos fazer observações semelhantes para C S N P e B Q PFACTORINGNPcoNPNPNPcoNP=NP

PFACTORINGNPFACTORINGNP.
coNPBQP, Para demonstrar que, pelo menos, a um nível de grão grosseiro, tem os mesmos limites de complexidade como o problema FATORAÇÃO em si, o que quer dizer P FATORAÇÃON P C O N P B Q P .PFACTORINGFACTORING
PFACTORINGNPcoNPBQP.
Niel de Beaudrap
fonte
NPcoNP
3
UPcoUP
6

PAΔ2P

Marcus Ritt
fonte
5

FNPPPAΔ2pPNPBQPPPAPNPBQP

Joe Fitzsimons
fonte