Me parece que la tarea de eliminación de cuadrados se puede reducir a la tarea de factorización , pero que no hay forma de reducir la factorización a la eliminación de cuadrados. ¿Hay alguna manera de hacer que este "sentimiento" sea más preciso, es decir, alguna hipótesis comúnmente creída que se violaría si la factorización pudiera reducirse a la eliminación de cuadrados? Pero si la eliminación de cuadrados debería ser más fácil que factorizar (en el esquema de sentido anterior), entonces la siguiente pregunta es si se trata de un problema NP-intermedio (es decir, si se conoce o no un algoritmo de tiempo polinómico).
Aquí hay una descripción torpe de las tareas de eliminación y factorización de cuadrados :
Sea dado en representación binaria. Sea con prime, , y para sea la factorización prima de . p i α i ∈ N ∗ p i ≠ p j i ≠ j n
- Para la eliminación de cuadrados, se solicita la representación binaria de .
- Para factorizar, se solicita encontrar (la representación binaria de) un factor no trivial de , es decir, un número con , , y .q = ∏ j p β j j 1 < q < n β j ∈ N β j ≤ α j
fuente
Respuestas:
Creo que no se conoce ningún algoritmo polinomial.
Según un documento, esto se usa en al menos un criptosistema:
Si puede encontrar , romperá el sistema criptográfico calculando p k qp q .pagskqp q= pk - 1
Esta pregunta muestra que no se conoce un algoritmo polinomial para decidir si un entero es cuadrado (todos sus ).αyo= 1
fuente
Podemos demostrar que si todos los son diferentes, la eliminación de cuadrados y la factorización de n son igualmente difíciles.αyo norte
Es obvio que si podemos factorizar , también podemos calcular la eliminación cuadrada de n .norte norte
La otra dirección es un poco más complicada. Primero calcule la eliminación cuadrada de y llamemos a esto m . De la definición se deduce que m divide n . Dividir por m repetidamente hasta llegar a un número, que no es divisible por m , llamaré a esto xnorte metro metro norte metro metro X
Ahora calcule , situviera más de un factor primo, estos tendríanidénticoen el producto original, lo que contradice la suposición de que todoes diferente, por lo tantoes un factor primo en.p = mmcd ( x , m ) α i n α i p npags αyo norte αyo pags norte
Conocer un factor primo en es posible reducir el problema a factorizar un más pequeño , que satisfaga los mismos criterios, por lo que el algoritmo puede repetirse.norte norte′
También podemos mostrar que si todos son iguales, entonces la eliminación de cuadrados es fácil. Esto se debe a que solo puede tener un tamaño logarítmico en , y cada posible puede probarse calculando la raíz th de .αyo αyo norte αyo αyo norte
fuente