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

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 = PQ$$P, Q < 2^n$$P$$Q$

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. ]$x$$x$$P$$Q$$P$$Q$$x$$PQ$

pode ser mostrado como unidirecional.

Outra função unidirecional candidata é

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

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.)$x$$P, 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 [ $N = PQ$$N$$A'$$A = NA'$$A'$$P, Q$$P, Q$$A$$A$ ). Em seguida, escolha o inteiro B aleatoriamente no mesmo intervalo [ 0 , 2 n - 1 ] .$[0,2^n-1]$$B$$[0,2^n-1]$

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 .$AB$$A', B' < 2^n$$A'B' = AB$$A'$$B'$$P$$Q$$P$$Q$$A'$$N = 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' ′ .$AB$$A'$$B'$$P$$Q$$A'$$B'$

Existe outra abordagem que funcione?

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

$\mathcal{A}$$n^{-c}$$c \in \mathbb{N}$$n$$\mathcal{A}'$$\mathcal{A}$$n$$n^{-d}$$d \in \mathbb{N}$

$\mathcal{A}^*$$N$ $N = PQR$$P$$Q$$n/4$$R$$n/2$$N$$PQ$$R$$\mathcal{A}^*$$n$$\mathcal{A}^*$

$k$

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

$n$

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

$n$

$\mathcal{A}'$$\mathcal{A}^*$$n$$n^{-d}$$d \in \mathbb{N}$

$\mathcal{A}^*$$PQ$