Foros de matemática
23/03/2017, 09:17:15 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: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: 1 [2] 3   Ir Abajo
  Imprimir  
Autor Tema: Factorización-III Análisis de los Compuestos RSA  (Leído 1101 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #20 : 02/03/2017, 06:02:38 pm »

Buenas Noches Feriva...


Cita
Su producto se acerca al RSA, pero no consigo acercarme más de momento, es:


179694915979410667329161284495732461563675618080126000708889

188355317264603414909334933722478686507552308558642010158651

811357915321414361929903864592297741188721529988323380928767

87266827822416125561567741338953508412368129840907


• Una consulta... Este número que indicas, son 4 números ó solo son parte de uno...?
→ Mira que la raiz cuadrada de RSA-230 tiene 115 digitos, donde si ambos divisores son de igual tamaño, esto se dará hasta la proporcion [texx]kp=45 \%[/texx] ó quizás una proporción algo mayor; pero la diferencia en digitos entre los divisores [texx]p[/texx] y [texx]q[/texx] de nuestro RSA-230 no será mas de 25 digitos, cuando mucho... al menos eso creo, donde se puede verificar esto, determinando la proporción [texx]kp[/texx] en los RSA que ya fueron factorizados.


• Respecto a tu metodología, hice un desarrollo en Mathematica ya que Python (él muy desesperado...) ya está evaluando en la Zona de Factorización a nuestro RSA-230.
→ Como te decía, el programa busca compuestos semiprimos y los va descomponiendo, según el criterio que te expliqué, sacando la raiz de cada parte y haciendo una sumatoria de estos, donde luego va dividiendo entre {2,3,4,5,6,...} mientras que el cociente sea mayor e igual que [texx]p[/texx] el primer divisor.

• En compuestos de hasta 9 digitos, la metodología es genial... ya parece de adivinos.... puesto que la distancia hacia el divisor [texx]p[/texx] es mínina, cuando mucho de 1, por eso digo de adivinos.
→ Pero en compuestos semiprimos de 15 digitos, se dan distancias respecto al divisor [texx]p[/texx] que casi igualan a la raiz cuadrada del compuesto, lo que para nuestro RSA-230 tendríamos que evaluar una distancia menor a los 115 digitos.

• No sé.... supongo que esto se debe, a que la sumatoria de las raices, lo hice con la parte entera de estos, ya que no pude aplicar la funcion "Round" que tenemos en Python.
→ Por otro lado, evalué tu metodología con compuestos semiprimos dados en proporción [texx]kp=5,0 \%[/texx] hasta [texx]kp=10,0 \%[/texx] que como te dije, hasta compuestos de 9 digitos, resulta genial... pero ampliando hasta [texx]kp=25,0 \%[/texx] se dan distancias ya mayores hacia el divisor [texx]p[/texx]


Cita
Es muy, muy, posible que los primos se parezcan mucho a éstos; casi seguro que empiezan así, uno por 25 ó 26 y el otro por 71 ó 70 (uno empieza por 7 o 69, en eso casi me atrevo a hacer apuestas y todo).

• No te contagies de mi impaciencia... Amigo Feriva... Pero tu conjetura tiene una forma de comprobarlo, que como te dije, si conformamos compuestos [texx]m[/texx] tipo RSA-230, obtenemos el 50% de los digitos de sus divisores, esto con absoluta seguridad.
→ Para conformar un compuesto "Tipo RSA-230" el proceso es simple, tan solo tomamos un número al azar de 230 digitos, donde reemplazamos casi la mitad de sus digitos de la izquierda con la misma cantidad de digitos de la izquierda que tiene el RSA-230.
→ Luego para cada proporción [texx]kp[/texx] determinamos un divisor [texx]p[/texx] respecto a la raiz cuadrada del compuesto conformado y ahí tienes la mitad de los digitos de la izquierda del divisor, donde la cosa está en que se dan distintos para cada proporción [texx]kp[/texx] lo cual es no mas de esperarse.



1° ATAQUE a RSA-230 con PYTHON


Siendo [texx]zf[/texx] la distancia de la Zona de Factorización, realizamos dos particiones de esta.

1°) [texx]d=\displaystyle\frac{zf}{20}[/texx]
Fraccionamos la zona en 20 partes, que serían como las filas de una tabla.

2°) [texx]h=\displaystyle\frac{d}{500}[/texx]
Fraccionamos cada parte en 500 sub-partes, las que serían como las columnas de una tabla.

• Siendo [texx]pf1[/texx] el inicio de la zona de factorización y [texx]pf2[/texx] el final de la misma zona, iteramos 20 veces desde [texx]pf2[/texx] reduciendo con [texx]d[/texx] es decir [texx]pf2=pf2-d[/texx]
→ En cada iteración y/o reducción de [texx]pf2[/texx] iteramos 500 veces reduciendo [texx]pf2=pf2-h[/texx] cargando estos puntos estructurales en un array y/o lista y al terminar esta iteración, cargamos la lista en otra lista, conformándose una matriz ó tabla.

• Ya con esto, con cada punto cargado en la matriz, evaluamos con [texx]v=5000[/texx] valoraciones de referencia, que con una sub-iteracion de 40, evaluamos una distancia de 200000, en cada punto fraccionado de la zona de factorización.
→ Es lo que pude hacer, tomando en cuenta el tiempo de proceso que lleva evaluar toda la matriz con sus sub-iteraciones, donde en sí, la zona de factorización queda fraccionada en 10.000 partes, esperando con esto dar con el punto mismo de factorización y al darse esto, Python nos dirá los divisores primos del compuesto RSA-230... sin precisar el tiempo que nos llevará lograr el cometido.




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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #21 : 02/03/2017, 06:45:34 pm »



• Una consulta... Este número que indicas, son 4 números ó solo son parte de uno...?


Hola, otra vez, Víctor Luis.

Esas cuatro líneas son todo un número de 230 cifras, como el RSA.


Sus primeras 110 cifras coinciden con las del RSA-230, fíajte:


17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864.

En cambio, si tomas la parte entera de la raíz cuadrada del RSA-230 y la elevas al cuadrado, se alejan mucho del RSA, sólo coinciden las 16 primeras

1796949159794106

Como ves, gano a la raíz cuadrada (parte entera) por escandalosa goleada: 94 goles.

Sin duda, créeme, la cosa va por esos números, uno que empieza por 69, 70 ó 71 y otro que empieza por 2; quizá 25...

De hecho acabo de probar eso que te decía con los RSA ya conocidos; y funciona igual, aunque cuando los números son muy cercanos (en cuanto a las dos primeras cifras, digo), produce más error; en este caso no los son, estoy seguro de que las primeras cifras difieren en unas cuatro unidades.

Ah, el método que te dije ha sido un poco ampliado en cuanto a lo dividir por 2,3... Lo que hago ahora es restar fracciones de la suma de raíces a la misma suma y obtengo una familia mayor de números; así puede estudiar mejor cómo varía la cosa. Mañana a ver si te pongo el programa, que tengo que ponerle comentarios, que si no, no se entiende, y ya te explico también lo de formar los números.

Pero hay que acercarse más; ya te daré la zona que me pedías, espera un poco; aunque no sea segura 100%, tendrá muchas posibilidades y espero que lo puedas factorizar.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #22 : 02/03/2017, 07:55:28 pm »

Buenas Noches Feriva...


• He evaluado con tus dos candidatos ó puntos de divisibilidad.


[ 1° PUNTO ]


Código:
pv1=7128144860588516138972741919436003476291593327478791559187195079050193101705443294166190361220785095813859899342617

○ Este punto no puede ser, ya que está en proporción [texx]kp=168,15454 \%[/texx] donde puede que te refieras al segundo divisor [texx]q[/texx]
→ De igual forma, la evaluación es totalmente valida, ya que no empleo divisores primos, tan solo busco determinar el punto de factorización, donde para este candidato, recorri una distancia de:  120.000.000.000  y no se dio la factorización del RSA-230.



[ 2° PUNTO ]


Código:
pv2=2520921214339275354344959560141745155008352813312578575166558284150217970728459040445061476661570244053255804690371

○ Este punto está en proporción [texx]kp=59,4691 \%[/texx] correspondiendo al divisor [texx]p[/texx] que desde el punto estructural que nos dá, he evaluado una distancia de 10.000.000.000 sin dar con la factorización del RSA-230.


• El tiempo de evaluación para cada candidato no fue mucho, aproximadamente de unos 20 minutos, donde no sé la distancia de evaluación que se tiene que realizar para dar con la factorización, ya que para una distancia de 11 digitos, procesaríamos la evaluación en 200 minutos es decir 3 horas con 20 minutos, para cada punto de divisibilidad de tus candidatos, que no sé si esto sería suficiente, donde estimando que los divisores sean del mismo tamaño, la distancia a evaluar sería hasta unos 18 digitos cuando mucho y eso...
→ Si los divisores del RSA-230 difieren en tamaño 1 digito, la distancia a evaluar será menor y mas cuando difieran en mas digitos, lo que facilita de algún modo su factorización, y supongo que esto lo debieron considerar los señores de RSA.

• No he completado los analisis iniciales que hacía, sobre compuestos semiprimos pertenecientes al grupo PIG[13], ya que de acuerdo a esto, las proporciones ciclicas se van dando de forma cuasi-constante, dependiendo a la clase de primos divisores que se dan y que conforman compuestos semiprimos del grupo PIG[13].
→ Recuerda que si [texx]p[/texx] pertenece al grupo PIG[5] con total exactitud y sin que nadie de los nadies lo pueda refutar, el divisor [texx]q[/texx] también pertenecerá al grupo PIG[5] y así con los demás... esto es importante de considerarlo Feriva.




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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #23 : 02/03/2017, 09:11:16 pm »


Hola, Víctor; te cuento.

El programa es éste (no he puesto comentarios explicativos pero hace más o menos lo que te dije:

Spoiler (click para mostrar u ocultar)

Como no es difícil ver vaticinar cuáles serán las cifras, con un margen de error de una unidad, por la que empieza uno o los dos factores;.

Vamos a ver ahora qué valores nos da el RSA-230

Spoiler (click para mostrar u ocultar)

Quizá que empiece por 71 es demasiado grande a tenor de los resultados, pero unas operaciones me han llevado a él; sin embargo, pienso que puede ser un 70 o un 69 o incluso un 68 (hablo del primo grande, no del pequeño)

Cita
Este punto está en proporción kp=59,4691% correspondiendo al divisor p que desde el punto estructural que nos dá, he evaluado una distancia de 10.000.000.000 sin dar con la factorización del RSA-230.


Piensa que si te doy un número de 114 ó 115 cifras y recorres el equivalente a 11 (según el número que pones ahí) no tocas ninguna cifra de delante, no puedes saber cómo empieza el número, ni los otros 102 números que hay delante; es un recorrido muy corto, y no hay manera de hacerlo mucho más largo sin volverse anciano, ése es el problema.

El número pequeño estará de 250000... en adelante, puede que muy adelante, pero no será menor; pero dado que al principio de esos resultados que he obtenido hay uno que empieza por 23... pues bajemos ahí; de ahí, esto con total seguridad, no baja.

Un cordial saludo y buenas noches.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #24 : 03/03/2017, 05:34:49 am »

Buenos Días Feriva...


Cita
Piensa que si te doy un número de 114 ó 115 cifras y recorres el equivalente a 11 (según el número que pones ahí) no tocas ninguna cifra de delante, no puedes saber cómo empieza el número, ni los otros 102 números que hay delante; es un recorrido muy corto, y no hay manera de hacerlo mucho más largo sin volverse anciano, ése es el problema.

• Si tú me das un punto próximo al divisor primo del RSA-230 sea [texx]p[/texx] ó sea [texx]q[/texx] se estima el punto [texx]m[p,q][/texx] y si es así como dices, llegamos al punto de factorización dando grandes pasos.
→ La cosa está en el criterio con el que estima el punto inicial de tu selección, ya que correcto es descender por la estructura, algo que quizás tu lo haces en el otro sentido, es decir, seguimos el descenso de la proporción [texx]kp[/texx] y esto se corrobora con lo que te comento a continuación...


PREGUNTA de EXAMEN en TEORÍA de NÚMEROS.


( Me imagino que esto podría darse en un examen, solo me imagino esto...  :sonrisa_amplia: )

Siendo [texx]m=p\cdot{}q[/texx] un natural compuesto semiprimo, donde desconocemos sus divisores [texx]p[/texx] y [texx]q[/texx], como también desconocemos la zona de factorización y es trivial el aplicar el criterio de divisibilidad con naturales primos, sabiendo tan solo que [texx]z=\sqrt[ ]{m}[/texx]

PREGUNTA.
○ Cómo procedemos a factorizar y/o determinar a los divisores primos, con solo estos datos?  ¿Ó no es posible hacer esto?


Spoiler (click para mostrar u ocultar)


• En tu metodología Feriva... haces una descomposición y la sumatoria de las raíces de las partes descompuestas y con la sumatoria estimas un punto próximo a uno de los divisores.
→ No has considerado en tomar fracciones y/o partes de la misma raíz cuadrada del compuesto [texx]m[/texx] ?

• Esto sin entrar al enfoque estructural, que con Fermat y el Conjunto FV podemos verificar los puntos de cuasi-factorización que nos dá la raiz cuadrada del compuesto semiprimo.
→ Por qué no pruebas de implementar esto en tu metodología, que puede simplificarse el proceso, ya que con lo que comprobe, no es tan simple evaluar el RSA-230, aunque ya hice un desarrollo para esto, cosa que lo dejaré ejecutando, este fin de semana, luego que Python haya recorrido un poco mas con su trabajo, que comparado a esto, es mas complejo.
→ No te olvides determinar la proporción [texx]kp[/texx] en tus evaluaciones, para saber por dónde uno anda, ya que con esta metodología de fraccionamiento de la raiz, se observa una interesante reducción de la proporción [texx]kp[/texx] donde no la utilizamos esta, tan solo vemos como no sigue una secuencia constante, como lo habíamos tomado (al menos mi persona)




Saludos Cordiales...
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #25 : 03/03/2017, 06:01:30 am »

Buenas Feriva...


• La metodología que te dije funciona... mira que podemos factorizar un compuesto de 6 digitos manualmente.

[texx]m=776353[/texx]

[texx]z=\sqrt[ ]{m}=881[/texx]

Con esto tomamos una fracción de la raiz:

[texx]\displaystyle\frac{z}{7}=125[/texx]

Con 125 operamos sobre la raiz y con el compuesto obtenemos [texx]x=944[/texx] para aplicar Fermat, donde:

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

Por ultimo conformamos el divisor:

[texx]p=x-y=944-338=606[/texx]


► A que no adivinas cuál es el divisor [texx]p[/texx] ....?

Spoiler (click para mostrar u ocultar)




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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #26 : 03/03/2017, 07:24:28 am »

Buenas Feriva...


• La metodología que te dije funciona... mira que podemos factorizar un compuesto de 6 digitos manualmente.

Buenos dias, Víctor Luis.

Funciona pero el tiempo en recorrer los posibles divisores depende del valor del número, el cual aumenta una barbaridad en la medida que aumentan las cifras.

Fíjate en este número:

4239043712671652402680509502085873379711077970370529360979111

047742174601905286733913433709805089522538514393599971

compáralo con la parte entera de la raíz cuadrada del RSA-230; que es éste:

4239043712671652402680509502085873379711077970370529360979111

047742174601905286733913433709805089522538514393599”843”

Sólo se diferencia en esas tres últimas cifras, sólo en ésas; sólo 128 unidades mayor nada más, poquísimo.

¿Si conociéramos los primos relacionados con ese semiprimo sería fácil hallar los primos del RSA-230?

Ya te garantizo que no, de hecho ésa es la parte entera del número que te daba anoche y cuyos primos divisores son esos dos que también te daba.

¿A que distancia están los divisores de su raíz? Pues ahí los tienes, tú mismo puedes calcularlo.

Dado el parecido, uno pensaría que los del RSA-230 estarían más o menos a la misma distancia y, ya que, la diferencia es sólo de 128 cifras, daríamos con ellos seguro recorriendo, por ejemplo 1000000000000000000 mil números (quiero decir quedándonos sólo con los 6n+1 o 6n-1, según proceda, que hay en esos mil números). Pero no; o sí, tampoco lo he probado.


Cuando tu tienes un número (vamos a poner uno cualquiera y a suponer que es la parte entera de la raíz de un semiprimo) como pueda ser éste

353637390008967856396748937111243748596098777564738291

y recorres, por ejemplo, 1000000000000 números (los primos candidatos que hay ahí) lo que haces es llegar hasta aquí:

35363739000896785639674893711124374859609”9”777564738291

Donde está ese 9  entre comillas había un ocho. Quiere decir que has probado todos los números posibles de ese nueve hacia atrás combinados sólo con estas cifras de delante:

35363739000896785639674893711124374859609

Si yo cambio una sola cifra de aquí (entre todas las combinaciones que puedo hacer, que son incontables “llones”) obtengo un número que tú no habrás comprobado; ¿ves lo que te quiero decir?

De ahí algunos de mis inventos con matrices y eso, tomando cifras, para probar “bloques” de dígitos a lo largo del número; para ver si hay suerte.

Ante esto, ¿qué se puede hacer?

Hay que inventar (intentarlo) una forma de construir el número cifra a cifra; lo que conllevará rastreo para buscar cada cifra. Ahora bien, nunca se puede estar seguro del todo de cuál puede ser esa primera cifra para seguir deduciendo las demás; hay que suponerlo a tenor de unas pesquisas, como las que he hecho, por ejemplo, e imaginar que hemos acertado. También tenemos que suponer que hemos acertado en la cantidad de cfras de los primos que lo componen (si lo luego no es así... pues no llegaremos a nada, pero no queda más remedio)

¿Cómo hacerlo? Vamos con un ejemplo, con un semiprimo pequeño, para no eternizarnos (lo que propongo es una labor de al menos meses si lo queremos hacer con el RSA-230):



541
 * 409
 = 221269

Supongamos que hemos acertado con la cifra la cifra de algún semiprimo considerando que empieza por 5, y también suponemos que tiene tres cifras, como la raíz del número.

Lo que hacemos es dividir el “RSA” por 500 y tomar la parte entera

>>> 221269/500
442


Ahora multiplicamos
>>> 442*500

221000
Hallamos la diferencia con el “RSA”

>>> 221269-221000

269
En este caso es muy pequeña, sólo 269 unidades, pero es un ejemplo.

Vamos a tomar ahora las dos cifras siguientes (se tomarán de dos en dos) desde 10 hasta 99; y vamos dividiendo, tomando la parte entera y multiplicando:

>>> 221269/510
433
>>> 433*510
220830


Éste ya es mayor que el anterior y la diferencia más grande

 221269-220830=439

Sin embargo, aún no hemos probado todos, tenemos que llegar a 599.

En este caso, al dividir entre  221269/540 ya obtenemos el primo; pero es que es muy pequeño. Lo que ocurrirá normalmente es que uno de los números 510, 511, 512... 599 esté más cercano que todos los demás.

Al encontrarlo, debemos quedarnos sólo con la primera cifra como segura; y este proceso seguirá así con las cifras siguientes, de dos en dos y quedándonos sólo con la primera de ellas. ¿Por qué? Pues verás:

Si yo tengo un RSA que empieza, vamos a poner, por 789..., si yo tomo sólo la segunda y pongo un cero detrás, al llegar a 790 me dirá que es el más parecido, porque la tercera es un 9; por tanto, me quedaría con ese 9, que no es realmente la siguiente cifra. Pero si tomo de dos en dos y me voy quedando sólo con la primera, parece que evitaré esto.

Esto es algo que tengo pensado desde hace tiempo; si me hubiera dedicado a trabajar en ello seguramente estaría mucho más cerca, pero me aburre y a lo que me he dedicado es a inventar otras cosas; porque en el fondo lo que busco es más divertirme que factorizar el RSA :sonrisa: Y, en fin, lo fui dejando y no te dije nada.

Spoiler (click para mostrar u ocultar)

Entonces, te sugiero que pruebes como te digo; uno de los primos empieza, con bastante seguridad, por 2 o por 3 en nuestro RSA; supongamos 2 y supongamos que tienen las cifras de la raíz los dos primos. Haciendo el trabajo entre varios, en unos meses o no sé, pero no demasiado, podría estar factorizado; y si no lo hacemos nosotros y perdemos el tiempo con métodos más largos... lo harán otros que lean esta idea (si verdaderamente funciona, y si funciona en el tiempo que supongo; que estas cosas las cuento siempre sin haber probado todo lo necesario).

Fermat es muy insuficiente para estos números; existe una cosa que se llama criba racional, que estuve mirando por encima, y otra que se llama criba general; ésta última es la que se suele usar y da resultado en plazos largos para factorizar estos números de doscientas cifras.


En fin, resumiendo, se trata de construir el número, no de buscarlo a ciegas (o no a ciegas del todo) si no, es casi imposible en cuanto el número tiene cientos de cifras, ni con criba general: hay que construir el número cifra por cifra, no queda otra.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #27 : 04/03/2017, 06:53:11 am »

Buenos Días Feriva...



Cita
Fíjate en este número:

4239043712671652402680509502085873379711077970370529360979111

047742174601905286733913433709805089522538514393599971

compáralo con la parte entera de la raíz cuadrada del RSA-230; que es éste:

4239043712671652402680509502085873379711077970370529360979111

047742174601905286733913433709805089522538514393599”843”

Sólo se diferencia en esas tres últimas cifras, sólo en ésas; sólo 128 unidades mayor nada más, poquísimo.

¿Si conociéramos los primos relacionados con ese semiprimo sería fácil hallar los primos del RSA-230?

• Comprendo lo que me dices... pero, con las disculpas, no cabezota a priori me dice que no es tanto así, eso de las 128 unidades, por lo que voy a buscar compuestos, no siempre serán semiprimos, (esto va a tu favor) que tengan la misma raiz cuadrada del RSA-230 y esto es dable, porque como ya lo dijimos en otro hilo, cuando el compuesto es grande, se dan otros compuestos con la misma raiz, donde esto no significa que sean divisibles por los mismos divisores primos, ante lo cual comentamos que la raiz cuadrada no es específica en la factorización, tan solo una referencia.
→ Lo que te comenté de la metodología, es que con fracciones tomadas de la raiz cuadrada del compuesto semiprimo, nos posicionamos cerca del "punto de factorización" esto en el enfoque estructural, y en el enfoque de la divisibilidad no posicionamos cerca del punto del divisor [texx]p[/texx] que por eso te puse ese ejemplo, donde con el Conjunto FV, realizamos una generación de [texx]nb[/texx] y damos con el divisor [texx]p=607[/texx]

• Esto mismo lo comprobé con tu compuesto de 42 digitos, que fue donde hice el analisis de esto, ajustando los calculos, para ver si en verdad se podía factorizar el compuesto, es decir, si su raiz nos lo permite hacerlo y así fue.
→ Al realizar el ajuste que te digo, es que comenzó el proceso con datos dados cerca de este punto de factorización, no así desde un inicio, lo que sí es en parte mucha iteración y evaluación y digo en parte, porque es curioso lo que sucede, ya que al dividir la raiz con divisores pequeños, estamos en proporciones [texx]kp[/texx] pequeñas y al dividir la raiz con divisores grandes, estamos en proporciones [texx]kp[/texx] altas, dándose un limite de hasta cuanto podemos dividir la raiz, lo cual no aumenta tantísimo respecto a tu compuesto 42 digitos y el RSA de 230 digitos, y eso fue lo que me llamo la atención.

• La constante ó razón con que se incrementa ó disminuye la proporción [texx]kp[/texx] no es la misma en todo el trayecto, lo cual es logico, siendo por decirlo asi casi constante al iniciar desde [texx]kp=99,95 \%[/texx] y ya desde [texx]kp=89,91 \%[/texx] se advierte un aumento, lo que acelera el proceso, debiendo tomar fracciones mas pequeñas y ya con [texx]kp=49,95 \%[/texx] por mas que tomemos fracciones pequeñas, el proceso se sigue acelerando, lo que nos favorece.
→ No lo he evaluado aún con el programa de factorización de 21 digitos, donde hago mis comprovaciones; pero lo haré, ahora que tengo el fin de semana libre y te lo comentaré.

◘ Cuando volví de la tienda, el computador se había apagado, por algún corte, supongo, donde la evaluación de Python se perdío, ante lo cual, ya inicié la evaluación de factorización con la metodología que te comenté y veremos si nos dá algó.

• Preguntabas si conociéramos la relación de los divisores primos... y es que ya te lo dije un par de veces,... Si [texx]p[/texx] pertenece al grupo PIG[5] por ejemplo, con "total y absoluta seguridad" (esto puedes apostarlo donde y con quieras...) el divisor [texx]q[/texx] también será del grupo PIG[5]
→ Es decir, para un compuesto de PIG[13] como es nuestro RSA-230 ambos divisores serán y/o pertenecerán al mismo grupo PIG, algo que si le da la complejidad que le dotan; pero no la imposibilidad de ser factorizado.

• Yo no evalúo con divisores, pero si tienes un candidato divisor [texx]p[/texx] digamos de PIG[7] debes buscar su correspondiente divisor [texx]q[/texx] que debe ser también de PIG[7] que de no darse esto, no tienes que evaluar la divisibilad con el compuesto.
→ Esto puede resultar trivial, ya que para un [texx]p[/texx] operamos [texx]q=\displaystyle\frac{m}{p}[/texx] donde en vez de evaluar el grupo PIG de [texx]q[/texx] con solo evaluar el resto de la división, determinamos si son divisores del compuesto... verdad?
→ Pero en base a los primos relacionados, que nos dicen estos de la pertenecia de grupos PIG de los divisores, se obtiene una constante de generación para [texx]q[/texx] y su correspondiente [texx]q[/texx] que limitado por el compuesto [texx]m[/texx] solo se dá una opción de candidato [texx]q[/texx] sin tener que realizar la división con [texx]m[/texx] donde solo verificamos la pertenecia de grupos PIG e incluso ni esto, porque ya sabemos para un [texx]p[/texx] se genera con la constante un [texx]q[/texx] verificando tan solo que sea del Conjunto FV y luego que sea primo, para recién evaluar la división con el compuesto [texx]m[/texx]


○ Voy a hacer una evaluaciones y luego seguimos este tema.... OK





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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #28 : 04/03/2017, 01:13:14 pm »


Hola, Víctor Luis, buenos días.

Creo que no explico bien lo que quiero decir; quizá porque todavía no he encontrado lo que quiero; pero voy a hacer una metáfora.

Cuando un artista pinta un cuadro más menos grande, no empieza a dibujar con todo detalle un árbol, por ejemplo, y después le da color y tal, sino que que dibuja un boceto muy por general por todo el lienzo. Del mismo modo, cuando empieza a dar color, no pinta sólo sobre una zona aislada, va haciéndolo por todo el lienzo, marcando grandes zonas de sombras y luces; y, ya después, poco a poco, va pasando sobre esas zonas detallando un poco más paulatinamente. De la misma manera, un músico, un compositor no empieza escribir una partitura, en principio tiene una melodía, corta, un tema, con la cual armoniza, hace un armazón para sustentar más notas. Después piensa en la forma, en cuántas veces e va a repetir, en qué variaciones va a hacer, dónde va a poner los puentes... también va “pintando” por toda la partitura. O un director cine, no rueda linealmente las escenas, a veces graba una del principio, otra de la mitad de la película, otra del final... el montaje viene cuando está acabada; y por supuesto, todo eso se hace sobre guión.

Cuando tú dices que si un método no es determinista y te quejas, ¿a qué te refieres? En realidad no te refieres a que no sea determinista, porque tarde o temprano (a veces muy tarde) se factorizará el número, lo que seguramente quieres decir es que se dan palos de ciego, y, sobre todo, no se conservan los “bocetos”, sino que se dice “éste no es, fuera”. Y, así, hasta que se dé con el divisor, a fuerza de probar e insistencia.

Todos los métodos existentes son muy poco o nada constructivos, están muy lejos del proceso artístico del pintor, el músico o el director de cine (o del novelista, porque los novelistas que saben también lo hacen así, no linealmente). Y, al ser poco artísticos, en consecuencia, también son métodos poco matemáticos; y no es por largos ni porque pueda no acabarse, no es ésa la cuestión, es porque no son constructivos.

Todavía no sé bien cómo se haría para terminar llegando al divisor de esa manera, pero puedo poner un ejemplo algo parecido al de ayer y ser un poco más concreto:


El número 14351 = 113*127 con parte entera de la raíz: 119.

Tenemos que
14351 / 119 = 120

119*120
 = 14280

14351-14280
=71

La diferencia es de 71.

Puedo intentar cambiar la primera cifra por 2,3,4... a ver si encuentro una diferencia más pequeña

119 diferencia 71
219 diferencia 116
319 diferencia 315
419 diferencia 105
519 diferencia 338
619 diferencia 114
719 diferencia 690
819 diferencia 428
919 diferencia 566

No la encuentro y me quedo con el 1 de primera cifra.

Ahora cambio la segunda y encuentro estas diferencias según lo explicado


109 diferencia 72
119 diferencia 71
129 diferencia 32
139 diferencia 34
149 diferencia 47
159 diferencia 41
169 diferencia 155
179 diferencia 31
189 diferencia 176
199 diferencia 23

Me quedo con 19 y pruebo a cambiar la última, encuentro estas diferencias:

190 diferencia 101
191 diferencia 26
192 diferencia 143
193 diferencia 69
194 diferencia 189
195 diferencia 116
196 diferencia 43
197 diferencia 167
198 diferencia 95
199 diferencia 23

Me quedo con 199; que no es divisor; pero vuelvo a dar otra pincelada a la primera, y acabando en 99... y en este caso me sigo quedando igual, con 199; no sirve.

No sirve, pero lo que he hecho ha sido ir moldeando un número, cincelándolo, no he ido tirando lo obtenido, sino que he hecho cambios progresivos a partir de los resultados (pocos cambios en el ejemplo, con un número largo serían más).

Esto es lo que hay que buscar, algo así, pero que sirva, claro, que se vaya acercando más hasta llegar a un divisor; no importa que se tarde, porque el método es constructivo.

Si tu método no se parece a esto... no sueñes con factorizar nunca números gigantes en menos de varios años o lustros  (ni tú ni nadie; salvo avances tecnológicos o gran suerte, tipo la que tiene el que le toca la lotería varias veces).

Hay que trabajar por todo el número, por todo, como con el cuadro, dando pinceladas a todas las cifras; pero para llegar a un acabado perfecto poco a poco, siempre construyendo sobre lo obtenido y estando cada vez más cerca de ello, no sin saber si estamos más cerca o más lejos. 

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #29 : 05/03/2017, 09:02:07 am »

Buenas Tardes Feriva


Cita
No sirve, pero lo que he hecho ha sido ir moldeando un número, cincelándolo, no he ido tirando lo obtenido, sino que he hecho cambios progresivos a partir de los resultados (pocos cambios en el ejemplo, con un número largo serían más).

Esto es lo que hay que buscar, algo así, pero que sirva, claro, que se vaya acercando más hasta llegar a un divisor; no importa que se tarde, porque el método es constructivo.

Si tu método no se parece a esto... no sueñes con factorizar nunca números gigantes en menos de varios años o lustros  (ni tú ni nadie; salvo avances tecnológicos o gran suerte, tipo la que tiene el que le toca la lotería varias veces).

Hay que trabajar por todo el número, por todo, como con el cuadro, dando pinceladas a todas las cifras; pero para llegar a un acabado perfecto poco a poco, siempre construyendo sobre lo obtenido y estando cada vez más cerca de ello, no sin saber si estamos más cerca o más lejos.


• Pues sí... reconozco que por mi impaciencia, voy modificando las metodologías, intentando hacerlas mas rápidas, aunque estas son, como digo, determinsitas, es decir, que nos dará la factorización del compueto, tarde ó temprano, donde que sea mas tarde no va de mi agrado y por eso, busco otras maneras de hacerlo, para que sea mas temprano y no es que las deseche ó no tengan madera de construcción, bueno, no tanto así para ustedes con el enfoque de ahora... pero, me asusta y desesperta, el que tenga que esperar la factorización del RSA-230 en cuestión de años como dices, ni aún meses, puesto que mi estimación es de hacerlo en cuestión de días, cuando mucho y a eso aspiro y por ello me metí en esto.
→ Disculpa que no haya probado tu algoritmo, ni te haya apoyado mucho en el analisis de tu criterio metodológico y es que amigo, el tiempo pasa volando y la salud no es tan recia como antes...  :triste:

• Como te decía, en estos ultimos días, he ido desarrollando unas cuantas metodologías de factorización, que las he ido enumerando como "FACTO", repasando asibrevemente estas serían, desde el principio:

FACTO-I
○ Determinar la proporción iclica-estructural, desde el inicio de la estructura numérica, que nos llevará al punto de factorización.
→ El proceso es muy, muy lento y podemos decirlo asi, absurdo para un compuesto grande como el RSA-230, ya que no completamos los analisis iniciales.

FACTO-II
○ Factorizar el compuesto RSA-230 mediante la proporción [texx]kp[/texx] iniciando desde [texx]kp=99,99 \%[/texx] reduciendo con [texx]-0,01 \%[/texx] hasta [texx]kp=5,0 \%[/texx]
→ La evaluación no dio resultados, puesto que empleamos una proporción [texx]kp[/texx] de apenas 2 fracciones decimales, mas fue un recorrido de trastrillaje superficial, para familiarizarnos con el tamaño del RSA-230 y no verlo como algo tan grande ni tan complejo.

FACTO-III
○ Buscamos el punto de factorización, en la zona de factorización. Luego de hacer varias comprobaciones, factorizando compuestos semiprimos de 21 digitos para toda proporción [texx]kp[/texx] de una fracción decimal, encontré que hay una zona dónde debemos buscar el punto de factorización, lo que simplifica el proceso y no sé si esto lo plicaría Fermat cuando factorizó para Mersenne.
→ Esta evaluación quedó a medias, porque se cortó la energía y no supe hasta dónde avanzó Python.

FACTO-IV (La pregunta de examen...)
○ Sabiendo la zona de factorización, desde dónde comenzar el proceso de evaluación, por pura intuición y empirismo, busqué como acercarme al punto de factorización, encontrando que la raiz cuadrada del compuesto nos lo dá, al tomar fracciones de esta misma, aplicada al inicio de la zona de factorización, nos aproxima al punto de factorización.
→ Esta evaluación acabo de reiniciarla donde Python ya va por la proporción [texx]kp=88,98079 \%[/texx] lo cual es una referencia, ya que no me baso en la proporción [texx]kp[/texx] sino que luego de ajustar la zona con las fracciones de la raiz cuadrada, para saber dónde estamos, es que calculo la proporción [texx]kp[/texx] lo cual es inversamente proporcional al recorrido que hacemos en la zona de factorización.

• Esto lo analicé, de inicio con tu compuesto de 42 digitos:

[texx]m=425895541296481876121938841622630742547983[/texx]

Con sus divisores:
[texx]p=630260821152408424063[/texx]
[texx]q=675744909096122697841[/texx]

 Sabemos que el divisor [texx]p[/texx] está en una proporción [texx]kp=96,5759000345 \%[/texx] que son 10 fracciones decimales y que con hasta 3 iteraciones damos con el divisor específico.

 Pero es mucho evaluar con 10 fracciones decimales, me refiero, desde [texx]kp=99,9999999999 \%[/texx] hasta [texx]kp=1,0000000001 \%[/texx]


• Para nuestro RSA-230 tendríamos que tomar un [texx]kp[/texx] de 53 fracciones decimales, cubriendo toda la extensión de la zona de factorización y si daremos con la factorización del compuesto... pero en mucho, mucho tiempo... a menos que tengamos un poco de suerte... y eso no lo tengo, por eso no juego a la lotería nacional.
→ A pesar de esto, hice un desarrollo para [texx]kp[/texx] de 25 fracciones decimales, reduciéndose esta no de a [texx]-1[/texx] sino de una cantidad mayor, para hacer un recorrido rápido en toda la zona y luego volver a hacer el mismo recorrido, pero continuando el anterior,... lo que tampoco es directo, mas en algún momento sí o sídaremos con la factorización y la evaluación inicial con esta metodología, no dio resultados  :triste:

FACTO-V
○ En los compuestos semiprimos, el punto de factorización solo tiene unas cuantas proporciones cíclicas hacia este punto, al menos eso consideré, porque no concluí los analisis iniciales.
→ Como tu tratas de determinar el punto de divisibilidad mismo, yo hice un programa y/o desarrollo, donde con la proporción [texx]kp[/texx] de solo 2 fracciones decimales, obtenemos un probable [texx]p[/texx] y con este calculamos [texx]m[p,q][/texx] el cual lo fraccionamos hacia las proporciones ciclicas que pueda tener, de tal forma que nos llevarían a determinar el ciclo estructural mismo y con esto el punto de factoriación.

• Luego de muchas evaluaciones, infructuosas, me puse a pseudo-analizar esto, considerando que [texx]p[/texx] y [texx]q[/texx] pertenecen al grupo PIG[7] que por supuesto tendremos que [texx]m=p\cdot{}q[/texx] pertenece al grupo PIG[13] y esto se lo apuesto a quien quiera y lo que quiera... :sonrisa_amplia:
→ Resulta que las proporciones cilcicas no son tan limitadas como suponía, pero encontré que las proporciones ciclicas en poco mas del 95% de los compuestos de 21 digitos evaluados para todo [texx]kp[/texx] son divisibles entre una constante, para este caso, me refiero a que [texx]m[/texx] es PIG[13] con divisores de PIG[7], faltando analizar para divisores de los otros grupos PIG.
→ Esto aún no lo he aplicado a nuestro RSA-230, pues me falta ver como se dan las proporciones ciclicas en los divisores de los otros grupos PIG... pero esto surge la otra metodología.

FACTO-VI
○ Analizando compuestos semiprimos de 21 digitos, con [texx]m[/texx] de PIG[13] y divisores [texx]p[/texx] y [texx]q[/texx] de PIG[7] para proporciones entre [texx]kp=99,9 \%[/texx] hasta [texx]kp=90,0 \%[/texx] buscando como se van dando las distancias desde el inicio de la zona de factorización al punto de factorización, mismas que cargué en una lista y las exporté al finalizar el proceso, es que saqué la proporción porcentual que tenían respecto a la raiz cuadrada, cargadas en otra lista y exportadas al final, junto con lo anterior.

• No me dediqué a tratar de determinar la razón con que se van dando estas proporciones de raiz que denominaremos como [texx]kz[/texx] ya que es muy complejo para mi pobre arsenal de herramientas matemáticas.
→ Simplemente, copié la lista de [texx]kz[/texx] y volvi a ejecutar el programa, donde esperaba que se den otras proporciones [texx]kz[/texx] ya que los compuestos [texx]m[/texx] se toman de forma aleatoria y además empleamos [texx]kp[/texx] de una fracción decimal, por lo que era poco probable que se dé el mismo compuesto, donde resultó que eran prácticamente las mismas proporciones [texx]kz[/texx] tan solo variando en la ultima fracción decimal.

• Con esto, modifiqué el programa, para que inicialmente cargue una lista de proporciones [texx]kz[/texx] para compuestos semiprimos de 21 digitos en el intervalo de [texx]kp(99,9)\% a (90,0)\%[/texx] y luego conforme compuestos [texx]m[/texx] en este mismo intervalo de proporciones [texx]kp[/texx] y los factorice con la lista de proporciones [texx]kz[/texx]
→ El resultado me abrió los ojos, de lo agotado que estaba,ya que estas evaluaciones, analisis y desarrollos los fui haciendo de corrido, por el empecinamiento que tengo y mas que todo por lo emocionante que resulta todo esto.... Como te decía, el resultado fue que se factorizaron todos los compuestos, tan, tan rápido que solo pude ver el ultimo mensaje de "** PROCESO TERMINADO **".
→ Como soy excéptico de mí mismo, es que dudé de esto, por lo muy rápido del proceso, pensando que estaba factorizando los mismo compuestos, por lo cual, cargue en una lista, los compuestos de los cuales se tomaban sus proporciones [texx]kz[/texx] controlando luego que los compuestos a factorizar, no sean estos mismo y al ejecutar el programa, sucedió lo mismo, se factorizarón así de rápido.

• Bueno, pero esto parecía algo trivial de considerarlo, ya no mas como algo valido, digno de analizarlo, por lo que modifiqué el programa, para que esta vez con la misma lista de proporciones [texx]kz[/texx] tomadas desde proporciones [texx]kp[/texx] de "una fracción decimal" se factoricen compuestos tomados al azar, con proporciones [texx]kp[/texx] (toma en cuenta esto) de "dos fracciones decimales" donde las distancias de ajuste con [texx]kz[/texx] al punto de factorización, son mayores, al menos eso creía, y no fue así, tan solo se demoró unos cuántos milisegundos mas en cada factorización, siendo que ahora desde [texx]kp=99,99 \%[/texx] hasta [texx]kp=90,01 \%[/texx] se factorizan diez veces mas la cantidad de compuestos semiprimos y así sucedió, todos fueron factorizados en muy, muy poco tiempo.
→ Ya de verdad agotado, solo comprobé lo mismo con compuestos de 22 digitos, donde para [texx]kp[/texx] de dos fracciones decimales, se dieron algunas fallas, esto, porque la determinación del punto de factorización, se realizaba, con el minimo de iteraciones, por lo que incrementando un poco tan solo esto y al volver a ejecutar el programa, todos los compuestos fueron factorizados en muy poco tiempo... y ahí lo dejé, y es que exageré en mis horas de evaluación...



◘ Como te dije, analicé eso de la diferencia en los ultimos digitos de la raiz cuadrada del RSA-230 que me comentabas.


Código:
Distancia de 115 dgts
8478087425343304805361019004171746759422155940741058721958222095484349203810573467826867419610179045077028787199642

DESDE:
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199928645376798761628276271624060016080157804251662033341189875407814487433199692658711982372206672404298627440409624664

HASTA:
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199937123464224104933081632643064187826917226407602774399911833629909971782403503232179809239626282583343704469196824306


• "Desde" y "Hasta" son los limites, donde los naturales dados entre estos, todos tienen la misma raiz cuadrada que tiene el RSA-230 siendo esta distancia de 115 digitos, que es la misma que tiene la raiz cuadrada.
→ No exporté compuestos, porque son muchisisísimos, pero ahi ya tienes dos... No sé si a esto te referías, donde entendí, que teniendo un compuesto con la aproximación de su raiz al de la raiz del RSA-230, se podría factorizar este con no muchas evaluaciones.

• El valor natural de nuestro RSA-230 es:

Código:
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689

→ Donde este está entre los limites "Desde" y "Hasta" que te puse, coincidiendo con estos, tan solo en los primeros 114 digitos desde la izquierda:
Código:
179694915979410667329161284495732461563675618080126000708889188355317264603414909334933722478686507552308558641999

→ Siendo diferente con los 116 digitos desde la derecha:
Código:
29221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689


• Espero esto te sirva para tus analisis y el desarrollo de tu metodología, que como te dije, no la comprendo en sí y ya me explicaste que estás en proceso de creación estructural científica de tu metodología.
→ Estamos en lo mismo, solo que los analisis y desarrollos que hago, son de aporte al criterio estructural, que como comprenderas, en los desarrollos "FACTO" expuestos, he ido evaluando la factorización del RSA-230 desde varias proporciones estructurales dentro de la zona de factorización, buscando un proceso, que nos permita factorizarlo en poco tiempo, y esto debe ser en cuestion de días, ni siquiera un mes, cuando mucho una semana de proceso contínuo... y es que hasta ahora, solo hemos iniciado con el abordaje a este reto... y recuerda que tengo que cumplir con un pedido que tengo, que es entregar la piel de "tigre de bengala" para nuestro amigo y maestro [texx]\mathbb{El}[/texx]_[texx]\mathbb{Manco}[/texx] necesitando para esto, un desarrollo metodológico que factorice todo compuesto RSA, en sí todo compuesto semiprimo.




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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #30 : 06/03/2017, 08:11:58 am »


Buenos días, Víctor Luis.

Me parece bien que distingas entre casos según los números; un método que puede ser muy rápido frente a otro, en números más o menos pequeños, respecto de números grandes puede comportarse al revés, y el lento ser más rápido.

Estuve ayer todo el día, desde la mañana hasta la noche, haciendo un programa bastante complicado, con una función dentro de otra y varios bucles y cosas. Iba cambiando todos los dígitos de la raíz, tal como te dije por ahí, y a la vez conservando los otros; buscando cuáles de esos números hacían de “divisores” más cercanos.

Una vez que terminaba, usaba el menor de todos y sacaba una media con la raíz (bueno, no una media, varias, según diversas conjeturas) y volvía al bucle con otro número; y volvía a hacer lo mismo.

Obtuve parejas de números cuyo producto era muy cercano, pero cuanto más cercano... necesitaba divisores más distanciados, teniendo uno de ellos muy pocas cifras en comparación con las que deben tener los factores de un semiprimo.

Al levantarme, se me ha ocurrido cómo construir una ecuación diofántica de una sola variable para ir buscando el número de una manera que no es que sea constructiva del todo, pero sí lo es más que las cribas; ¿cuánto tardará el ordenador en resolver dicha ecuación?  No lo sé, supongo que mucho en el caso de los RSA, todavía es un esbozo, no he desarrollado ni pensado nada bien del todo.

Te pondría el programa y en qué consiste lo que voy a intentar; pero, si no hay resultados, me temo que no va a interesarte, así que espero.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #31 : 09/03/2017, 10:06:08 am »

Buenas Tardes Feriva...



Cita
Al levantarme, se me ha ocurrido cómo construir una ecuación diofántica de una sola variable para ir buscando el número de una manera que no es que sea constructiva del todo, pero sí lo es más que las cribas; ¿cuánto tardará el ordenador en resolver dicha ecuación?  No lo sé, supongo que mucho en el caso de los RSA, todavía es un esbozo, no he desarrollado ni pensado nada bien del todo.

Te pondría el programa y en qué consiste lo que voy a intentar; pero, si no hay resultados, me temo que no va a interesarte, así que espero.


• Le dí "actualizar" a la pestaña y se perdió todo lo que te estaba escribiendo... respecto al "Enfoque Estructural"...
→ Sobre lo que dices... de "ecuaciones Diofánticas" estoy en la luna... no me he tomado el tiempo de estudiar esto, porque casi todo, no está relacionado con el enfoque de la estructura numérica, lo que no es contrariar a la matemática; pero no hay información relevante que me sirva y se aplique a esto.

• Lo que te decía... es sobre qué datos tenemos de inicio, para comenzar el proceso de factorización.... tan solo que [texx]m=p\cdot{}q[/texx] conociendo el compuesto [texx]m[/texx] y desconociendo a sus divisores [texx]p[/texx] y [texx]q[/texx] lo cual es el problema de la factorización.
→ Algo que también conocemos y/o podemos calcular, es [texx]z=\sqrt[ ]{m}[/texx] la raiz cuadrada del compuesto, donde sabemos que:
       [texx]p < \sqrt[ ]{m} < q[/texx]
Es decir que el divisor [texx]p[/texx] es menor que la raiz y que el divisor [texx]q[/texx] es mayor que la raiz... A menos que [texx]m[/texx] sea un cuadrado perfecto, donde [texx]p=\sqrt[ ]{m}[/texx] y por ende, tenemos que [texx]p=q[/texx] lo cual no se aplica, en los compuestos semiprimos, dados por RSA.

• También decía que Fermat está en lo correcto, al decir que [texx]m=x^{2}-y^{2}[/texx] donde determinando [texx]x[/texx] dterminamos [texx]y=\sqrt[ ]{x^{2}-m}[/texx] y con esto conformamos:

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

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

→ Esto es irrefutable, ni yo podría contradecir esto, ya que lo aplico, para finalizar el proceso de factorización, donde [texx]m[p,q][/texx] es el  "Punto de Factorización" y sabiendo esto, teniendo que [texx]c=m[p,q][/texx] determinamos:

[texx]x=(\displaystyle\frac{c}{2})+1[/texx]

Y ya con [texx]x[/texx] tenemos por factorizado al compuesto semiprimo [texx]m[/texx]


• ¿QUÉ MÁS tenemos...?
→ Desde el enfoque matemático de la divisibilidad, tenemos que [texx]p[/texx] y [texx]q[/texx] son naturales primos, donde para RSA-230 [texx]p[/texx] está inmerso en el mar de primos dados hasta la raiz cuadrada del compuesto... de tal forma, que al no contar con una función generadora de solo naturales primos, ni podemos determinar cuántos primos se dan exactamente hasta 115 digitos,  que es la aproximación que nos dá la raiz cuadrada del compuesto RSA-230.

• ¿Qué mas tenemos...?  en nuetra matemática... no lo sé... pero en el enfoque estructural.... tenemos principios y lemas deterministas de factorización....  Luego continúo con esto...





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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #32 : 09/03/2017, 12:03:02 pm »


Muy buenas tardes, Víctor Luis.

Cita
¿QUÉ MÁS tenemos...?

Puede que tengamos algo más; a raíz de una idea que se me ha ocurrido hace un rato; aún no me he puesto a probarla.

El problema de la factorización de semiprimos  es que no es fácil caracterizar los dos primos que componen al semiprimo; y eso es lo que llevo tiempo intentando, desde el verano.

Ocurre que si intentamos hallar unas “medias” para los divisores, por distintos métodos como los que he venido contando y alguno más que no he contado, porque ya no me acuerdo, finalmente esos candidatos que va uno moldeando tienden al valor de la raíz cuadra; o bien pasa eso, o bien no y entonces no sabemos con seguridad cuál es la primera cifra de uno de los factores, sólo podemos conjeturar.

Insisto en que hay que buscar (a lo mejor no existe lo que busco, pero yo creo que sí) construir los divisores cifra a cifra.

Cuando uno, en álgebra, tiene un sistema de ecuaciones, por ejemplo, también tiene una serie de métodos rutinarios (y, si quieres, “aburridos”) por los cuales se llega a las soluciones sí o sí. Eso es lo que me gusta a mí, que las cosas tengan un método o varios (sin detrimento de posibles ideas felices y atajos). Algunos los conozco y los he usado, unos más y otros menos, y muchísimos otros (en cuestiones sobre todo de análisis y cálculo diferencial) no los he usado ni estudiado, pero sé que existen; eso ya me tranquiliza, porque sé que, si necesitara algo sobre esos temas, hay una manera, hay una forma organizada de hacer las cosas.

Una criba no es un método como ésos, por eso te hablo de esta cuestión, porque no me gustan (no tanto como lo otro, no es que no me gusten) las cribas. Es aburrido andar con probaturas que no sabes si te están acercando a la solución. Antes que factorizar el RSA, prefiero dar con un método ineficiente, con el que no se acabe nunca, pero que sea constructivo tal y como expliqué; y por eso me voy a poner ahora dentro de un rato a probar lo que decía.

Si hay algo que merezca la pena, te contaré sin tardar, si no, seguiré buscando.


*Ah, una ecuación diofántica es simplemente una ecuación donde se buscan soluciones que sean enteras; tú mismo sin saberlo las usas. El método para resolver las lineales no es difícil, es de colegio en realidad, pero tampoco hace falta que aprendas, el Wolfram te las soluciona.

Un cordial saludo.
En línea

feriva
Pleno*
*****

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #33 : 10/03/2017, 07:19:58 am »


Buenos días, Víctor Luis.

Vuelvo a responder a tu pregunta “qué tenemos”; o, mejor dicho, sigo respondiendo.

Hice el programa que te dije en dos o tres versiones.

En semiprimos de ocho cifras, en todos los que probé, acertaba siempre la primera cifra de los dos primos. En otros más grandes (incluidos los RSA ya factorizados en los que cuento con la respuesta) ya no era así, a veces acertaba la de uno o bien una de esas cifras se quedaba a distancia de una unidad (la primera cifra por la izquierda, digo, la de más valor). Todo indica que el acierto en la estimación depende en parte de la distancia entre dichos dígitos (y estoy hablando de que los dos factores tengan las mismas cifras, como en la gran mayoría de los RSA).

Eso en cuanto a las pruebas; y seguiré a ver si afino más, espero conseguirlo al menos para uno de los primos, aunque no pueda saber si esa primera cifra es del primo gran o del pequeño (que ésa es otra cuestión, pero menos importante; se probaría con las dos por separado y ya está. Esto multiplicaría el tiempo en el proceso, pero el tiempo no me importa, como te dije, me importa tener seguridad en algo, o  digamos mucha seguridad, aunque no se pueda afirmar del todo que es así).


También tengo estas dos reflexiones, una que desilusiona y otra que cambia el punto de vista y, en consecuencia, ilusiona:

Reglexión que desilusiona.

Si uno piensa en una piscina de bolas de ésas de niños, pero con bolas del tamaño de un perdigón pequeño, e imagina que tiene que buscar una sola bola amarilla entre millones o billones de bolas blancas... supone que encontrar los factores del semiprimo es como si hubiera sólo dos bolas amarillas entre tan inmensa cantidad de blancas; y de momento se llega a la conclusión de que no depende de métodos ni de números, sino que las cosas son así por pura naturaleza, y que es inevitable que se tarde años o más.

Pensamiento que ilusiona.

Pero ahora pensemos en un primo de 200 ó 300 cifras; ¿cuánto tarda el ordenador en saber que es primo usando los métodos habituales? Nada, prácticamente tiempo cero.

Y un primo es una bola amarilla perdida en una psicina de bolas blancas.

Alguien podría alegar:  “sí, pero al ser dos factores hay muchas combinaciones”.

Ese argumento no me vale, porque si hay dos factores, también se multiplica mucho más las cantidades de los números que contienen algún factor, no es ya una sola bola; de hecho se puede poner este ejemplo.

Pensemos en una persona que sabe lo mínimo para descubrir si un número es primo o no. Si, por ejemplo, el número es 127 y él lo único que sabe es que dividiéndolo entre 1, 2, 3... hasta 127, llegará siempre ha la solución, pues hará eso y tendrá que recorrer 127 números.

Si, ahora, a esa persona se le da el semiprimo 13081 y se le pide que encuentre algún número que lo divida, pensará que tardará más. Sin embargo, no es así, pues ese número se compone de los primos 127 y 103, que es menor que 103; como mucho tardará lo que tardé en recorrer 103 números.

Esto es lo básico, lo que podría saber un hombre de hace muchos, muchos siglos, un hombre cuyos descendientes irían sabiendo más cosas.

¿Por qué si nuestro antepasado primitivo encontraba antes el divisor de 13081 que el de 127, por qué, pasados los siglos, no sólo ocurre al revés sino que además se tarda una barbaridad más, una cantidad de tiempo no comparable, en hallar el divisor de un semiprimo?, ¿hemos aprendido todo en cuanto a esta cuestión o nos hemos dejado algún saber por ahí?

Yo creo que no es que nos hayamos dejado ningún saber, sino que, quizá existe la forma y no atendemos a ese saber que podría acortar el tiempo de factorización de los semiprimos (o como es una cuestión de seguridad, sí que la conocen algunos pero no se quiere menear la cosa, no sé realmente).

Dónde puede estar ese “saber” al que no atendemos:

Existe una cuestión conocida como “El problema de Fermi”:

https://es.wikipedia.org/wiki/Problema_de_Fermi

Conozco esto de oídas porque ya sabes que un día me pasee por una facultad de físicas (y poco más).  En fin, léete el enlace, es muy cortito, para qué voy a escribir yo lo mismo.

Basándonos en datos, podemos hacer estimaciones que resulten suficientes para lo que buscamos; aunque esas estimaciones no nos den “demostrativamente” el dato que necesitamos.

Mi idea va por ahí (“qué tenemos”, preguntabas, y te cuento lo que yo tengo para que lo tengas tú también).

Cuento con unas estimaciones sobre la primera cifra (la más grande, la más significativa) de los semiprimos, pero estas estimaciones aún no se acercan todo lo que necesito para poder seguir con la segunda cifra de números tan grandes como los RSA; necesito una seguridad mayor para no perder el tiempo.

Si, por ejemplo, construyo (con primos de 100 cifras conocidos y que empiecen por diferentes dígitos) 20 semiprimos y logro que mi programa (el siguiente que haga o uno de los siguientes)  me dé las primeras cifras de los primos de esos 20 semiprimos en todos los casos... pues seguiré con la segunda; consideraré que es muy difícil que falle. Si con la segunda pasa lo mismo, y con la tercera... y hallo los factores de los veinte... ese día te diré: “mira, Víctor Luis, aquí tienes factorizado del RSA-230 “ (claro que va a ser difícil o quizá imposible; no sólo por la dificultad en sí, matemática, sino también porque los programas que tengo que hacer cada vez son más enrevesados en la medida que se me ocurren nuevas ideas que probar).

Me diste por ahí una lista de semiprimos de 21 cifras y me dijiste que los factorizabas en menos de 5 minutos; te propongo una cosa: intenta hacer un programa que halle la primera cifra del semiprimo que sea de ésos (mediante una estimación) en mucho menos tiempo. Pero no vale el método de criba, tiene que ser como te he dicho, mediante estimación, a lo Fermi, usando promedios, usando cosas de ese estilo.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #34 : 11/03/2017, 07:01:38 am »

Buenos Días Feriva...


RESPONDIENDO a TUS CONSULTAS.


Cita
El problema de la factorización de semiprimos  es que no es fácil caracterizar los dos primos que componen al semiprimo; y eso es lo que llevo tiempo intentando, desde el verano.

• Si con "caracterizar" te refieres a identificar a los primos divisores de un compuesto semiprimo... esto lo hacemos con Fermat al determinar el "punto de factorización".
→ Pero si te refieres a estimar los valores próximos que tienen estos primos divisores, según sea, el conocer el 99% de sus cifras y/o digitos desde la izquierda, faltándonos saber tan solo el ultimo digito de la derecha, que nos dan un maximo de 9 ó 10 posibilidades,... tan solo tendremos la estimación de uno de los divisores del compuesto semiprimo [texx]m[/texx] ya que si este muy probable primo divisor que diremos es [texx]p[/texx] divide exactamente a [texx]m[/texx] se debe comprobar que [texx]q=\displaystyle\frac{m}{p}[/texx] sea un natural primo.

• Dentro de las 10 posibilidades para el ultimo digito de la derecha, sabemos que los primos terminan en {1,3,7,9} según algunas publicaciones leidas, por lo que tenemos 4 candidatos, donde puede que los 4 sean naturales primos, de tal forma que solo uno será el divisor de [texx]m[/texx] y esto, cuando hayamos estimado y/o desarrollado una metodología que nos permita hacer esto.
→ Tal acercamiento, no me parece, tan real y prácticamente aplicable a todo natural semiprimo, del tamaño en digitos que tenga y/o deseemos, porque lo que se está haciendo es determinar un divisor, el [texx]p[/texx] que es mas factible, en base al criterio de la divisibilidad y esto es complejamente eterno para el RSA-230.

◘ Respondiendo a tu comentario... los naturales semiprimos, desde el "Enfoque Estructural" son lo mas simple de comprender, dándonos un resultado determinista, que como dijiste, que sin importar la complejidad que tenga, es decir, el tiempo de proceso que lleve hacerlo, con "absoluta" seguridad que daremos con los dos divisores primos.



Cita
Eso en cuanto a las pruebas; y seguiré a ver si afino más, espero conseguirlo al menos para uno de los primos, aunque no pueda saber si esa primera cifra es del primo gran o del pequeño (que ésa es otra cuestión, pero menos importante; se probaría con las dos por separado y ya está. Esto multiplicaría el tiempo en el proceso, pero el tiempo no me importa, como te dije, me importa tener seguridad en algo, o  digamos mucha seguridad, aunque no se pueda afirmar del todo que es así).

◘ Si tienes un candidato [texx]d[/texx] a primo divisor de un compuesto semiprimo [texx]m[/texx] el saber si este es el pequeño ó el grande, es simple, tan solo se lo compara con raiz cuadrada, donde siempre se cumplirá que:

[texx]p < \sqrt[ ]{m} < q[/texx]



Cita
Reglexión que desilusiona.

Si uno piensa en una piscina de bolas de ésas de niños, pero con bolas del tamaño de un perdigón pequeño, e imagina que tiene que buscar una sola bola amarilla entre millones o billones de bolas blancas... supone que encontrar los factores del semiprimo es como si hubiera sólo dos bolas amarillas entre tan inmensa cantidad de blancas; y de momento se llega a la conclusión de que no depende de métodos ni de números, sino que las cosas son así por pura naturaleza, y que es inevitable que se tarde años o más.

• Sobre esto... comprendo que tu complejidad radica en que, es un tanto difícil de identificar las bolas amarillas, respecto a la restante cantidad menos dos de bolas que son blancas.
→ Lo haremos un poco mas complejo... diremos que las dos bolas (divisores) son blancas, con tan solo un punto plomo de un amstron de diámetro, donde las bolas están dadas y/o mostradas con su cara blanca del todo, por lo que no podemos ver ese punto plomo... qué tal...?

◘ Su factorización, es decir, el determinar las dos bolas divisores, es posible, factible y precesable, sin incluir en esto a la obra de la naturaleza, ya que como dijiste y me enseñaste, los números son elementos imaginarios.
→ Fíjate que al estar volcadas las bolas blancas, no podemos saber siquiera cuáles son primos, lo que es innecesario saberlo, tan solo determinar el "Punto de Factorización" y con esto... determinamos a las dos bolas blancas con punto plomo, los divisores del mar de bolas blancas que es el compuesto semiprimo.


Spoiler (click para mostrar u ocultar)



Cita
Pensamiento que ilusiona.

Pero ahora pensemos en un primo de 200 ó 300 cifras; ¿cuánto tarda el ordenador en saber que es primo usando los métodos habituales? Nada, prácticamente tiempo cero.

Y un primo es una bola amarilla perdida en una psicina de bolas blancas.

Alguien podría alegar:  “sí, pero al ser dos factores hay muchas combinaciones”.

Ese argumento no me vale, porque si hay dos factores, también se multiplica mucho más las cantidades de los números que contienen algún factor, no es ya una sola bola; de hecho se puede poner este ejemplo.

◘ Como te dije, al ser tan solo dos bolas de divisores primos, en el enfoque estructural, esto es lo mas básico y elemental, donde un día, en las Universidades de matemática, al entrar al tema de Factorización, se iniciará con la "factorización de compuestos semiprimos" por ser básica y elemental antes de entrar al tema de la factorización de compuestos no semiprimos.



Cita
¿Por qué si nuestro antepasado primitivo encontraba antes el divisor de 13081 que el de 127, por qué, pasados los siglos, no sólo ocurre al revés sino que además se tarda una barbaridad más, una cantidad de tiempo no comparable, en hallar el divisor de un semiprimo?, ¿hemos aprendido todo en cuanto a esta cuestión o nos hemos dejado algún saber por ahí?

Yo creo que no es que nos hayamos dejado ningún saber, sino que, quizá existe la forma y no atendemos a ese saber que podría acortar el tiempo de factorización de los semiprimos (o como es una cuestión de seguridad, sí que la conocen algunos pero no se quiere menear la cosa, no sé realmente).

Dónde puede estar ese “saber” al que no atendemos:

RESPUESTA. En el ENFOQUE ESTRUCTURAL, al menos a priori, respecto a primalidad y factorización... no sabiendo decir, en qué mas repercutirá este enfoque.



Cita
Me diste por ahí una lista de semiprimos de 21 cifras y me dijiste que los factorizabas en menos de 5 minutos; te propongo una cosa: intenta hacer un programa que halle la primera cifra del semiprimo que sea de ésos (mediante una estimación) en mucho menos tiempo. Pero no vale el método de criba, tiene que ser como te he dicho, mediante estimación, a lo Fermi, usando promedios, usando cosas de ese estilo.

• Si quieres te doy una lista de compuestos semiprimos a factorizar, donde los divisores están en proporción [texx]kp[/texx] de varias fracciones decimales, para toda proporción [texx]kp[/texx] es decir, desde [texx]kp=99,99999 \%[/texx] hasta [texx]kp=1,00001 \%[/texx]


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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #35 : 11/03/2017, 02:35:46 pm »

Hola, Víctor Luis, buenas tardes.

Cita
Si con "caracterizar" te refieres a identificar a los primos divisores de un compuesto semiprimo... esto lo hacemos con Fermat al determinar el "punto de factorización".

En parte el método de Fermat sí está relacionado con cierta “caracterización” de los dos primos, desde el momento en que considera un número mayor que la raíz y otro menor; lo que ocurre es que eso es insuficiente en cuanto a lo que yo me refiero; es parte de lo que hay que considerar, sí, sin duda, pero con eso solamente... no hacemos nada si pretendemos emprender la hazaña de factorizar un primo de más de 200 cifras.

No puedo concretar mucho, no puedo decir mucho más de lo que ya he dicho sobre  en qué consistiría ese intento de caracterizar los primos; y más bien sería ir caracterizando cifras una a una; los primos quedarían caracterizados al final, si se logra eso, hablaba de una caracterización parcial solamente.
¿Cómo? Pues aún no me sale nada que sirva para números grandes; pero me quedan por probar cosas, esto es largo (ahora te cuento una cosa “antigua” que pensé que, creo, te gustará).

Cita
Dentro de las 10 posibilidades para el ultimo digito de la derecha, sabemos que los primos terminan en {1,3,7,9} según algunas publicaciones leidas


Claro, porque las demás cifras son pares o el 5. Pero la primera cifra por la derecha es la menos significativa de todas, la de menos valor; en cambio, si conozco la primera por el otro lado y le pongo todo ceros detrás (tantos como cifras tiene la raíz menos una cifra) ya tengo un número muy grande, cercano a los divisores; o no tan cercanos, pero, desde luego, sí muchísimo más que un número de un dígito, no hay color.

Sería bueno poder factorizar el par siguiente y el anterior o al menos uno de ellos, pero son muy grandes también; al decir esto me baso en lo siguiente, pongo un ejemplo:

Tomemos un semiprimo de tamaño “humano” para ilustrarlo: 356519.

Al menos la inmensa mayoría de las veces será más fácil factorizar el par  356520 que el semiprimo, ya que, al dividir por 2 me queda un número más pequeño:

178260

Y es par además, lo que suele pasar muchas veces con los pares que flanquean a los semiprimos, que son múltiplos de potencias de 2 que pueden ser más o menos altas.

En fin, que es más fácil de factorizar, es

[texx]2^ 3* 3*5* 2971[/texx]

Ese primo largo que aparece, 2971, tiene dos cifras menos que el semiprimo. En el caso de un número grande, a veces, también se pueden factorizar los pares que flanquean a los semirpimos; a veces sólo. Se puede usar la factorización basada en curvas elípticas y suele salir (yo uso Pyecm, creo que te lo dije, y factoriza muy bien y muy rápido números bastante grandes siempre y cuando tengan unos cuantos divisores).

Pero vamos a lo que iba diciendo.

Se trata de construir con esos divisores dos factores (no primos, claro) de igual tamaño; semejantes en tamaño a los primos componentes de   356519 (que tienen la longitud en cifras de la raíz, tres cifras). Claro que en este caso se factorizaría mejor y más rápido de cualquier otra manera, pero imagina que es muy grande y están muy alejados su factores de la raíz.

Como tenemos un primo de cuatro cifras, que es demasiado grande respecto de la longitud, hacemos lo mismo, buscamos un par de al lado: 2970, que se factoriza así


[texx]2*3^3*5*11[/texx]

y con los factores que teníamos acompañando a 2971, tenemos en total

[texx]2^ 4* 3^4*5^2* 11=356400 [/texx]

Siendo el semiprimo que queremos factorizar 356519 (se parece, como ves)

Y ahora, pues eso, se trata de combinar productos de esos primos de la descomposición [texx]2^ 4* 3^4*5^2* 11[/texx] y buscar los distintos factores de tres cifras que podamos obtener al combinarlos.


Tenemos muchas formas de combinar esos números, porque podemos tomar un solo dos, o dos doses y dos treses...  (aunque los haya escrito agrupados en una potencia, se pueden separar).

 Y, si se pretende hacer esto, hay que organizarse muy bien para hacer un programa que combine todo lo combinable.

En este caso, el producto [texx]2*2*3*5*11=660[/texx], por ejemplo, es un número bastante cercano a uno de sus factores; está sólo a una unidad de distancia del factor 659 (que es uno de ellos).

Es cierto que estamos hablando de un semiprimo muy pequeño, la diferencia en los grandes no será de una unidad o cosa así, pero a lo mejor, para alguno de ésos combinados, con suerte, puede ser de 100000 ó  1000000 y buscando “al lado” encontraríamos seguida el divisor.

Esto se me ocurrió hace días, no tiene que ver tanto con lo de ir estimando las cifras, pero me he acordado ahora y te lo cuento. Es necesario, ya te digo, tener paciencia para programar una rutina que vaya obteniendo todas las combinaciones; que pueden ser muchas, pero también se descartan muchas por pequeñas o demasiado grandes, muchísimas.

Esto creo que tiene sentido, ¿no? Parece un método de acercamiento que puede ser bastante seguro (no sé cómo de eficiente, pero sí que nos dejará a no muchas “paradas del autobús” en comparación con las cribas más básicas; vamos, eso es lo que estimo, a lo mejor no siempre).

No hace falte que te enteres mucho de esto (tú sigue con tu método estructural) pero si pudieras factorizar uno de los pares de al lado... nos vendría bien; ya me encargo yo de buscar la combinación del producto “ganador”, a ver si doy con ella; o tú mismo, si lo has entendido, no tengo ningún problema en eso, me gustaría incluso más que lo factorizaras tú antes que yo.

Cita
Lo que continúa en mi llamado proyecto personal, es conseguir la la colaboración de uno o mas matemáticos en el campo de Teoría de Números, para hacer la demostración matemática del enfoque estructural y con esto, demotrar y validar las metodologías de primalidad que les dije se dan y/o tenemos, y por supuesto, que eliminar el mito de la complejidad de factorizar compuestos semiprimos algo grandes como son los dados por los señores de RSA.... (No habrá por ahí... una beca de investigación sobre y para esto... ?)

Sinceramente, yo no puedo ayudarte mucho; entre otras cosas porque no pincho ni corto en el mundo de las matemáticas (ni en ningún otro mundo tampoco).

En mi caso, cuando tengo una idea, un método o lo que sea, lo cuento abiertamente, como te acabo de contar esto. Un día, “inventé” cómo hallar las potencias de los primos de un factorial (que me dijo Juan Pablo que ya estaba inventado, te acordarás). Hace dos días o así nada más, “invente” un algoritmo para hallar la raíz cuadrada (que me dijo el_manco que era el algoritmo babilónico, que ya existía, vamos). Otro día “inventé” el método de inclusión-exclusión para hallar la cantidad de primos...

Y lo que hago es detallarlo lo mejor que sé, eso que he encontrado, y ponerlo por aquí para que me digan si se puede demostrar, si alguien lo conoce o lo que sea; pero hay que detallarlo muy bien e ir al grano de cómo es el método; y ser muy concreto, todo lo que uno pueda o sepa.

Un cordial saludo.   
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #36 : 18/03/2017, 09:40:52 am »

Buenos Días Feriva...



Cita
Claro, porque las demás cifras son pares o el 5. Pero la primera cifra por la derecha es la menos significativa de todas, la de menos valor; en cambio, si conozco la primera por el otro lado y le pongo todo ceros detrás (tantos como cifras tiene la raíz menos una cifra) ya tengo un número muy grande, cercano a los divisores; o no tan cercanos, pero, desde luego, sí muchísimo más que un número de un dígito, no hay color.

• Mira que la raiz del RSA-230 tiene 115 digitos, donde digamos a ojo de predictor el divisor tiene 111 digitos y este comienza con 71 teniendo por lo tanto que rellenar 108 digitos con ceros, lo cual es muy complejo determinar al divisor, aún sabiendo estos datos.


Cita
Esto creo que tiene sentido, ¿no? Parece un método de acercamiento que puede ser bastante seguro (no sé cómo de eficiente, pero sí que nos dejará a no muchas “paradas del autobús” en comparación con las cribas más básicas; vamos, eso es lo que estimo, a lo mejor no siempre).

No hace falte que te enteres mucho de esto (tú sigue con tu método estructural) pero si pudieras factorizar uno de los pares de al lado... nos vendría bien; ya me encargo yo de buscar la combinación del producto “ganador”, a ver si doy con ella; o tú mismo, si lo has entendido, no tengo ningún problema en eso, me gustaría incluso más que lo factorizaras tú antes que yo.

• No comprendo bien esto... ¿Tú quieres la factorización de un compuesto semiprimo de 230 digitos, con casi igual, digamos el 90%, de digitos de la izquierda que tiene el RSA-230 ?
→ Esto llevaría un tiempito; pero se puede hacer esto, si es así como lo quieres... Lo que no comprendo, ni lo he analizado, es si los divisores se aproximarán en el 90% de digitos izquierdos, por lo menos, ó cuál sería el porcentaje de aproximación que se necesita? .... Me refiero, a los digitos izquierdos del compuesto RSA-230?

• Como ya te dije, hay una distancia de 115 digitos, donde todos los compuestos en este rango, estando el RSA-230 algo en medio, tienen la misma raiz cuadrada de este compuesto.
→ Si se busca factorizar ó determinar un compuesto semiprimo con 227 digitos izquierdos iguales al RSA-230, solo tenemos una pequeña cantidad de cantidatos que se dan según las lineas de generación que se den en 1000 y con 224 digitos izquierdos iguales, tenemos los [texx]nb[/texx] que se den en lineas de generacion de 1000000, donde no te indico una cantidad, pues esto depende si se emplea el Conjunto FV, el Conjunto V ó la Organización, de todos modos, la cantidad se incrementa, por decirlo así, casi exponencialmente, por cada digito que se tome del RSA-230.




Cita
Sinceramente, yo no puedo ayudarte mucho; entre otras cosas porque no pincho ni corto en el mundo de las matemáticas (ni en ningún otro mundo tampoco).

En mi caso, cuando tengo una idea, un método o lo que sea, lo cuento abiertamente, como te acabo de contar esto. Un día, “inventé” cómo hallar las potencias de los primos de un factorial (que me dijo Juan Pablo que ya estaba inventado, te acordarás). Hace dos días o así nada más, “invente” un algoritmo para hallar la raíz cuadrada (que me dijo el_manco que era el algoritmo babilónico, que ya existía, vamos). Otro día “inventé” el método de inclusión-exclusión para hallar la cantidad de primos...

• Gracias, pero solo era una idea que se me pasó por la mente, ya que en TVE vi cómo la vicepresidenta de España, daba el presupuesto para investigación y tecnología, algo que en mi país, no se sabe de esto y si hay, será a medio escondidas, para quién sabe qué intereses.
→ Ayer tuve una buena noticia... Mi compañero de colegio que es informático, a quién le conté sobre mi proyecto, me dijo que había un informático muy bueno, que estaba a cargo de la informática de la Corte de Justicia y que le había hablado de mí, estando de acuerdo en que le explicara mi proyecto.

• Sé que para validar mi criterio y/o Enfoque Estructural, debo hacer una demostración matemática con un matemático; pero mientras, ya tengo dos metodologías deterministas para primos de Mersenne, ya habiendo determinado poco mas de la mitad de los primos encontrados, esto con mis escasos conocimientos en programación.
→ El objetivo es que el informático, me ayude a acelerar el proceso, simplificando y/o reduciendo la complejidad de modalidad de calculo, puesto que solo se necesita hacer una sola valoración estructural, para decir con 100% de exactitud si un número de Mersenne es primo y con esto, completar la evaluación de todos ó casi todos los primos encontrados,... por lo menos llegar hasta el Mp[48] pero en poco tiempo, es decir, en unos cuantos días y qué mejor en unas cuantas horas.

• GIMPS pretende llegar al número primo de 100 millones de digitos, donde ya vi que dar con uno de estos, es complejo, por las distancias que se dan entre primos, siendo lo mas práctico, determinar primos de Mersenne.
→ Para esto tenemos que seleccionar candidatos, lo cual lo hacemos con la factorización para estos, como ya te expliqué, algo que estimo GIMPS emplea, para hacernos creer que tiene una super-metodología de factorización, lo cual también se puede simplificar el proceso.

• La evaluación de primalidad "PEM" solo se la realizaría en los candidatos seleccionados, es decir, los no factorizados y para esto, preciso tener a punto, la metodología de primalidad PEM (Primalidad Estructural para Mersenne)
→ Ya comprobé, empleando Mathematica 5.0 que mi primalidad para Mersenne, es mucho mas rápida que la primalidad de Wolfram, donde comparando con el Test de Lucas Lehemer, este es muy compleja, al trabajar con valores secuenciales, super-astronómicos, ante lo cual, se dice que GIMPS lo habría simplificado... Y yo me pregunto, que si lo simplificó... ¿por qué emplea miles de ordenadores para hacer sus evaluaciones? Y es que las constantes secuenciales de Lucas Lehemer, se pueden simplificar, hasta cierto punto y esto ya lo hice en un anterior desarrollo, que está en mi basurero de programas, lo que me permitió compararme con Lucas Lehemer.





◘ En estos días Feriva... He estado realizando mis analisis, a medias, picoteo por aqui y allá, según las ideas que me llegaban, que como de costumbre, parecen ser, que no me llevan a nada concreto y cualquiera que esté a mi lado, puede decir, que estoy perdiendo el tiempo; pero por experiencia, ya sé que no es así, ya que todo tiene su propósito constructivo.
→ Continuando.... Ya terminé de evaluar, un algo superficialmente, la factorización de nuestro RSA-230 con las proporciones que nos dá la raiz cuadrada, no llegando a resultados satisfactorios y es que esas metodologías, podemos decir que son, probabilísticas en su factorización, al no cubrir el 100% del recorrido estructural, lo cual hacerlo así, nos llevaría, la eternidad de universos creados.

• Al ver esto, opté por determinar la "proporción ciclica" que nos lleva exactamente al "punto de factorización" que es el ciclo-estructural de los naturales compuestos semiprimos, donde la metodología que había empleado anteriormente, era muy compleja; pero era logico para mí el hacer esto, no comprendiendo el por qué de su complejidad.
→ La razón de esa complejidad, era por la redundancia de evaluación que hacía, ya que estimando un posible "PF" punto de factorización, buscando desde este una proporción-ciclica, al particionar en una mayor cantidad y no dar con la valoración-ciclica esperada, ajustamos el PF y al particionar esta, estamos evaluando los mismos rangos-estructurales del anterior, lo cual ya lo esquematicé, con el compuesto 356519 de tu ejemplo.

• No hice esto antes, ya que según las ideas que me llegaban, lo fui aplicando directo sobre compuestos semiprimos de 21 digitos, algo que se dió, por decirlo así, sin complejidad, para cualquier proporción "Kp" y de las fracciones decimales que se quiera tomar, lo que también comprendí, que hay un limite para esto, dándose un maximo de 5 fracciones decimales en "Kp" para hacerlo complejo la factorización de este tamaño de compuestos semiprimos.
→ Con la nueva metodología empírica y perceptiva, pase a factorizar compuestos de 24 y 26 digitos, hasta Kp=50% algo que no podía hacerlo con mi anterior metodología, llegando hasta compuetos semiprimos de 32 y 35 digitos; pero esta vez, hasta proporciones "Kp" de 98% notando la complejidad que se daba y todo esto, sin realizar mis analisis de comprensión, lo cual recién lo haré, iniciando con tu compuesto de ejemplo.

• No es que me haya costado mucho esto... sino que el Lunes, al cerrar la tienda de mi hermana Carmen, me dí un golpe en la base de mi esternón, cerca a la boca del estómago, lo que me dejó en cama, por dos días seguidos, donde luego, me dí, para hacer unos ajustes y hacer una evaluación de factorización con esta metodología, en el RSA-230, estando Python en Kp=81,823491...% realizando en cada proporción Kp la evaluación de un intervalo y/o rango de 100.000 naturales, para lo cual fraccioné la zona de factorización y un poco mas, en 100.000.000 partes, que no es contínuo y/o secuencial, según creo, por haber trabajado empíricamente; pero es un poco mas determinista que las anteriores evaluaciones y puede que con mucha, mucha suerte, nos dé la factorización de nuestro RSA-230.
→ Mientras, realizaré el analisis de esto, donde ya con tu semiprimo de ejemplo, hice en Excel, una tabla, para ver como se van cubriendo los rangos-estructurales que no sean redundantes ó repetidos, con lo cual, modificaré el proceso de evaluación y luego de hacer mis comprobaciones, aplicarlo para factorizar el RSA-230, con mayor amplitud y eficiencia.

• Lo interesante de esto, es que no buscamos determinar el punto de factorización, sino que determinamos una proporción-ciclica que como te dije, nos lleva al punto de factorización mismo del compuesto semiprimo, lo cual ya lo he comprobado, factorizando compuestos de 26, 28, 32 y 35 digitos y no tenemos falla alguna, si es que determinamos la proporción ciclica, ante lo cual, el cometido es, simplificar el proceso y para esto, comprender como actúan los ajustes que empíricamente fui realizando.
→ Todo lo que hago, al ir explorando, encontrando y comprendiendo, es totalmente distinto al enfoque de tu metodología.... pero con la explicación de tu criterio metodológico, comprendo que quieres un compuesto, tan cercano e igual en digitos que tiene el RSA-230, el cual sea semiprimo, teniendo por lo tanto, su factorización con dos naturales primos... es así verdad?  Si es así, me lo confirmas, pues ya realicé esto mismo... donde para muchas proporciones "Kp" se dan compuestos semiprimos muy, muy similares en digitos izquierdos al del RSA-230 donde todos tienen la misma raiz cuadrada, lo cual solo me sirvió para aplicar mi anterior metodología de ajustes con la raiz cuadrada, para cada proporción "Kp".


Spoiler (click para mostrar u ocultar)

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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #37 : 18/03/2017, 06:09:04 pm »

Buenas noches, Víctor Luis.

Cita
pero con la explicación de tu criterio metodológico, comprendo que quieres un compuesto, tan cercano e igual en digitos que tiene el RSA-230

Sí, pero no tiene que ser semiprimo; al contrario, tiene que tener muchos factorcitos con los que componer dos factores (o todas las parejas de factores posibles) de 115 cifras que den ese mismo número.

No obstante, esto desestímalo, porque sería muy complicado.

De hecho conseguí (bueno, consiguió el Pyecm) factorizar enteramente uno que está muy cerca, sólo a 13 unidades por debajo:

Spoiler (click para mostrar u ocultar)

Pero el último primo es gigante, y eso es malo, porque no puedo formar dos factores de la misma longitud con productos de esos primos; tengo que restar otra vez una unidad al primo y volver a factorizar hasta tener unos primos lisos y homogéneos.

Yo también he estado mirando bastantes cosas.

Anduve viendo este PDF donde vienen los métodos más habituales de factorización.

http://biblioteca.unirioja.es/tfe_e/TFE000668.pdf

Me quedé en el método de Pollard y lo programé a partir de la explicación; funciona bien para números cuyos factores sean pequeños; y mi método del mcd y los intervalos (0,n) y (n, 2n), que es parecido (y que te expliqué por ahí) funciona casi mejor o sin el casi; pero imagino que el de Pollard, bien programado, o sea, con optimizaciones y eso, funcionará mejor. No obstante, no dejé de incluir la historia esa de la libre y la tortuga, para que fuera lo mejor posible; pero aún así no llega para números con primos “largos”; de hecho ya lo dicen por ahí, en Wikipedia en el PDF, no recuerdo.

Luego, descubrí una calculadora para factorizar programada en Java y que se usa en línea (también se puede descargar). Lo bueno que tiene que es que eliges el método, el tipo de criba (curvas elípticas o criba cuadrática) y escoges la cantidad de cifras que tienen los primos del semiprimo para que no pierda tiempo; está muy bien:

https://www.alpertron.com.ar/ECMC.HTM

Estuve probando con el RSA un rato; sin éxito, como era de esperar.

Hoy también he programado una cosa que me da una idea de cercanía de los primos del semiprimo; es algo parecido al algoritmo de Euclides, pero enfocado a intentar ver eso. EL problema es el de siempre, si conozco los semiprimos y voy mirando, veo en qué punto el algoritmo se acerca a los primos; y parece haber unos indicios, pero éstos, estas “señales”, no se cumplen igual siempre; y es lógico, porque el algoritmo va a piñón fijo, funciona con unos restos que pasan a ser divisores (apareados mediante una fórmula... no gran cosa) pero esto es muy “rígido” y no llega nunca al divisor, pasando al “lado”; sí que es cíclico, pero tampoco con claridad, depende del semiprimo.

En fin, tengo que seguir mirando cosas, a ver...

Cita
 Mira que la raiz del RSA-230 tiene 115 digitos, donde digamos a ojo de predictor el divisor tiene 111 digitos...

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

:sonrisa:

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 870


Ver Perfil
« Respuesta #38 : 18/03/2017, 11:05:02 pm »

Buenos Días Feriva...
( FELIZ DIA del PADRE !!! Aquí en Bolivia..)


Cita
"De hecho conseguí (bueno, consiguió el Pyecm) factorizar enteramente uno que está muy cerca, sólo a 13 unidades por debajo.."

• No has considerado, algo que supongo, es importante en esto y es que el compuesto semiprimo RSA-230 pertenece al grupo PIG[13] dándose por lo tanto sus dos divisores primos "p" y "q" que pertenecerán al mismo grupo PIG.
→ De todas formas, he comprobado con Mathematica 5.0 ya que Python sigue evaluando, que tu divisor:

Código:
291285296201342924926179723532087233968009212934434708912302396823953054073888573388320834518411481396256984945687571179009499774399806328936587922664810718866714941826353660842057501220491995758139713181

Es primo y divide exactamente al compuesto:

Código:
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852676

◘ Ahora, si tu predicción es que este divisor, es lo mas cercano al divisor del RSA-230,... Luego que Python haya llegado a Kp=50,00% lo detendré y voy a evaluar la factorización del RSA-230 con este divisor, en ambos sentidos de evaluación, es decir, en sentido ascendente y descendente, donde como estamos a 13 cifras del RSA-230, su factorización, debería darse, casi de inmediato, al menos eso creo.
→ Si es así... Amigo... habrás logrado factorizar nuestro tan escurridizo RSA-230... Por ahora, con tú me des un probable divisor, su evaluación es simple, claro, si es que está un tanto cerca del divisor mismo, ya que estructuralmente, la evaluación avanza a pasos muy grandes, en comparación a lo que haría Fermat ó el enfoque divisibilístico.

◘ Dame unas horas para Python y luego te digo el resultado que se dá...




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

Karma: +1/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 6.178



Ver Perfil
« Respuesta #39 : 19/03/2017, 08:22:41 am »


Hola, Víctor Luis, buenos días.

Cita
No has considerado, algo que supongo, es importante en esto y es que el compuesto semiprimo RSA-230 pertenece al grupo PIG[13] dándose por lo tanto sus dos divisores primos "p" y "q" que pertenecerán al mismo grupo PIG.

No, en realidad no importa eso porque ese número no tiene que ver en sí con los primos ni con el RSA; simplemente es un apoyo para construir un número compuesto (y compuesto de muchos primos) cercano a alguno de los divisores.


Si tú descompones 36, que está al lado del semiprimo 35, te da los factores: 2*2*3*3, que puedes agrupar así:

[texx](2*3)*(2*3)=6*6[/texx] (en este caso salen iguales, pero bueno, en otros no)

Y 6, es muy cercano a los factores 5 y 7  (en otro caso será cercano sólo a uno de ellos, claro).

Es decir, es lo que te dije, sería componer dos números del mismo “largo” (la longitud en cifras de la raíz) poniendo la esperanza en que el RSA tenga dos factores del mismo número de cifras.

Normalmente, podremos componer muchos factores de las mismas cifras si el semiprimo es grande  (no sólo dos) combinando; y alguno de ellos estará muy cerca de uno de los primos, como 6 lo está de 5, por ejemplo; es algo lógico, tú mismo puedes probar buscando pares que estén al lado de un semiprimo pequeño.

Alguno de esos compuestos estaría cerca de uno de los factores y entonces, con tu método o con cualquiera, se podría dar con él fácilmente (en principio, depende de lo grande que sea el semiprimo de la puntería a que hayamos tenido al formar los dos factores).

 Pero cuando los factores no son pequeños y aparece un número mayor que la propia raíz, mucho mayor, no sirve porque no se pueden formar dos factores de la misma longitud. Esta idea la tuve ya en verano cuando empecé a intentar factorizar el RSA, sin saber que a los números, hechos por primos menores que los del “n” que se intenta factorizar, se les llama números lisos, técnicamente, y se usan en varias de las cribas habituales (otra cosa que “inventé” que ya estaba inventada; pero mi visión, con esto de tomar los número de al lado y descomponerlos, quizá sea un poco diferente).

Ayer, y hoy hace sólo un rato, andando por el campo tomé dos palos de distinta longitud y pensé con ellos, montándolos, quitándoles trozos... Hoy he casi visto lo que quería ver: creo que existe un algoritmo semejante al de Euclides pero en  dos variables, por así decirlo (y añadiendo alguna idea más) que sirve para llegar, rutinariamente, a los divisores del semiprimo. De hecho, lo he probado con algunos números pequeños y funciona; pero lo que he visto con los palos, curiosamente, no termino de “aprehenderlo”, y entonces no puedo estar seguro de ha funcionado en esas pruebas por casualidad y no es como creo. Y, aunque funcionara, quiero entenderlo.

Me he hecho el firme propósito de no probarlo con un programa antes de comprenderlo completamente bien, razonadamente, y no como hasta ahora he procedido con otras intuiciones; estoy harto de que luego fallen las cosas. Pero la idea es esquiva, se escapa, no es fácil lo que quiero llegar a vislumbrar; y encima como estoy atontado... pues me cuesta un montón.

Si fuera como digo... sería muy “fuerte”, como dicen ahora.

Para explicarlo un poco, lo que tengo que llegar a ver, con los ojos de la razón absoluta y sin que queden ángulos muertos, es por qué ese algoritmo, siempre que se haga con un número no primo, llega a encontrar un mcd distinto de 1 para los restos x e y (aunque esto de restos... sí, son restos, pero entrelazados de una manera; se hacen dos tablas y llega un momento que un resto se repite, y los “restos” de la otra columna, entonces...  )

Entonces me callo hasta que lo entienda, lo programe y lo pruebe (si encima llega a ser eficiente... pues ya sería demasiado; pero me vale con que no esté equivocado y esta vez, por fin, sí que vaya construyendo los divisores).

Un cordial saludo.
En línea

Páginas: 1 [2] 3   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!