Foros de matemática
21/07/2017, 09:52:07 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Observaciones sobre el método de factorización de Hugo Scolnik  (Leído 146 veces)
0 Usuarios y 1 Visitante están viendo este tema.
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« : 15/07/2017, 06:27:07 am »

Esto que voy a explicar ya lo publiqué en otro foro, hace años, pero ese otro foro ya cerró. Lo he modificado un poco para que se entienda mejor, y he añadido algunas cosas nuevas. Tenía pensado publicarlo en un solo post, pero he ido añadiendo cosas nuevas que han ido surgiendo a medida que iba repasando lo que ya tenía, y se ha alargado demasiado. Así que lo publicaré en varios posts, ya que me parece más fácil de leer. Además, todavía tengo cosas pendientes que añadir, que iré publicando en post sucesivos.

Para entender lo que voy a explicar, conviene leer los documentos de Hugo Scolnik, que se pueden encontrar en los siguientes enlaces:

Un trabajo del 2007: http://www.criptored.upm.es/descarga/Avances_en_la_factorizacion_entera.pdf

Un trabajo del 2008: http://campus.usal.es/~xrecsi/Imagenes/conferenciantes/Scolnik.pdf

Un trabajo del 2011: http://www.40jaiio.sadio.org.ar/sites/default/files/T2011/WSegI/834.pdf

Estos documentos son bastante breves y fáciles de entender (el último es un poco más extenso). Basta con leer el primero para entender lo que voy a exponer.

También hay un vídeo en el que da una conferencia explicando su método:

https://www.youtube.com/watch?v=Zrd8tM_1Pnk

En estos documentos se habla de un algoritmo de factorización en tiempo polinómico que estaba desarrollando Hugo Scolnik.

Lo primero que hay que indicar, antes de empezar a explicar, es que de momento el método de factorización de Hugo Scolnik no permite factorizar grandes enteros de forma rápida. El método fue presentado en el año 2007 (o quizá antes), y desde entonces no se han visto avances, ni se encuentra casi información del mismo en Internet, lo que lleva a pensar que no se ha podido desarrollar para permitir factorizaciones rápidas de grandes enteros (o a lo mejor sí, y lo mantienen en secreto :sonrisa:).

Y dicho esto, empiezo con el resumen de lo que voy a explicar.

Resumen

Como todavía tengo cosas pendientes que revisar, seguramente añada más adelante cosas que no se reflejen en este resumen. De momento, resumo lo que ya tengo listo para añadir.

Primero explicaré el fundamento del resto de lo que voy a exponer. Es un poco lo que Hugo Scolnik explicó en sus trabajos, para entender lo que voy a exponer.

Definiré lo que denomino como target válido, target no válido, target correspondiente a una diferencia de cuadrados, y target trivial.

Explicaré unos algoritmos para determinar si un entero tiene target único módulo [texx]\displaystyle c[/texx], a pesar de no ser necesario debido a la limitación del valor de [texx]\displaystyle c[/texx] a [texx]\displaystyle 1440[/texx], como indica Hugo Scolnik en sus trabajos, para que puedan existir targets únicos, ya que podría comprobarse de forma exhaustiva rápidamente.

Explicaré la composición de targets, y cómo afectan a la composición los targets únicos, los targets válidos, y los targets no válidos.

Mostraré un caso especial de target, que es aquel target válido cuyo módulo es mayor que el menor de los cuadrados de la expresión de un entero como diferencia de cuadrados. Explicaré el fundamento de un algoritmo de factorización basado en esta idea, y mostraré el algoritmo en pseudocódigo, con un ejemplo de factorización (el algoritmo no permite factorizar grandes enteros por las limitaciones de los targets únicos :triste:). Por último, mostraré una optimización de este algoritmo.

Explicaré un poco el límite de [texx]\displaystyle 1440[/texx] en los módulos que pueden tener target único.

Hablaré del problema que suponen los targets múltiples a la hora de factorizar un entero con el algoritmo presentado antes.

Definiré lo que denomino como target trivial solapado, mostraré cómo calcular los módulos máximos (que sean máximos es una conjetura) para los que existen estos targets conociendo la factorización del entero, y presentaré una serie de conjeturas sobre estos targets, conjeturas que parecen ciertas por las pruebas que he realizado (todavía tengo que revisar estas conjeturas, para ver si se me ocurre cómo demostrarlas, o ver si encuentro algún contraejemplo, aunque las he comprobado con millones de enteros y todavía no he encontrado contraejemplos).

Hablaré de cómo determinar algunos divisores de la suma y la diferencia de los divisores de un entero con los targets únicos, cálculo extensible a cualquier target válido.

Finalmente, hablaré de los enteros cuyos targets son todos válidos módulo algún [texx]\displaystyle c[/texx]. Esto todavía lo estoy estudiando, pues me lo encontré casi de casualidad (pensaba que si un entero no tenía targets únicos módulo [texx]\displaystyle c[/texx], tendría algún target no válido, pero resulta que no siempre ocurre esto).

Cualquier otra cosa que me encuentre la añadiré en sucesivos posts.

Notas preliminares

En lo que sigue, todas las variables, si no se dice otra cosa, cumplirán las siguientes condiciones:

- Los valores de las variables serán enteros mayores o iguales a [texx]\displaystyle 0[/texx].
- La variable [texx]\displaystyle n[/texx] hace referencia al entero que se quiere factorizar, que será impar y, por tanto, expresable como diferencia de cuadrados, y puede ser primo o compuesto.
- La variable [texx]\displaystyle c\ge 2[/texx] hace referencia al módulo de las congruencias de los targets.
- Las variables [texx]\displaystyle p[/texx] y [texx]\displaystyle q[/texx] hacen referencia a valores primos.
- Las variables [texx]\displaystyle a[/texx], [texx]\displaystyle b[/texx], [texx]\displaystyle r[/texx], [texx]\displaystyle s[/texx], y cualquier otra, hacen referencia a cualquier valor, que puede ser primo o compuesto.
- Todo lo anterior también aplica si las variables tienen subíndices, o primas.

A menudo se verá expresado [texx]\displaystyle n[/texx] como producto de dos enteros, o como diferencia de dos cuadrados. Para simplificar, y no estar continuamente diciendo que un entero es menor que otro, en estas expresiones el orden alfabético de los pares de variables indica también el orden de sus valores. Así, en las expresiones [texx]\displaystyle n=r\cdot s[/texx], [texx]\displaystyle n=p\cdot q[/texx], [texx]\displaystyle n=b^2-a^2[/texx], se considerará que [texx]\displaystyle r\le s[/texx] [texx]\displaystyle p\le q[/texx], [texx]\displaystyle a\le b[/texx]. En otras expresiones, sobre todo en congruencias, no habrá necesariamente tal orden, y si lo hay, se indicará explícitamente.

A la hora de escribir targets, se podrán expresar con cuadrados explícitos (esto es, de la forma [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx]), o con cuadrados implícitos (esto es, de la forma [texx]\displaystyle n+a\equiv b\pmod{c}[/texx], donde se entenderá que [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] son cuadrados módulo [texx]\displaystyle c[/texx]). En este último caso, se mencionará que la expresión es un target para evitar confusiones.

Las formas [texx]\displaystyle n=b^2-a^2[/texx] y [texx]\displaystyle n+a^2=b^2[/texx], que son equivalentes, las llamaré indistintamente como 'diferencia de cuadrados de [texx]\displaystyle n[/texx]', a pesar de que la segunda expresión no muestra directamente una diferencia de cuadrados.
En línea
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #1 : 15/07/2017, 06:37:59 am »

Fundamento

Lo que voy a explicar aquí no es el fundamento del método de Hugo Scolnik, que puede leerse en los documentos mencionados antes, sino que está basado en el método de Hugo Scolnik, aunque buena parte de lo que voy a explicar es lo que Hugo Scolnik explica en sus trabajos, pero con un punto de vista algo diferente.

El método de Hugo Scolnik se basa, como muchos métodos modernos de factorización, y como él mismo indica, en la expresión de un entero [texx]\displaystyle n[/texx] como diferencia de cuadrados. Recordemos que todo entero impar dado por [texx]\displaystyle n=r\cdot s[/texx] puede expresarse como diferencia de cuadrados de la forma [texx]\displaystyle n=\left(\dfrac{s+r}{2}\right)^2-\left(\dfrac{s-r}{2}\right)^2[/texx] (esto también aplica a los enteros pares múltiplos de [texx]\displaystyle 4[/texx] (siempre que [texx]\displaystyle r[/texx] y [texx]\displaystyle s[/texx] sean ambos pares), pero estos los descartamos porque se extrae el factor [texx]\displaystyle 2[/texx] dividiendo directamente, quedando al final un valor impar que hay que factorizar).

Esta expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados se lleva a las congruencias, siguiendo, como indica Hugo Scolnik, un método parecido al método de Maurice Kraitchik, de forma que en el método de Hugo Scolnik tenemos congruencias de la forma [texx]\displaystyle n\equiv b^2-a^2\pmod{c}[/texx], que se expresarán normalmente como [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx], debido a que se parece más a la forma de expresar los targets.

En el método de Hugo Scolnik, originalmente se tomaban únicamente los residuos cuadráticos módulo [texx]\displaystyle c[/texx], además del [texx]\displaystyle 0[/texx]. En su último trabajo indica que se toman todos los cuadrados módulo [texx]\displaystyle c[/texx]. En lo que voy a explicar, también se tendrán en cuenta todos los cuadrados módulo [texx]\displaystyle c[/texx], es decir, cualquier entero [texx]\displaystyle a[/texx] tal que exista un entero [texx]\displaystyle a'[/texx] que cumpla [texx]\displaystyle a\equiv a'^2\pmod{c}[/texx], sin importar si [texx]\displaystyle a[/texx] es primo relativo con [texx]\displaystyle c[/texx] o no.

Hugo Scolnik define el concepto de target, y de target único, que puede consultarse en los documentos indicados más arriba, y que utilizaré en la explicación. Ambos conceptos hacen referencia a la relación [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx]. En lugar de utilizar la notación de Hugo Scolnik para los targets, voy a escribir directamente las congruencias.
En línea
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #2 : 15/07/2017, 06:46:03 am »

Targets válidos, targets no válidos, targets correspondientes a las diferencias de cuadrados, y targets triviales

En los trabajos de Hugo Scolnik se ve que un mismo entero puede tener varios targets módulo [texx]\displaystyle c[/texx], es decir, existen varios valores diferentes de [texx]\displaystyle a^2[/texx] y [texx]\displaystyle b^2[/texx] módulo [texx]\displaystyle c[/texx] tales que cumplen la congruencia [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx]. De aquí surgen las siguientes definiciones:

Target válido

Dado el entero [texx]\displaystyle n[/texx], diremos que el target [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx] es un target válido para [texx]\displaystyle n[/texx] si existen enteros [texx]\displaystyle a'[/texx] y [texx]\displaystyle b'[/texx] tales que [texx]\displaystyle n=b'^2-a'^2[/texx], [texx]\displaystyle a'^2\equiv a^2\pmod{c}[/texx] y [texx]\displaystyle b'^2\equiv b^2\pmod{c}[/texx].

Target no válido

Dado el target [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx], diremos que el target es un target no válido para [texx]\displaystyle n[/texx] si no existen enteros [texx]\displaystyle a'[/texx] y [texx]\displaystyle b'[/texx] tales que cumplan simultáneamente [texx]\displaystyle n=b'^2-a'^2[/texx], [texx]\displaystyle a'^2\equiv a^2\pmod{c}[/texx] y [texx]\displaystyle b'^2\equiv b^2\pmod{c}[/texx].

Otra forma de decirlo es la siguiente: diremos que el target [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx] es un target no válido para [texx]\displaystyle n[/texx] si, para toda expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados de la forma  [texx]\displaystyle n=b_i^2-a_i^2[/texx], siempre se cumple [texx]\displaystyle a_i^2\not\equiv a^2\pmod{c}[/texx] o [texx]\displaystyle b_i^2\not\equiv b^2\pmod{c}[/texx].

Es obvio que para todo [texx]\displaystyle n[/texx] expresable como diferencia de cuadrados, siempre existe al menos un target válido módulo [texx]\displaystyle c[/texx] (basta calcular cada uno de los cuadrados, de la diferencia de cuadrados, en módulo [texx]\displaystyle c[/texx], para obtener un target válido). Además, pueden existir como máximo tantos targets válidos como formas diferentes de expresar el entero como diferencia de cuadrados.

En caso de existir más de un target válido módulo [texx]\displaystyle c[/texx], cada uno de esos targets sólo será válido para una determinada expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados.

Target correspondiente a una diferencia de cuadrados

Dada la expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados de la forma [texx]\displaystyle n=b'^2-a'^2[/texx], diremos que el target [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx] es un target correspondiente a esta diferencia de cuadrados si se cumple [texx]\displaystyle a'^2\equiv a^2\pmod{c}[/texx] y [texx]\displaystyle b'^2\equiv b^2\pmod{c}[/texx].

Para cada expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados sólo existe un target correspondiente, como se deduce fácilmente. Además, puede ocurrir que un mismo target sea un target correspondiente a varias expresiones de [texx]\displaystyle n[/texx] como diferencia de cuadrados (el caso más claro es el de los targets únicos, en los que sólo hay un target válido para todas las expresiones de [texx]\displaystyle n[/texx] como diferencia de cuadrados).

Target trivial

Siendo [texx]\displaystyle n[/texx] expresable como diferencia de cuadrados, ocurre que siempre hay una expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados que podemos obtener sin conocer su factorización. Esta expresión es [texx]\displaystyle n=\left(\dfrac{n+1}{2}\right)^2-\left(\dfrac{n-1}{2}\right)^2[/texx]. A esta expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados la denominaremos expresión trivial de [texx]\displaystyle n[/texx] como diferencia de cuadrados, y al target correspondiente le llamaremos target trivial.

El principal problema del método de Hugo Scolnik es el de determinar el target válido cuando el entero [texx]\displaystyle n[/texx] no tiene un target único módulo [texx]\displaystyle c[/texx], y éste parece el principal problema que impide que el método no permita factorizar rápidamente un entero grande.

Spoiler (click para mostrar u ocultar)
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.430



Ver Perfil
« Respuesta #3 : 15/07/2017, 07:04:32 am »


Hola, Sqrmatrix. Gracias por esta aportación.

Aunque aún no he probado cosas ni pensado del todo lo que se dice, una pregunta: ¿se sabe más o menos en qué medida aumentan los targets respecto del aumento de la cantidad de cifras?
 
Veo que, en el ejemplo, un número de sólo cinco cifras tiene 105 targets, si el aumento no es “lineal” por así decirlo, un RSA como el 230 puede tener una barbaridad de  targets, supongo.

Un cordial saludo.
En línea

sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #4 : 15/07/2017, 07:38:36 am »

Saludos, feriva

Aunque aún no he probado cosas ni pensado del todo lo que se dice, una pregunta: ¿se sabe más o menos en qué medida aumentan los targets respecto del aumento de la cantidad de cifras?
 
Veo que, en el ejemplo, un número de sólo cinco cifras tiene 105 targets, si el aumento no es “lineal” por así decirlo, un RSA como el 230 puede tener una barbaridad de  targets, supongo.

No sé si habrá una fórmula que determine directamente el número de targets. Por las pruebas que he hecho, el número de targets aumenta a medida que aumenta el módulo. El número de targets depende del tamaño del módulo y de la clase residual del entero en ese módulo, más que de las cifras del entero en sí. Dos enteros con la misma clase residual tendrán los mismos targets. El mayor problema es determinar qué target, de todos los que hay, es el que nos interesa (y este es el problema fundamental de este método de factorización).

Todavía me quedan muchas cosas que añadir, y todo esto se irá viendo poco a poco. Iré añadiendo poco a poco cosas que ya tengo listas para publicar, pero que tengo que adaptar y repasar. Cualquier aclaración, ya sabes, no dudes en preguntar. Y cualquier aportación siempre es bienvenida
En línea
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #5 : 15/07/2017, 12:53:20 pm »

Algoritmos para buscar targets de un entero [texx]\displaystyle n[/texx] módulo [texx]\displaystyle c[/texx]

En el resumen no mencioné que iba a añadir este apartado, porque en ese momento no lo tenía planificado. Pero al ponerme a repasar el apartado de los algoritmos para determinar si un entero tiene target único, ví que todos los algoritmos tenían que buscar targets, y que no había mencionado para nada la búsqueda de targets. Así que añado este apartado para dejar completo el apartado de algoritmos para determinar si un entero tiene target único.

Recordemos que un target de [texx]\displaystyle n[/texx] módulo [texx]\displaystyle c[/texx] es una terna de valores [texx]\displaystyle (a,b,c)[/texx] tales que [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] son cuadrados módulo [texx]\displaystyle c[/texx] (es decir, que existen enteros [texx]\displaystyle a'[/texx] y [texx]\displaystyle b'[/texx] tales que [texx]\displaystyle a\equiv a'^2\pmod{c}[/texx] y [texx]\displaystyle b\equiv b'^2\pmod{c}[/texx]), que cumplen [texx]\displaystyle n+a\equiv b\pmod{c}[/texx].

Lo primero que hay que comprobar, en cualquier algoritmo que vaya a trabajar con targets de un entero [texx]\displaystyle n[/texx], es que el entero sea impar o múltiplo de [texx]\displaystyle 4[/texx]. Esto es porque los targets son congruencias basadas en la expresión del entero como diferencia de cuadrados, y los enteros pares que no son múltiplos de [texx]\displaystyle 4[/texx] no tienen expresión como diferencia de cuadrados. Así, si el entero [texx]\displaystyle n[/texx] no es impar ni múltiplo de [texx]\displaystyle 4[/texx], no hay target que buscar. Dicho esto, pasemos a los algoritmos, que suponemos que han hecho esta comprobación antes.

Primer algoritmo

El primer algoritmo es el más simple de todos, y el más ineficiente. Consiste en simplemente ir recorriendo los enteros desde [texx]\displaystyle i=0[/texx] hasta [texx]\displaystyle i=c-1[/texx]. Calculamos [texx]\displaystyle b\equiv n+i^2\pmod{c}[/texx], y comprobamos si [texx]\displaystyle b[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx]. Si lo es, hemos encontrado un target, cuyos valores serán [texx]\displaystyle a\equiv i^2\pmod{c}[/texx], [texx]\displaystyle b\equiv n+i^2\pmod{c}[/texx], y [texx]\displaystyle c[/texx].

Para determinar si [texx]\displaystyle b[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx], se puede hacer de diferentes maneras. La primera consiste en hacer más o menos lo mismo que estamos haciendo para los targets. Recorremos todos los enteros desde [texx]\displaystyle j=0[/texx] hasta [texx]\displaystyle j=c-1[/texx], y comprobamos si se cumple [texx]\displaystyle j^2\equiv b\pmod{c}[/texx]. Si se cumple, [texx]\displaystyle b[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx]. Si recorremos todos los enteros sin que se cumpla para ninguno, no lo es.


Otra forma es utilizar el Criterio de Euler (esto no lo voy a explicar aquí. Simplemente recordar que  debe aplicarse a cada primo que divide a [texx]\displaystyle c[/texx] (el primo sin exponente), y ver que para todos los primos se cumple el criterio. Si es así, [texx]\displaystyle b[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx]. Si no se cumple para alguno de los primos, no lo es).


Corrección: Lo anterior no es correcto, me despisté. Sólo se puede hacer si [texx]\displaystyle c[/texx] es producto de primos impares con exponente [texx]\displaystyle 1[/texx] y además, si [texx]\displaystyle a[/texx] es primo relativo con [texx]\displaystyle c[/texx]. Cuando los primos están elevados a exponentes mayores a [texx]\displaystyle 1[/texx] y/o cuando [texx]\displaystyle c[/texx] es par y/o cuando [texx]\displaystyle a[/texx] no es primo relativo con [texx]\displaystyle c[/texx], lo anterior se puede hacer aplicando criterios adicionales. Voy a ver si añado estos criterios en un apartado adicional. Y si no, pues siempre quedará la búsqueda exhaustiva :sonrisa:.

Hay que indicar que este algoritmo devuelve targets repetidos, pues todo cuadrado módulo [texx]\displaystyle c[/texx] tiene al menos dos raíces. [texx]\displaystyle i[/texx] va tomando todos los valores, incluyendo el de raíces repetidas, que al elevar al cuadrado, generarán todas esas raíces el mismo cuadrado y, por tanto, el mismo target (para los casos en los que se haya encontrado el target).

En pseudocódigo queda (suponiendo informados [texx]\displaystyle n[/texx], [texx]\displaystyle c[/texx], "inicio"):

     1.- Para [texx]\displaystyle i[/texx]=inicio hasta [texx]\displaystyle c-1[/texx], hacer:
     2.- Hacer [texx]\displaystyle a=i^2\bmod c[/texx]
     3.- Hacer [texx]\displaystyle b=(n+a)\bmod c[/texx]
     4.- Si [texx]\displaystyle b[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx], devolver el target [texx]\displaystyle (a,b,c)[/texx]. Fin del bucle
     5.- Repetir bucle en 1
     6.- Devolver indicador de "no hay más targets"

Segundo algoritmo

El anterior algoritmo, además de ineficiente, nos devolvía targets repetidos. En este segundo algoritmo vamos a mejorar la eficiencia. Dado que lo que buscamos son cuadrados [texx]\displaystyle a[/texx] y [texx]\displaystyle b[/texx] módulo [texx]\displaystyle c[/texx], lo mejor que podemos hacer es tener una lista de esos cuadrados para poderlos buscar en ella. Esto, por supuesto, sólo se puede hacer si [texx]\displaystyle c[/texx] no es excesivamente grande.

Tener una lista de cuadrados módulo [texx]\displaystyle c[/texx] nos permite, además, evitar repetir targets, ya que cada cuadrado sólo va a estar una única vez en la lista. Para construir la lista, basta hacer como antes, recorrer los enteros desde [texx]\displaystyle i=0[/texx] hasta [texx]\displaystyle i=c-1[/texx], y almacenar en dicha lista los valores [texx]\displaystyle i^2\bmod c[/texx]. El problema que se plantea es eliminar los valores repetidos. Esta eliminación se puede hacer a priori, o a posteriori.

La eliminación a priori consiste en comprobar, antes de guardar un valor, si está ya en la lista. Si está, no lo guardamos. Si no está, lo guardamos. Para comprobar si existe el valor, se recorrerían los valores guardados y se compararían con el que queremos guardar. Pero hay otra opción. Los valores se pueden guardar ordenados en la lista. Para ello, se localiza el lugar donde debe ir el valor, y se desplazan los elementos que hay desde ese lugar hasta el final una posición para dejar el hueco libre, y luego se almacena el valor en ese hueco. La ventaja de hacer esto es que, a la hora de comprobar si un valor ya existe en la lista, se puede hacer una búsqueda binaria en los elementos que tenemos ya almacenados, la cual es mucho más rápida que ir recorriendo todos los elementos hasta encontrar el que buscamos, o no encontrarlo. Otra ventaja de hacerlo así es que la lista queda ordenada al terminar el proceso de búsqueda de cuadrados. La desventaja es que se deben hacer muchos movimientos de datos para ir colocando los nuevos datos.

La eliminación a posteriori consiste en almacenar en la lista todos los cuadrados módulo [texx]\displaystyle c[/texx] que vayamos encontrando, sin importar si están repetidos o no. Cuando terminemos, ordenamos la lista. Ahora, todos los elementos repetidos están en posiciones contiguas. Para eliminarlos, basta construir una segunda lista, a la que le vamos pasando los elementos de la primera siempre que el elemento a añadir no se repita con el último que añadimos. Este es el método que me parece mejor, aunque requiere más memoria. Además, la lista obtenida estará ordenada.

Ahora, para buscar los targets, basta recorrer la lista de los cuadrados que acabamos de construir. Sabemos que los valores de esa lista son cuadrados módulo [texx]\displaystyle c[/texx], y que además no están repetidos. Sea [texx]\displaystyle a[/texx] uno de esos cuadrados. Obtenemos [texx]\displaystyle b=(n+a)\bmod c[/texx]. Ahora, para determinar si [texx]\displaystyle b[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx], basta tener en cuenta que todos los cuadrados módulo [texx]\displaystyle c[/texx] están en la lista, por lo que basta una búsqueda de [texx]\displaystyle b[/texx] en dicha lista. Además, por estar ordenada, podemos hacer una búsqueda binaria, que es mucho más rápida que una secuencial.

En pseudocódigo queda (suponiendo informados [texx]\displaystyle n[/texx], [texx]\displaystyle c[/texx], "inicio", y construida la lista de cuadrados módulo [texx]\displaystyle c[/texx] "listaCuadrados". "inicio" ahora hace referencia a un elemento de "listaCuadrados". En esta lista, el primer elemento es el de la posición 0):

     1.- Si es la primera consulta, construir la lista de cuadrados módulo [texx]\displaystyle c[/texx], llamada "listaCuadrados"
     2.- Para [texx]\displaystyle i[/texx]=inicio hasta (número de valores de "listaCuadrados")-1, hacer:
     3.- Hacer [texx]\displaystyle a=listaCuadrados\left[i\right][/texx]
     4.- Hacer [texx]\displaystyle b=(n+a)\bmod c[/texx]
     5.- Hacer búsqueda binaria de [texx]\displaystyle b[/texx] en "listaCuadrados". Si se encuentra el valor, devolver el target [texx]\displaystyle (a,b,c)[/texx]. Fin del bucle
     6.- Repetir bucle en 2
     7.- Devolver indicador de "no hay más targets"

Si se va a trabajar con varios módulos, se pueden almacenar las listas de cuadrados de cada módulo  para posteriores llamadas, y así acelerar dichas consultas, o cualquier otra que requiera saber si un entero es un cuadrado módulo alguno de los módulos de las listas de cuadrados almacenadas.
En línea
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #6 : 16/07/2017, 10:48:50 am »

Algoritmos para determinar si un entero [texx]\displaystyle n[/texx] tiene target único módulo [texx]\displaystyle c[/texx]

Dado que el límite del módulo [texx]\displaystyle c[/texx] para que un entero impar pueda tener target único es de [texx]\displaystyle 1440[/texx], y sólo [texx]\displaystyle 1440[/texx] o cualquiera de sus divisores puede tener target único (esto se irá viendo en otros apartados más adelante), resulta innecesario describir ningún algoritmo para determinar si un determinado entero [texx]\displaystyle n[/texx] tiene target único módulo [texx]\displaystyle c[/texx], pues se puede hacer una búsqueda exhaustiva que no tomará mucho tiempo. Además, se pueden almacenar las clases residuales para las que un entero puede tener target único módulo [texx]\displaystyle 1440[/texx] y sus divisores, para que simplemente baste una búsqueda para determinar si cualquier entero tiene target único. No obstante, me parece interesante describir un algoritmo aprovechando las características de los targets únicos.

Desconozco si hay una manera más rápida que las que voy a proponer para determinar si un entero [texx]\displaystyle n[/texx] tiene target único módulo [texx]\displaystyle c[/texx].

Todos los algoritmos que voy a describir aprovechan la propiedad de los targets únicos de que cualquier expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados tiene asociado el mismo target. Además, en estas condiciones, si el target único de [texx]\displaystyle n[/texx] es [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx], y tenemos todas las expresiones de [texx]\displaystyle n[/texx] como diferencia de cuadrados de la forma [texx]\displaystyle n=b_i^2-a_i^2[/texx], se cumple: [texx]\displaystyle a_i^2\equiv a^2\pmod{c}[/texx] y [texx]\displaystyle b_i^2\equiv b^2\pmod{c}[/texx]. Como consecuencia, se cumplirá [texx]\displaystyle a_i^2\equiv a_j^2\pmod{c}[/texx] y [texx]\displaystyle b_i^2\equiv b_j^2\pmod{c}[/texx].

Como se indicó en el anterior apartado, se habrá comprobado que el entero es impar o múltiplo de [texx]\displaystyle 4[/texx]. Si no, no tendrá ningún target. A la hora de buscar los targets, se aplicará alguno de los algoritmos del apartado anterior, indicando el valor de "inicio" que corresponda para buscar el siguiente target (se incrementa en [texx]\displaystyle 1[/texx] respecto del valor del último target encontrado).

Primer algoritmo

Lo primero que se nos ocurre es que, si [texx]\displaystyle n[/texx] tiene target único módulo [texx]\displaystyle c[/texx], entonces todos los targets de [texx]\displaystyle n[/texx] módulo [texx]\displaystyle c[/texx] serán iguales. Por tanto, se buscará un target, que se guardará como target de referencia, y luego se obtendrán todos los demás targets, que se irán comparando con el que hemos guardado. Si alguno es diferente, el entero [texx]\displaystyle n[/texx] no tiene target único módulo [texx]\displaystyle c[/texx]. Si todos son iguales, entonces el entero [texx]\displaystyle n[/texx] tiene target único módulo [texx]\displaystyle c[/texx]. El algoritmo queda:

     1.- Buscar el primer target del entero [texx]\displaystyle n[/texx] módulo [texx]\displaystyle c[/texx]. Sea [texx]\displaystyle t_0[/texx] dicho target
     2.- Mientras haya targets pendientes de leer, hacer:
     3.- Buscar el siguiente target. Sea [texx]\displaystyle t[/texx]
     4.- Si [texx]\displaystyle t_0\ne t[/texx], devolver indicador de "no tiene target único"
     5.- Repetir bucle en 2
     6.- Devolver indicador de "sí tiene target único"

Segundo algoritmo

El anterior algoritmo requería hacer una primera búsqueda para encontrar un target con el que comparar el resto. Pero podemos ahorrarnos esa primera búsqueda teniendo en cuenta que el target trivial es un target que también habrá que comparar con los demás. Este target lo podemos determinar directamente. Basta hacer [texx]\displaystyle a=\dfrac{n-1}{2}\bmod c[/texx] y [texx]\displaystyle b=\dfrac{n+1}{2}\bmod c[/texx] para obtener el target [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx], que podemos usar para comparar con los demás. El algoritmo quedaría:

     1.- Obtener el target trivial del entero [texx]\displaystyle n[/texx] módulo [texx]\displaystyle c[/texx]: sea [texx]\displaystyle a=\dfrac{n-1}{2}\bmod c[/texx] y [texx]\displaystyle b=\dfrac{n+1}{2}\bmod c[/texx], y sea [texx]\displaystyle t_0[/texx] el target [texx]\displaystyle n+a^2\equiv b^2\pmod{c}[/texx]
     2.- Mientras haya targets pendientes de leer, hacer:
     3.- Buscar el siguiente target. Sea [texx]\displaystyle t[/texx]
     4.- Si [texx]\displaystyle t_0\ne t[/texx], devolver indicador de "no tiene target único"
     5.- Repetir bucle en 2
     6.- Devolver indicador de "sí tiene target único"
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 988


Ver Perfil
« Respuesta #7 : 17/07/2017, 12:33:40 pm »

Buenas Tardes Feriva y SqrMatrix (Matrixciado  :cara_de_queso: ) ....


Cita de: Feriva
Hola, Sqrmatrix. Gracias por esta aportación.

Aunque aún no he probado cosas ni pensado del todo lo que se dice, una pregunta: ¿Se sabe más o menos en qué medida aumentan los targets respecto del aumento de la cantidad de cifras?
 
Veo que, en el ejemplo, un número de sólo cinco cifras tiene 105 targets, si el aumento no es “lineal” por así decirlo, un RSA como el 230 puede tener una barbaridad de  targets, supongo.

Un cordial saludo.


• Con mil disculpas anticipadas,... "empíricamente" es dable considerar, que para un natural de 230 digitos, como el RSA-230, se dará una muy grande cantidad de "targets" ya que el inicio del criterio de factorización que nos expone SqrMatrix, es:

Cita de: SqrMatrix
El método de Hugo Scolnik se basa, como muchos métodos modernos de factorización, y como él mismo indica, en la expresión de un entero [texx]n[/texx] como diferencia de cuadrados.


• Esto ya nos lo expuso "Fermat" en su metodología de factorización, el cual, también nuestro Amigo SqrMatrix, nos lo explicó en uno de sus hilos anteriores,... mismo que sinceramente, no lo comprendí a fondo como mi cabezota quisiera, a pesar que Feriva, también me lo explicó,.. y es que, no es que uno sea un retrasado,... sino que los fundamentos empleados, son "limitativos", donde al no darse y/o hallarse mas, se lo concluye y teoriza, negando la re-evolución de nuevos criterios, que complementen, lo que por ejemplo nos quiso decir Fermat con su pequeño Teorema de [texx]2^{p-1}\equiv{1} (mod \ p)[/texx]  el cual está "incompleto" por mas que se tengan las demostraciones matemáticas re-validadas, que se tengan.... y lo dice, un sencillo y testarudado, empesinado con la primalidad, que ya pronto dejará de inmiscuirse con sus criterios triviales.
→ El asunto es que, siendo [texx]m[/texx] un natural impar compuesto, se puede escribir este como una diferencia de cuadrados, donde:  [texx]m=x^{2}-y^{2}[/texx]

Por Ejemplo

Siendo [texx]m=35[/texx] con [texx]p=5[/texx] y [texx]q=7[/texx] como sus divisores, operamos:

[texx]rz=\sqrt[ ]{m}=5.91...[/texx]

Damos valores a [texx]x[/texx] a partir de [texx]rz+1[/texx] osea: [texx]x=6[/texx]

Siendo [texx]x=6[/texx] determinamos [texx]y[/texx] en la ecuación:

[texx]m=x^{2}-y^{2}[/texx]

[texx]y^{2}=x^{2}-m[/texx]

[texx]y=\sqrt[ ]{x^{2}-m}[/texx]

Donde:

[texx]y=\sqrt[ ]{6^{2}-35}=1[/texx]


Verificamos que:

[texx]35=6^{2}-1^{2}=36-1=35[/texx]


• En efecto, esto ya nos lo dice Fermat,... PERO,... la complejidad de su metodología, está en determinar [texx]x[/texx] donde determinar este valor para un compuesto [texx]m[/texx] de 230 digitos, es muy, muy, muy complejo, por mas que se hagan mejoras y simplificaciones a la metodología de Fermat... ó no es así?
→ Estimo, que esto mismo, es lo que acompleja, a la metodología de factorización de Hugo Scolnik, donde nuestro amigo SqrMatrix, implementa la evaluación con targets, mismos que al buscar el valor de [texx]x[/texx] estamos, al igual que Fermat, buscando un polvo lunar, en nuestro sistema solar.


Spoiler (click para mostrar u ocultar)


◘ Si se me permite.... un complemento a la consulta de Feriva,... y es que, ¿La cantidad de targets se incrementa ó no se incrementa, de acuerdo a la proporción [texx]Kp[/texx] que tenga el divisor [texx]p[/texx] en compuestos [texx]m[/texx] de un mismo tamaño en digitos?





Saludos Cordiales...
En línea
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #8 : 18/07/2017, 05:24:41 am »

Saludos, Victor Luis. Me alegra verte por estos lares :sonrisa:

Cita de: Feriva
Hola, Sqrmatrix. Gracias por esta aportación.

Aunque aún no he probado cosas ni pensado del todo lo que se dice, una pregunta: ¿Se sabe más o menos en qué medida aumentan los targets respecto del aumento de la cantidad de cifras?
 
Veo que, en el ejemplo, un número de sólo cinco cifras tiene 105 targets, si el aumento no es “lineal” por así decirlo, un RSA como el 230 puede tener una barbaridad de  targets, supongo.

Un cordial saludo.


• Con mil disculpas anticipadas,... "empíricamente" es dable considerar, que para un natural de 230 digitos, como el RSA-230, se dará una muy grande cantidad de "targets" ya que el inicio del criterio de factorización que nos expone SqrMatrix, es:

En realidad, los targets se dan en un determinado módulo, y el número de targets en dicho módulo depende principalmente del propio módulo, y de la clase residual a la que pertenezca el entero a factorizar. Para factorizar un entero, se necesitan targets de varios módulos. Pero todo esto se irá viendo a medida que vaya añadiendo los diferentes apartados (como ejemplo, para factorizar el RSA-640, bastan 90 targets (en 90 módulos diferentes), lo cual no es mucho). El problema está en lo que ya dije, que de momento no hay forma de determinar qué targets son los que nos interesan para factorizar sin conocer la factorización del entero.

Lo que dices después, quizá lo he entendido mal, pero me parece entender que consideras equivocado seguir trabajando con el método de Fermat. Si es así, yo creo que no es correcto lo que dices. El método de Fermat permite factorizar enteros con ciertas características, y variantes del método permiten factorizar enteros bastante grandes. Precisamente varios algoritmos de los más potentes utilizan variaciones del método de Fermat (los denominados de cribas cuadráticas), que permiten factorizar enteros bastante grandes. Es cierto que no pueden factorizar enteros arbitrariamente grandes, pero creo que, de momento, son los métodos que permiten factorizar los enteros más grandes.
En línea
sqrmatrix
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 118


Ver Perfil
« Respuesta #9 : 18/07/2017, 05:51:16 am »

Aplicación del Criterio de Euler para determinar si un entero [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx]

En el apartado del algoritmo para buscar targets, indiqué que podía aplicarse el Criterio de Euler para determinar si un entero es un cuadrado módulo [texx]\displaystyle c[/texx], pero lo que indiqué era erróneo. Voy a explicar aquí el procedimiento que habría que seguir.

El Criterio de Euler sólo se puede aplicar a módulos [texx]\displaystyle c[/texx] que sean primos impares y a enteros [texx]\displaystyle a[/texx] primos relativos con [texx]\displaystyle c[/texx]. Por suerte, los cuadrados modulares tienen características que nos permitirán reducir las comprobaciones a primos impares (salvo el factor [texx]\displaystyle 2[/texx]) para poder aplicar el Criterio de Euler.

En lo que sigue, hablaré de residuos cuadráticos módulo un entero, y de cuadrados módulo un entero. Un entero [texx]\displaystyle a[/texx] es cuadrado módulo un entero [texx]\displaystyle m[/texx] si existe un entero [texx]\displaystyle b[/texx] tal que [texx]\displaystyle a\equiv b^2\pmod{m}[/texx]. Un entero [texx]\displaystyle a[/texx] es un residuo cuadrático módulo un entero [texx]\displaystyle m[/texx] si [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle m[/texx] y, además, se cumple [texx]\displaystyle mcd(a,m)=1[/texx]. A veces llamaré "cuadrados" a los residuos cuadráticos, ya que lo que estamos buscando es determinar si un entero [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx], sin importarnos si es residuo cuadrático o no.

Lo primero que vamos a hacer es factorizar el entero [texx]\displaystyle c[/texx]. Consideraremos la factorización [texx]\displaystyle c=2^{\alpha_0}\cdot\prod p_i^{\alpha_i}[/texx], con [texx]\displaystyle p_i[/texx] primo impar, [texx]\displaystyle \alpha_0\ge 0[/texx], [texx]\displaystyle \alpha_i\ge 1[/texx]. Si [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx], también lo será módulo cada uno de sus factores primos elevados a su máximo exponente. Y viceversa, si [texx]\displaystyle a[/texx] es un cuadrado módulo cada uno de los factores primos de [texx]\displaystyle c[/texx] elevados a su máximo exponente, también será cuadrado módulo [texx]\displaystyle c[/texx]. Si [texx]\displaystyle a[/texx] no es cuadrado módulo alguno de los factores primos de [texx]\displaystyle c[/texx] elevados a su máximo exponente, tampoco será cuadrado módulo [texx]\displaystyle c[/texx]. Y es esto lo que vamos a utilizar para determinar si [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx].

Dividiremos los diferentes casos que se nos pueden dar. Veremos cómo determinar si un entero [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle p_i^{\alpha_i}[/texx], tanto si es primo relativo con [texx]\displaystyle p_i^{\alpha_i}[/texx], como si no.

Caso [texx]\displaystyle p_0=2[/texx]

Éste es un caso especial, ya que no se puede aplicar el Criterio de Euler por no ser el primo impar. No obstante, se puede aplicar un criterio simple. Tenemos los casos especiales [texx]\displaystyle \alpha_0=\{1,2,3\}[/texx], es decir, los módulos [texx]\displaystyle 2^1=2, 2^2=4, 2^3=8[/texx]. En módulo [texx]\displaystyle 2[/texx], [texx]\displaystyle a[/texx] siempre será un cuadrado, pues o bien [texx]\displaystyle a\equiv 0\equiv 0^2\pmod{2}[/texx], o bien [texx]\displaystyle a\equiv 1\equiv 1^2\pmod{2}[/texx]. Ambos valores son cuadrados módulo [texx]\displaystyle 2[/texx].

Para el caso de los módulos [texx]\displaystyle 2^2=4, 2^3=8[/texx], tenemos que [texx]\displaystyle a[/texx] es un cuadrado módulo uno de estos valores en los siguientes casos:

[texx]\displaystyle
a\equiv 0\equiv 0^2\pmod{2^2=4} \\
a\equiv 1\equiv 1^2\pmod{2^2=4} \\
a\equiv 0\equiv 0^2\pmod{2^3=8} \\
a\equiv 1\equiv 1^2\pmod{2^3=8}
[/texx]

No hay más cuadrados módulo [texx]\displaystyle 2^2=4[/texx] ni [texx]\displaystyle 2^3=8[/texx].

Para el caso [texx]\displaystyle 2^{\alpha_0}[/texx], con [texx]\displaystyle \alpha_0>3[/texx], tenemos dos casos.

El primer caso es cuando [texx]\displaystyle mcd(a,2^{\alpha_0})=1[/texx]. En este caso, se cumple que [texx]\displaystyle a[/texx] es residuo cuadrático módulo [texx]\displaystyle 2^{\alpha_0}[/texx] si es residuo cuadrático módulo [texx]\displaystyle 2^3=8[/texx]. Y en módulo [texx]\displaystyle 2^3=8[/texx] sólo hay un residuo cuadrático, que es [texx]\displaystyle 1\pmod{2^3=8}[/texx]. Es decir, que [texx]\displaystyle a[/texx] es residuo cuadrático módulo [texx]\displaystyle 2^{\alpha_0}[/texx] si [texx]\displaystyle a\equiv 1\pmod{8}[/texx].

El segundo caso es cuando [texx]\displaystyle mcd(a,2^{\alpha_0})=2^{\beta}[/texx], [texx]\displaystyle \alpha_0\ge\beta>0[/texx]. Sea [texx]\displaystyle a=a'\cdot 2^{\beta}[/texx], de donde se deduce que [texx]\displaystyle mcd(a',2^{\alpha_0})=1[/texx].

En este caso, se cumple que [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle 2^{\alpha_0}[/texx] si [texx]\displaystyle \beta=\alpha_0[/texx], o si [texx]\displaystyle \beta[/texx] es par y además [texx]\displaystyle a'[/texx] es un residuo cuadrático módulo [texx]\displaystyle 2^{\alpha_0-\beta}[/texx]. Si [texx]\displaystyle \alpha_0-\beta\ge 3[/texx], por lo visto antes, esto último significa que tiene que cumplirse [texx]\displaystyle a'\equiv 1\pmod{8}[/texx]. Si [texx]\displaystyle \alpha_0-\beta<3[/texx], se tiene que cumplir [texx]\displaystyle a'\equiv 1\pmod{2^{\alpha_0-\beta}}[/texx]. Si [texx]\displaystyle \alpha_0-\beta=1[/texx], por cumplirse [texx]\displaystyle mcd(a',2^{\alpha_0})=1[/texx], también se cumplirá la congruencia. Si no, sólo queda el caso en el que [texx]\displaystyle \alpha_0-\beta=2[/texx], en cuyo caso tiene que cumplirse [texx]\displaystyle a'\equiv 1\pmod{4}[/texx].

Caso [texx]\displaystyle p_i[/texx] primo impar

En este caso se puede aplicar el Criterio de Euler, ya que estamos ante un primo impar. Tenemos, a su vez, dos casos.

El primer caso es en el que [texx]\displaystyle mcd(a,p_i^{\alpha_i})=1[/texx]. Si [texx]\displaystyle \alpha_i=1[/texx], se puede aplicar el criterio de Euler directamente. Si no, basta observar que [texx]\displaystyle a[/texx] es un residuo cuadrático módulo [texx]\displaystyle p_i^{\alpha_i}[/texx] si es un residuo cuadrático módulo [texx]\displaystyle p_i[/texx]. Por tanto, aquí también se aplica el Criterio de Euler al entero [texx]\displaystyle a[/texx], y al primo [texx]\displaystyle p_i[/texx], sin el exponente.

El otro caso es en el que [texx]\displaystyle mcd(a,p_i^{\alpha_i})=p_i^{\beta}[/texx], [texx]\displaystyle \alpha_i\ge\beta>0[/texx]. Sea [texx]\displaystyle a=a'\cdot p_i^{\beta}[/texx], de donde se deduce que [texx]\displaystyle mcd(a',p_i^{\alpha_0})=1[/texx].

En este caso, se cumple que [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle p_i^{\alpha_0}[/texx] si [texx]\displaystyle \beta=\alpha_0[/texx], o si [texx]\displaystyle \beta[/texx] es par y además [texx]\displaystyle a'[/texx] es un residuo cuadrático módulo [texx]\displaystyle p_i^{\alpha_0-\beta}[/texx]. Por lo visto antes, esto último significa que [texx]\displaystyle a'[/texx] tiene que ser un residuo cuadrático módulo [texx]\displaystyle p_i[/texx]. Por tanto, se puede aplicar el Criterio de Euler como en el otro caso, pero con el valor [texx]\displaystyle a'[/texx].

Se ve cómo curiosamente, para el caso [texx]\displaystyle p_0=2[/texx], el valor [texx]\displaystyle 2^3=8[/texx] se comporta casi como los primos impares respecto de los cuadrados modulares.

Procedimiento

Ahora hay que juntar lo anterior. Para ello, partimos de la factorización de [texx]\displaystyle c[/texx] de la forma [texx]\displaystyle c=2^{\alpha_0}\cdot\prod p_i^{\alpha_i}[/texx].

Si [texx]\displaystyle c[/texx] es par, comprobamos si [texx]\displaystyle \alpha_0[/texx] vale [texx]\displaystyle 1, 2 ó 3[/texx]. En ese caso, si [texx]\displaystyle a\not\equiv \{0,1\}\pmod{2^{\alpha_0}}[/texx], entonces [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx], y hemos terminado la comprobación. Lo contrario supondría que [texx]\displaystyle a[/texx] sería un cuadrado módulo [texx]\displaystyle 2^{\alpha_0}[/texx], y no tendríamos que comprobar nada más para este factor.

En caso de que [texx]\displaystyle \alpha_0>3[/texx], comprobamos si [texx]\displaystyle mcd(a,2^{\alpha_0})=1[/texx]. Si es así, si [texx]\displaystyle a\not\equiv 1\pmod{8}[/texx], [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx], y hemos terminado la comprobación. Lo contrario supondría que [texx]\displaystyle a[/texx] sería un cuadrado módulo [texx]\displaystyle 2^{\alpha_0}[/texx], y no tendríamos que comprobar nada más para este factor.

En caso de que [texx]\displaystyle mcd(a,2^{\alpha_0})=2^{\beta}[/texx], comprobamos si [texx]\displaystyle \beta=\alpha_0[/texx]. Si es así, [texx]\displaystyle a[/texx] sería un cuadrado módulo [texx]\displaystyle 2^{\alpha_0}[/texx], y no tendríamos que comprobar nada más para este factor. Si no, comprobamos si [texx]\displaystyle \beta[/texx] es par. Si no es así, [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx], y hemos terminado la comprobación. Si es así, hacemos [texx]\displaystyle a'=\dfrac{a}{2^{\beta}}[/texx], y comprobamos si [texx]\displaystyle a'\equiv 1\pmod{8}[/texx]. Si no es así, [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx], y hemos terminado la comprobación. Lo contrario supondría que [texx]\displaystyle a[/texx] sería un cuadrado módulo [texx]\displaystyle 2^{\alpha_0}[/texx], y no tendríamos que comprobar nada más para este factor.

Una vez comprobado el caso de [texx]\displaystyle 2^{\alpha_0}[/texx], procedemos a comprobar el caso del resto de primos elevados a su máximo exponente.

Comprobamos si [texx]\displaystyle mcd(a,p_i^{\alpha_i})=1[/texx]. Si es así, aplicamos el Criterio de Euler a los valores [texx]\displaystyle a[/texx] y [texx]\displaystyle p_i[/texx]. Si se cumple, [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle p_i^{\alpha_i}[/texx] y pasamos al siguiente factor. Y si no se cumple, [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx] y hemos terminado la comprobación.

En caso de ser [texx]\displaystyle mcd(a,p_i^{\alpha_i})=p_i^{\beta_i}[/texx], [texx]\displaystyle \alpha_i\ge\beta_i>0[/texx], comprobamos si [texx]\displaystyle \beta_i=\alpha_i[/texx]. Si es así, [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle p_i^{\alpha_i}[/texx] y pasamos al siguiente factor. Si no, comprobamos si [texx]\displaystyle \beta[/texx] es par. Si no lo es, [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx] y hemos terminado la comprobación. Si es par, hacemos [texx]\displaystyle a'=\dfrac{a}{p_i^{\beta}}[/texx], y aplicamos el Criterio de Euler a los valores [texx]\displaystyle a'[/texx] y [texx]\displaystyle p_i[/texx]. Si se cumple, [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle p_i^{\alpha_i}[/texx] y pasamos al siguiente factor. Y si no se cumple, [texx]\displaystyle a[/texx] no es un cuadrado módulo [texx]\displaystyle c[/texx] y hemos terminado la comprobación.

Si en todos los factores se cumple que [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle p_i^{\alpha_i}[/texx], entonces [texx]\displaystyle a[/texx] es un cuadrado módulo [texx]\displaystyle c[/texx].
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 988


Ver Perfil
« Respuesta #10 : 18/07/2017, 06:23:54 pm »

Buenas Noches Feriva y SqrMatrix (Matrixciado)....

◘ En "Factorización" de naturales compuestos semiprimos, no niego la utilidad de aplicar Fermat,... Pero es tan solo para finalizar el proceso de factorización, es decir, determinar el valor natural de los divisores [texx]p[/texx] y [texx]q[/texx] donde:

[texx]p=x-y[/texx]

[texx]q=x+y[/texx]


• Tan solo para esto,.... siendo la problemática, el determinar [texx]x[/texx] y en esto, el algoritmo de Fermat, es insatisfactorio, al menos para factorizar simples e incomplejos compuestos semiprimos, como los que adjunto a este tu hilo, para que pruebes de factorizarlos, donde yo antes, ya apliqué, mi nuevo criterio de evaluación estructural y los factoricé.
→ Cuando digo "simples" e "incomplejos" compuestos, es que como observarás, los compuestos semiprimos adjuntados, están en proporción [texx]Kp=99,99999... \ %[/texx] donde al ser un tanto grandecitos en digitos los compuestos, esto no quiere decir que el compuesto sea un cuadrado perfecto de algun primo, ni que se den divisores primos relativamente a muy escasa distancia de la raiz cuadrada, como si fueran tanto [texx]p[/texx] y [texx]q[/texx] primos gemelos,... simplemente, que en naturales compuestos como de 75 digitos, entre [texx]Kp=99,999999999 \ %[/texx] y [texx]Kp=99,999999998 \%[/texx] hay un gran margen de distancia en la recta numérica, donde podrán darse un sin fin de naturales primos, como posibles candidatos a divisores, lo cual, estructuralmente, evaluámos (ahora) por ejemplo una distancia estructural de 2,5 billones en menos de 40 segundos, lo que equivale aproximadamente, en la recta numérica natural, a evaluar la divisibilidad de naturales primos, dados en un rango de 61 digitos, esto en naturales compuestos semiprimos de 125 digitos, comos que adjunto en este tu hilo.... lo que con Fermat, es muy difícil poder hacerlo, por no decir imposible. (en tiempo polinomial-práctico)


◘ He leído (a groso modo y a mi entender) los documentos PDF que enlazaste, donde en: Avances de la factorización en enteros (pag 4) y Scolnik (pag 6) se menciona algo que no sabía, sobre lo que es en sí, el proceso de cifrado en la criptografía que utiliza RSA, mismo que (a priori y según pseudo-comprendí) se daría, una modalidad, no así para factorizar el compuesto que conforma RSA como productos de dos primos [texx]p[/texx] y [texx]q[/texx], sino, para dar directamente, con la llave que abre y rompe el cifrado,... esto, a-priori, desde el enfoque estructural, ya que eso entiendo y se dice en las páginas que te indico de los documentos PDF que enlazaste...




Saludos Cordiales...

* AFTE-060_LISTA_COMPUESTOS_para_SQRMATRIX.rar (2.58 KB - descargado 1 veces.)
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 988


Ver Perfil
« Respuesta #11 : Ayer a las 05:18:01 am »

Buenos Días Feriva y SqrMatrix....



◘ Como mencionaste que estabas analizando la determinación de targets en compuestos de 640 digitos, es que me permití conformar compuestos semiprimos de: 640, 960 y 1120 digitos, mismos que pongo adjunto a este tu hilo y estos, son fáciles y simples de factorizar,... indicando esto, porque antes los factoricé, no tan solo los conformé, reiterando, que son "fáciles" porque el divisor [texx]p[/texx] está en proporción [texx]Kp=99,9999999... \ %[/texx]

• Por ejemplo, siendo [texx]m[/texx] un compuesto semiprimo de 40 digitos, el mayor divisor [texx]p[/texx] será de 20 digitos, siendo también que en la proporción [texx]Kp[/texx] debemos considerar 20 fracciones decimales, dándonos así, una aproximacíon mas exacta del divisor [texx]p[/texx] al emplear la proporción [texx]Kp[/texx].
→ Pero sin ir muy lejos, consideremos que de las 20 fracciones decimales de [texx]Kp[/texx] sean las primeras 10 tan solo de "9" nueves, osea: [texx]Kp=99,9999999999.......... \%[/texx] completando aleatoriamente las restantes 10 fracciones decimales.

• Si conformas compuestos semiprimos, con estas proprociones [texx]Kp[/texx] como te indico, para unos 10 compuestos de 640 digitos por ejemplo, y me los das para que los factorice,... pues pondríasme a prueba, para que verifiques, si tan solo conformé estos compuestos ó es que también los factoricé, como hubete dicho,... y es que hay algunos que podrían, darme como "trucador" como Gaussito, cosa que ante mis amigos, no es dable el proceder en mi persona,.... por lo que, te pediría, me pongas a prueba.





Saludos Cordiales....

* AFTE-061_LISTA-II_COMPUESTOS_para_SQRMATRIX.rar (5.96 KB - descargado 1 veces.)
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!