Reduzindo produtos primários de fatoração para produtos inteiros de fatoração (em casos médios)

10

Minha pergunta é sobre a equivalência da segurança de várias funções unidirecionais candidatas que podem ser construídas com base na dureza da fatoração.

Assumindo o problema de

FACTORING: [Dado para números primos aleatórios P , Q < 2 n , encontre P , Q. ]N=PQP,Q<2nPQ

não pode ser resolvido em tempo polinomial com probabilidade não negligenciável, a função

PRIME-MULT: [Dada a sequência de bits como entrada, use x como uma semente para gerar dois primos aleatórios P e Q (onde os comprimentos de P , Q são polinomialmente menores que o comprimento de x ); em seguida, imprima P Q. ]xxPQPQxPQ

pode ser mostrado como unidirecional.

Outra função unidirecional candidata é

INTEGER-MULT: [Dados inteiros aleatórios como entrada, saída A B. ]A,B<2nAB

O INTEGER-MULT tem a vantagem de ser mais fácil definir em comparação com o PRIME-MULT. (Observe, em particular, que no PRIME-MULT, há uma chance (embora felizmente insignificante) de que a semente não gere P , Q que são primos.)xP,Q

Pelo menos em dois lugares diferentes (Arora-Barak, Complexidade Computacional, página 177, nota de rodapé 2) e ( notas da palestra Introdução a Criptografia de Vadhan ), é mencionado que o INTEGER-MULT é unidirecional assumindo dureza média de fatoração. No entanto, nenhum desses dois fornece a razão ou uma referência para esse fato.

Então a questão é:

Como podemos reduzir no fator tempo polinomial com probabilidade não negligenciável, para inverter INTEGER-MULT com probabilidade não negligenciável?N=PQ

Aqui está uma abordagem possível (que, como veremos, NÃO funciona!): Dado , multiplique N por um número inteiro aleatório A ' muito maior (embora polinomialmente) mais longo para obter A = N A ' . A ideia é que A ' é tão grande que tem muitos fatores primos de tamanho aproximadamente igual a P , Q , de modo que P , Q não "destacam-se" entre os fatores primos de um . Então A tem aproximadamente a distribuição de um número inteiro uniformemente aleatório em um determinado intervalo (digamos [ 0N=PQNAA=NAAP,QP,QAA ). Em seguida, escolha o inteiro B aleatoriamente no mesmo intervalo [ 0 , 2 n - 1 ] .[0,2n1]B[0,2n1]

Agora, se um inversor para INTEGER-MULT puder, dado , com alguma probabilidade encontrar A ' , B ' < 2 n tal que A ' B ' = A B , a esperança é que um de A ' ou B ' contenha P como um fator e o outro contém Q . Se fosse esse o caso, podemos encontrar P ou Q , tomando gcd de um ' com N = P Q .ABA,B<2nAB=ABABPQPQAN=PQ

O problema é que o inversor pode optar por separar os fatores primos, por exemplo, colocando os fatores pequenos de em A ' e os grandes em B ' , de modo que P e Q terminem em A ' ou em B' .ABABPQAB

Existe outra abordagem que funcione?

Omid Etesami
fonte
podemos reduzir a probabilidade de falha do INT-FACT ser exponencialmente pequena e, em seguida, usar a densidade dos primos para dizer que ele não falhará na maioria dos produtos de dois primos?
Kaveh
2
Se pudéssemos inverter o INTEGER-MULT para todas as instâncias, exceto a fração exponencialmente pequena das instâncias, seria muito fácil FACTORING produtos de primos. Mas não sei como obter um inversor forte de um inversor fraco.
Omid Etesami
11
O (de alguma forma) inversa desse problema já foi discutido aqui .
MS Dousti 29/07/11

Respostas:

4

Esta não é realmente uma resposta, mas lança alguma luz sobre a dificuldade de demonstrar essas reduções.


AnccNnAAnnddN

AN N=PQRPQn/4Rn/2NPQRAnA

k

2k/ln(2k)2k1/ln(2k1)=Θ(2k/k)

n

Θ(2n/4/(n/4))2Θ(2n/2/(n/2))2n1=Θ(n3)

n

AAnnddN

APQ

MS Dousti
fonte