¿La eliminación de cuadrados es más fácil que factorizar?

8

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 nortenorte dado en representación binaria. Sea con prime, , y para sea ​​la factorización prima de . p i α iNp ip j i j nnorte=yopagsyoαyopagsyoαyonortepagsyopagsjyojnorte

  • Para la eliminación de cuadrados, se solicita la representación binaria de .metro=yopagsyo
  • 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 β jN β jα jnorteq=jpagsjβj1<q<norteβjnorteβjαj
Thomas Klimpel
fuente
3
nyopagsyo se llama radical de . Hay una discusión relevante en math.stackexchange.com/a/171571 . norte
Emil Jeřábek
1
Solo como un comentario secundario: supongo que su pregunta está dirigida a enteros. Para los polinomios, la factorización libre de cuadrados es mucho más simple que la factorización completa.
Christopher Creutzig

Respuestas:

10

Creo que no se conoce ningún algoritmo polinomial.

Según un documento, esto se usa en al menos un criptosistema:

Resumen. Proponemos un módulo de criptosistema basado en el criptosistema RSA. Elegimos un módulo apropiado p k q que resiste dos de los algoritmos de factorización más rápidos, a saber, el tamiz de campo numérico y el método de curva elíptica.pagskqpagskq

Si puede encontrar , romperá el sistema criptográfico calculando p k qpagsq.pagskqpagsq=pagsk-1


Esta pregunta muestra que no se conoce un algoritmo polinomial para decidir si un entero es cuadrado (todos sus ).αyo=1

joro
fuente
¡Pregunta interesante y buena respuesta!
Tayfun paga el
11

Podemos demostrar que si todos los son diferentes, la eliminación de cuadrados y la factorización de n son igualmente difíciles.αyonorte

Es obvio que si podemos factorizar , también podemos calcular la eliminación cuadrada de n .nortenorte

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 xnortemetrometronortemetrometroX

X=nortemetrosi

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.pags=metromcd(X,metro)α i n α i p npagsαyonorteαyopagsnorte

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.nortenorte

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αyonorteαyoαyonorte

αyo

nortenorte

kasperd
fuente