Foros de matemática
26/09/2017, 12:52:34 am *
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: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Observaciones sobre el método de factorización de Hugo Scolnik  (Leído 401 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: 125


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: 125


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: 125


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



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: 125


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: 125


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: 125


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: 1.057


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: 125


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: 125


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: 1.057


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 6 veces.)
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.057


Ver Perfil
« Respuesta #11 : 20/07/2017, 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 5 veces.)
En línea
sqrmatrix
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 125


Ver Perfil
« Respuesta #12 : 23/07/2017, 10:46:55 am »

Saludos, Victor Luis

◘ 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é.

No estoy del todo de acuerdo en lo que afirmas. Estoy de acuerdo en que el método de Fermat, y cualquier otro de los existentes, no nos permiten factorizar en tiempo razonable todos los enteros compuestos que queramos, en especial los grandes compuestos (salvo casos especiales fácilmente factorizables). Pero no estoy de acuerdo en que el método que propones sea una solución, porque padece del mismo problema. Sólo puede factorizar ciertos enteros compuestos. Estoy de acuerdo en que tu método permite factorizar en tiempo razonable ciertos enteros que otros métodos no pueden. Pero hay enteros compuestos que tu método no puede factorizar en tiempo razonable. Y es el mismo problema que indicas que tiene el método de Fermat.

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

No acabo de entender esto. Creo que diferencias la factorización del entero utilizado en RSA con la llave que permite descifrar un mensaje cifrado con RSA. En realidad es equivalente. El que tiene la llave tiene la factorización del valor usado en RSA, que forma parte de la llave, y es lo que le permite descifrar los mensajes. Si alguien logra descifrar el entero usado en RSA, podrá descifrar los mensajes cifrados con ese valor (con la factorización se puede calcular [texx]\displaystyle \phi(n)[/texx], que permitirá calcular el valor [texx]\displaystyle d[/texx] de la clave privada).

◘ 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]

Lo que mencióné del RSA-640 era simplemente un ejemplo. Quizá lo expresé mal, y dí a entender que lo había factorizado directamente. Esta factorización la he podido hacer precisamente porque conocía su factorización de antemano, con la cual he podido seleccionar los targets que me permiten factorizar el RSA-640 con el método de Hugo Scolnik. Si pudiera factorizar el RSA-640 sin conocer su factorización de antemano, podría factorizar el resto de los RSAs del RSA Challenge, y anunciar sus factorizaciones, y el problema de la factorización se habría resuelto, al menos para enteros del tamaño del RSA-640. No estoy tratando de factorizar grandes enteros con el método de Hugo Scolnik. He indicado en varias ocasiones que este método no permite factorizar grandes enteros (salvo, por supuesto, que se haya encontrado la forma de hacerlo y se mantenga en secreto). Simplemente estoy mostrando unas observaciones que he hecho del método.

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

Yo no creo que mientas respecto a lo que dices. Estoy seguro de que eres capaz de factorizar sin problemas los productos de dos primos que cumplan las características que indicas. Así que no te voy a poner a prueba. Los que te tendrían que poner a prueba son lo que no creen lo que dices, para convencerse ellos mismos de que dices la verdad.
En línea
sqrmatrix
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 125


Ver Perfil
« Respuesta #13 : 23/07/2017, 11:07:33 am »

Composición de targets

Supongamos que tenemos el entero [texx]\displaystyle n=r\cdot s[/texx], y que hemos encontrado targets válidos no triviales módulo [texx]\displaystyle c_1[/texx] y [texx]\displaystyle c_2[/texx], correspondientes a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados, donde [texx]\displaystyle mcd(c_1,c_2)=1[/texx]. Sean estos targets:

[texx]\displaystyle
n+a_1\equiv b_1\pmod{c_1} \\
n+a_2\equiv b_2\pmod{c_2}
[/texx]

¿Se pueden combinar dichos targets para obtener un target con un módulo mayor?. La respuesta es que sí, como explica Hugo Scolnik en su trabajo, y se puede hacer gracias al Teorema Chino de los Restos. Para aplicarlo, basta plantear el sistema de congruencias:

[texx]\displaystyle
x\equiv a_1\pmod{c_1} \\
x\equiv a_2\pmod{c_2}
[/texx]

Se obtendrá una congruencia de la forma [texx]\displaystyle x\equiv a_{1,2}\pmod{c_1\cdot c_2}[/texx], donde [texx]\displaystyle a_{1,2}[/texx] será un cuadrado módulo [texx]\displaystyle c_1\cdot c_2[/texx], al ser [texx]\displaystyle a_1[/texx] y [texx]\displaystyle a_2[/texx] cuadrados módulo [texx]\displaystyle c_1[/texx] y [texx]\displaystyle c_2[/texx] respectivamente. Ahora, basta calcular [texx]\displaystyle b_{1,2}[/texx] simplemente haciendo [texx]\displaystyle n+a_{1,2}\equiv b_{1,2}\pmod{c_1\cdot c_2}[/texx], que también será un cuadrado módulo [texx]\displaystyle c_1\cdot c_2[/texx] al ser [texx]\displaystyle n+a_1[/texx] y [texx]\displaystyle n+a_2[/texx] cuadrados módulo [texx]\displaystyle c_1[/texx] y [texx]\displaystyle c_2[/texx] respectivamente (por definición de target). Además, este target será válido al ser válidos los targets de partida, y se corresponderá a la misma diferencia de cuadrados al corresponderse los targets de partida a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados, ya que si [texx]\displaystyle n=b'^2-a'^2[/texx], se cumple, por definición de target, y por ser correspondientes a la misma diferencia de cuadrados, [texx]\displaystyle a'^2\equiv a_1\pmod{c_1}[/texx], [texx]\displaystyle b'^2\equiv b_1\pmod{c_1}[/texx], [texx]\displaystyle a'^2\equiv a_2\pmod{c_2}[/texx], [texx]\displaystyle b'^2\equiv b_2\pmod{c_2}[/texx] y, por el Teorema Chino de los Restos, se cumplirá [texx]\displaystyle a'^2\equiv a_{1,2}\pmod{c_1\cdot c_2}[/texx], [texx]\displaystyle b'^2\equiv b_{1,2}\pmod{c_1\cdot c_2}[/texx].

Esto se puede repetir para cualquier cantidad de targets módulo [texx]\displaystyle c_i[/texx], siempre que todos los [texx]\displaystyle c_i[/texx] sean primos relativos entre sí, y que los targets sean todos correspondientes a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados. Aplicando el método explicado, se puede ir obteniendo un target módulo un número cada vez mayor. En caso de que los [texx]\displaystyle c_i[/texx] no sean primos relativos entre sí, se aplicará el Teorema Chino de los Restos Generalizado de la misma forma en que se ha explicado.

Targets únicos, targets válidos y targets no válidos en la composición de targets

Lo anterior se ha aplicado a targets correspondientes a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados. ¿Qué ocurre si uno de los targets no se corresponde con la misma diferencia de cuadrados a los que se corresponden el resto de targets?. O lo que es peor, ¿qué ocurre si uno de los targets no es válido?. En ambos casos, la composición de los targets se podrá realizar sin problemas, pero obtendremos un target que, o bien no será válido, o bien será válido, pero no se corresponderá a la diferencia de cuadrados de la que partimos. En todo caso, no podremos distinguir si es válido o no válido sin conocer todas las expresiones de [texx]\displaystyle n[/texx] como diferencia de cuadrados (esto, en una factorización, no es posible, ya que de conocerlas, tendríamos la factorización y no tendríamos que aplicar este método).

Aquí es donde se ve la importancia de los targets únicos. Un target único es un target que se corresponde con todas las expresiones de [texx]\displaystyle n[/texx] como diferencia de cuadrados. Si los targets con los que trabajamos son targets únicos, no hay posibilidad de error. No podremos usar un target correspondiente a una expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados distinta de la que hemos partido, porque sólo hay un target para todas las expresiones como diferencia de cuadrados. Tampoco podemos usar un target no válido, porque no hay targets no válidos. Sólo hay un target, que es válido. Además, en la composición de targets, si utilizamos targets únicos, los targets que vayamos obteniendo por composición, por las propiedades del Teorema Chino de los Restos, serán también targets únicos. El problema es que, por lo indicado por Hugo Scolnik en sus trabajos, el mayor módulo para el que hay targets únicos es [texx]\displaystyle 1440[/texx], lo que no permite obtener targets de módulos grandes (en realidad, [texx]\displaystyle 1440[/texx] es el límite para valores de [texx]\displaystyle n[/texx] impares. Para valores de [texx]\displaystyle n[/texx] pares, el límite es, por las pruebas que he hecho, [texx]\displaystyle 5760=2^2\cdot 1440[/texx], pero no lo he demostrado. En todo caso, este último límite no tiene interés, porque lo primero que se hace con un entero par que se va a factorizar es extraerle el factor [texx]\displaystyle 2[/texx] hasta que quede un valor impar, para el cual ya aplica el límite de [texx]\displaystyle 1440[/texx]).

Así, en caso de no disponer de targets únicos, y si no podemos distinguir los targets válidos de los no válidos, o si no podemos determinar los targets que se corresponden a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados, no podremos combinar con seguridad los targets para obtener un target válido correspondiente a una misma diferencia de cuadrados. Se podrían ir probando combinaciones hasta poder determinar que se ha llegado a un target válido, pero las probabilidades de acertar disminuyen a medida que aumentan los módulos de los targets a combinar, pues recordemos que cualquier conjunto de targets, sean válidos o no, o se correspondan a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados o no, se pueden combinar para obtener un nuevo target, pero este nuevo target puede ser válido o no, y corresponderse o no a la misma diferencia de cuadrados. No hay nada que nos indique que el target es el que buscamos.

Y respecto a las probabilidades de acertar, recordemos el ejemplo del entero [texx]\displaystyle 20437[/texx] módulo [texx]\displaystyle 419[/texx]. Había 105 targets, sólo dos de ellos válidos. Acertar uno de ellos tiene una probabilidad de [texx]\displaystyle \dfrac{2}{105}\approx 0.01905\approx 1.9\%[/texx]. Si lo queremos combinar con otro target, con probabilidades similares, obtendremos una probabilidad de acertar ambos targets válidos del orden de [texx]\displaystyle 0.036\%[/texx]. Y luego ambos targets tienen que hacer referencia a la misma expresión de [texx]\displaystyle n[/texx] como diferencia de cuadrados, lo que reduce aún más las probabilidades. Y el módulo es solamente [texx]\displaystyle 419[/texx], lo que nos da una idea de lo difícil que se va haciendo acertar con el target que buscamos si no disponemos de ninguna forma de saber cuál es. A medida que aumenta el módulo, el número de targets no válidos tiende a aumentar (aunque hay ciertos valores en los que disminuyen respecto a valores anteriores, pero por lo general aumentan), lo que disminuye las probabilidades de tomar targets válidos.

Spoiler (click para mostrar u ocultar)
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.057


Ver Perfil
« Respuesta #14 : 24/07/2017, 09:19:08 pm »

Buenos Días SqrMatrix (Matrixciado...) ....


Cita de: SqrMatrix
No estoy del todo de acuerdo en lo que afirmas. Estoy de acuerdo en que el método de Fermat, y cualquier otro de los existentes, no nos permiten factorizar en tiempo razonable todos los enteros compuestos que queramos, en especial los grandes compuestos (salvo casos especiales fácilmente factorizables). Pero no estoy de acuerdo en que el método que propones sea una solución, porque padece del mismo problema. Sólo puede factorizar ciertos enteros compuestos. Estoy de acuerdo en que tu método permite factorizar en tiempo razonable ciertos enteros que otros métodos no pueden. Pero hay enteros compuestos que tu método no puede factorizar en tiempo razonable. Y es el mismo problema que indicas que tiene el método de Fermat.

• Los compuestos (Tipo-RSA) que adjunté y adjunto ahora otros mas, son "facilmente factorizables" ya que antes de dártelos, los he factorizado con la metodología clásica (salvo los ultimos ajustes desarrollados) de la "Factorización Estructural", donde los ultimos compuestos RSA-3072 (de 3.072 digitos) se los deben factorizar, con la metodología que utilicen, cada uno en NO mas de 10 minutos, cuando mucho y es que esta condicionante, se aplica también a mi metodología y la cumplo,... siendo interesante, que nuestro Amigo El_Manco, nos lo factorice en un promedio digamos de 5 minutos, dado que él fue superando mis factorizaciones expuestas anteriormente.
→ Al decir "facilmente factorizables" reitero, que son compuestos, donde el divisor [texx]p[/texx] está en una proporción [texx]Kp=99,9999999.... \ %[/texx] respecto al valor de la raiz cuadrada, donde para un compuesto de digamos 1000 digitos, consideramos 500 fracciones decimales en la proporcion [texx]Kp[/texx] y para hacerlo "facilmente factorizable" conformamos la proporción [texx]Kp[/texx] con 250 fracciones decimales de "9" completando las demás 250 fracciones decimales, aleatoriamente, dándose un divisor [texx]p[/texx] algo cerca de la raiz cuadrada,.... siendo que en compuestos un algo grandecitos, como los ultimos adjuntados, la factorización estructural, los factoriza en un tiempo razonable,... lo que esperamos nuestro Amigo El_Manco, nos lo haga en menor tiempo, algo saludable para continuar mejorando nuestra metodología de factorización.

• Es claro que "por ahora" con la factorización estructural, no podemos factorizar compuestos pequeños como los dados por RSA;.... PERO a eso vamos apuntando, recuerda que con Feriva, nos involucramos, en la tarea de factorizar el RSA-230, donde este compuesto, se lo debe llegar a factorizar, en un tiempo exagerado de 1 día, cuando mucho,.... debiendo hacer esto, con la metodología final ya ajustada y mejorada, lo cual se va dando, con los analisis que estoy realizando y las consultas que voy haciendo a mis Maestros Feriva y El_Manco.
→ Si precisas, te puedo adjuntar, los compuestos y sus divisores, adjuntados en las listas, para que analices tus targets;... pero lo interesante, es que los factorices, con los desarrollos que vayas haciendo y sería muy bueno, (claro está en tu tiempo disponible) que conformes compuestos, dados con la proporcion [texx]Kp[/texx] de cantidad de "9" en sus fracciones decimales, tal como te lo explique, osea, tan solo la cuarta parte de "9" del tamaño en digitos que tenga el compuesto, donde yo deberé poder factorizarlos, en poco tiempo y darte a responder, los divisores de los compuestos semiprimos que me des.




Saludos Cordiales....

* AFTE-062_LISTA-III_COMPUESTOS_para_SQRMATRIX.rar (24.02 KB - descargado 5 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!