A remoção de quadrados é mais fácil do que fatorar?

8

Parece-me que a tarefa de remoção de quadrados pode ser reduzida à tarefa de fatoração , mas que não há como reduzir o fatoramento à remoção de quadrados. Existe uma maneira de tornar esse "sentimento" mais preciso, ou seja, alguma hipótese comumente considerada que seria violada se o fatoramento pudesse ser reduzido à remoção quadrada? Mas se a remoção quadrada deve realmente ser mais fácil do que fatorar (no sentido descrito acima), a próxima pergunta é se é um problema intermediário de NP (ou seja, se um algoritmo de tempo polinomial para ele é conhecido ou não).


Aqui está uma descrição desajeitada das tarefas de remoção e fatoração de quadrados :

Seja nN dado em representação binária. Vamos n=ipiαi com pi privilegiada, αiN , e pipj para ij ser Fatorização privilegiada de n .

  • Para a remoção de quadrado, a representação binária de m=ipi é solicitada.
  • Para fatoração, é necessário encontrar (a representação binária de) um fator não trivial de n , ou seja, um número q=jpjβj com 1<q<n , βjN e βjαj .
Thomas Klimpel
fonte
3
ipin
1
Apenas como uma observação lateral: Presumo que sua pergunta seja direcionada a números inteiros. Para polinômios, a fatoração sem quadrado é realmente muito mais simples que a fatoração completa.
Christopher Creutzig

Respostas:

10

Eu acredito que nenhum algoritmo polinomial é conhecido.

De acordo com um artigo, isso é usado em pelo menos um sistema de criptografia:

pkqpkq

pqpkqpq=pk1


αi=1

joro
fonte
Pergunta interessante e boa resposta!
Tayfun Pay
11

αin

nn

nmmnmmx

x=nmb

p=mgcd(x,m)pαinαipn

Conhecendo um fator primo em , é possível reduzir o problema para fatorar um menor , que satisfaz os mesmos critérios, para que o algoritmo possa ser repetido.nn

Também podemos mostrar que, se todos forem iguais, a remoção quadrada será fácil. Isso porque só pode ter tamanho logarítmico em , e todo possível pode ser testado calculando a a raiz de .αiαinαiαin

No entanto, o resultado obtido dessa maneira estará incorreto se o não for igual. O resultado obtido será correto se não houver quadrado. E @joro apontou que nenhum algoritmo polinomial é conhecido por decidir se um número é livre de quadrados.αi

Portanto, para alguns quadrados, remoção e fatoração é equivalente. Para outros quadrados, a remoção é fácil. Diferenciar esses dois casos parece difícil.nn

Kasperd
fonte