TARDÍGRADOS

Ciencia en español -ʟᴀ ʀᴀᴢóɴ ᴇsᴛá ᴀʜí ғᴜᴇʀᴀ-

Posts Tagged ‘factorización’

Números casi enteros

Posted by Albert Zotkin en febrero 13, 2018

Hola amigo. Ayer se me ocurrió jugar un poco con los llamados números casi-enteros. Como su propio nombre indica, son números reales que son casi enteros, es decir, que a su parte decimal le sobra o le falta muy poco para ser cero. Por ejemplo el número de Ramanujan:

\displaystyle  e^{\pi {\sqrt {163}}}=262\,537\,412\,640\,768\,743.999\,999\,999\,999\,25\ldots  (1)
Es un casi-entero porque le falta muy poquito para ser 262537412640768744. El problema con esta clase de números reside en su definición, la cual no parece muy matemática. Decir que algo es casi blanco o casi negro, es decir poco, cuando la definición la basamos en el adverbio “casi”. ¿Hasta qué punto un número es casi-entero?. Si el corte lo pusiéramos en que la parte decimal debe empezar por más de veinte 9’s seguidos o por más de veinte 0’s, entonces el número de Ramanujan no sería un casi-entero. Por eso, para resolver ese problema, se me ocurre la siguiente definición: Definamos la sucesión de números casi-enteros Qk, de orden k, de la función F(n) de dominio natural, así:

\displaystyle   Q_k(F(n))=\{ q_n \}_{n\text{,}\,k\in N} (2)
sería una sucesión de números reales, para los que su parte decimal tendría una precisión de k 9’s seguidos, ó de k 0’s seguidos, si expresamos la sucesión en notación de base decimal. Por ejemplo, el número de Ramanujan no estaría en ninguna sucesión de casi-enteros de orden k = 13, ó superior, ya que posee sólo doce 9’s seguidos en sus primeras posiciones decimales. En cambio, sí estaría en una sucesión de orden k = 10, o de grados inferiores. Pongamos un ejemplo: Sea la función de dominio natural siguiente:

\displaystyle   F(n)= e^{\pi {\sqrt {n}}} (3)

y calculemos su sucesión de casi-enteros de grado k = 10:

\displaystyle   Q_{10}( e^{\pi {\sqrt {n}}})= \{q_{58},\,q_{163},\,q_{1467},\,\ldots\} (4)
No sé si esa sucesión es finita o infinita, pero lo que si es fácil de comprobar es que 1467 = 9 × 163, y que esos tres primeros números casi-enteros son exactamente estos:

\displaystyle   q_{58}=e^{\pi \sqrt{58} }= 24591257751.99999982221324\ldots\\ \\   q_{163}=e^{\pi \sqrt{163} }= 262537412640768743.9999999999992500725\dots\\ \\  q_{1467}=e^{\pi \sqrt{1467} }=18095625621654510801615355531263454706630064771074975.9999999901236\ldots
Propongo que el número casi-entero q1467 = 18095625621654510801615355531263454706630064771074975.9999999901…, sea llamado número de Alberti, porque 1467 fue el año en que el criptógrafo León Battista Alberti escribió el tratado De Componendis Cifris, donde describe un disco para encriptar alfabeto, que ahora llamamos disco de Alberti.

Si el grado k de la sucesión Q de casi-enteros lo hubieramos rebajado a k = 6, esa sucesión sería esta:

\displaystyle   Q_{6}( e^{\pi {\sqrt {n}}})=  q_{37},q_{58},\, q_{67},q_{163},\, q_{232},\, q_{719},\, q_{1467},\, q_{4075},\ldots (5)
Todo esto nos debe hacer reflexionar sobre el hecho de que, antes de ponerse a divagar sobre un asunto, es muy importante acotar con una buena definición de qué estamos hablando, y eso es especialmente importante en matemáticas.

Y para terminar de jugar con el tema de los números casi-enteros, definiré ahora otra clase de números, que llamaré casi-enteros Cunningham. Los números casi-enteros Cunningham de base b van a ser números de la forma:

\displaystyle  \frac{\log(b^{n}\pm 1)}{\log(b)}= \log_b(b^{n}\pm 1) (6)
Donde, obviamente b^{n}\pm 1 es un número de Cunningham. Por ejemplo, la sucesión de casi-enteros Mersenne, son números casi-enteros Cunningham de base 2 de la forma:

\displaystyle  \frac{\log(2^{n} - 1)}{\log(2)} = \log_2(2^{n} - 1) (7)
Que es una forma de mapear los exponentes de esos números Mersenne. Por ejemplo, el número primo Mersenne M31 = 2305843009213693951, que fue descubierto por Euler en 1772, genera el casi-entero:

\displaystyle   Q_{31}=\log_2(2^{31} - 1) =30.99999999932819276991073646469478216 \ldots (8)
que, como vemos, se aproxima mucho al exponente 31. Y alguien se preguntará “ok, muy bien, y ¿qué utilidad tiene todo esto?“. La respuesta es fácil, “ninguna, en principio” 🙂 . Pero, si de lo que se trata es de hallar número primos Mersenne, los casi-enteros Cunningham, que he definido arriba, pueden tener mucho que decir, sobre todo si analizamos su partes fraccionales.

Podemos expresar elegantemente la parte fraccional, {Qp}, de un número casi-entero Mersenne Qp así:

\displaystyle  \{Q_p\}=\int_1^p \frac{dx}{2^x-1} (9)

porque es fácil ver que, efectivamente:

\displaystyle  \{Q_p\}=\int_1^p \frac{dx}{2^x-1} = \log_2(2^p - 1) -p+1 (10)

Saludos

Anuncios

Posted in Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , , , , , , , , | Leave a Comment »

Infinitas formas de dividir un número primo

Posted by Albert Zotkin en enero 25, 2018

    Uno de los hechos más asombrosos de dividir un número entero por otro, es que a veces ocurre que ciertos números sólo son divisibles por sí mismos y por la unidad, y los llamamos números primos. Pero, nadie sabe cómo esos números primos se van distribuyendo a lo largo de la sucesión de los números naturales. Ese hecho nos deja perplejos, porque no somos capaces de encontrar ninguna fórmula eficaz ni algoritmo para generar el siguiente número primo. ¿Por que ocurre eso?. Eso ocurre porque nuestra aritmética estándar es sólo una entre infinitas aritméticas posibles. En este pequeño artículo voy a definir algunas de esas aritméticas, que se me han ocurrido, pero siempre teniendo en mente que pueden haber infinitas más, desde otros criterios y perspectivas. Cada aritmética genera su sucesión única de números primos. Empecemos pues:

    Todos sabemos, o deberíamos de saber, que cuando dividimos un número natural por otro, lo podemos interpretar como un método para saber cuántos grupos de cosas se pueden formar, tal que todos los grupos posean el mismo número de ellas. Esa aritmética es básicamente una cuadrícula. Cada columna ( o cada fila) de la cuadrícula es pues un grupo de cosas, y todas tienen el mismo número. Puede ocurrir que la ultima fila o la ultima columna no tenga completas ( llenas) todas sus celdas, eso nos indica que hay un resto distinto a cero en la operación de division. Ahora borremos de nuestra mente esa cuadrícula y exploremos otras posibles formas de dividir un número por otro. Supongamos que, al dividir un número p de manzanas por otro q, lo que queremos es formar q grupos de manzanas y que cada uno contenga un número distinto. En concreto, lo que queremos es que exista una diferencia de una manzana entre los sucesivos grupos, desde el más numeroso al menos.

    Al aplicar ese criterio de división, aunque sería más apropiado hablar de distribución, entramos en el territorio de los números triangulares. Supongamos que tenemos 10 manzanas y queremos saber cuántos grupos podemos formar tal que exista esa diferencia de una unidad entre ellos al considerarlos sucesivamente. Rápidamente vemos que sólo se pueden formar 4 grupos:

    Con los números triangulares podemos definir operaciones de división y multiplicación que escapan ya de la estándar cuadriculada. Con los números triangulares, los distintos grupos que se pueden formar, con la operación de división, difieren en una unidad. En el caso del ejemplo, diremos que 10 manzanas son divisibles por 4, y el grupo más numeroso tiene precisamente 4 manzanas, y el menos numerosos tiene 1. En general, para los números triangulares tendremos que, cualquier número entero positivo p es divisible por otro q, si la siguiente igualdad se cumple:

    \displaystyle p =\frac{q(q+1)}{2}
    Y si obviamos la fórmula podemos indicar la división 10/4 de esta forma:

    \displaystyle  \frac{10}{4} = 4 ,\;\; \text{diff 1}
    que se leerá así: “10 divido por 4 igual a 4, diferencia 1“. El cociente de dividir 10 por 4 es también 4, es decir coincide con el divisor. La sucesión de los números triangulares es la siguiente,

    \displaystyle T_n=\{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136,\dots\} \\ \\  T_n=\{1, 1+2, 1+2+3, 1+2+3+4,1+2+3+4+5,\dots\} \\ \\  T_{n}=\sum _{k=1}^{n}k=1+2+3+\dotsb +n={\frac {n(n+1)}{2}}={n+1 \choose 2},
    Si Tn es el n-ésimo número triangular, entonces podemos decir que es divisible por n diff 1, y el cociente coincide siempre con su divisor:

    \displaystyle \frac{T_n}{n} = n ,\;\; \text{diff 1} \\ \\  T_n = n \times n = \;\; \text{diff 1}
    Veamos ahora qué otros números naturales, que no sean triangulares, son divisibles diff 1. Observamos que el primer número no triangular divisible diff 1 es el 5:

    5 es divisible por 2 diff 1, porque obtenemos dos grupos, uno de 3 manzanas y otro con 2, es decir:

    \displaystyle \frac{5}{2} = 3,\;\; \text{diff 1} \\ \\
    significa que el cociente 3 es el numero de manzanas en el grupo más numeroso, y vemos que 5 no es triangular porque el menor grupo no es la unidad. En seguida nos damos cuenta que los número no triangulares que son divisibles diff 1, son en realidad, fragmentos verticales de números triangulares
    En este caso, el menor número triangular que contiene al 5 es el 6, y el siguiente que lo contiene es el 10:

    El primer número primo diff 1 es el 2, el siguiente será el 4, y el siguiente el 8. Parecería fácil afirmar que todos los número pares que no sean triangulares serían primos diff 1, pero no, no es tan fácil, ya que existen números pares que no son triangulares, pero son divisibles diff 1. Por ejemplo:

    \displaystyle \frac{12}{3} = 5,\;\; \text{diff 1} \\ \\  \frac{18}{4} = 6,\;\; \text{diff 1} \\ \\
    En esta clase de divisiones (o distribuciones) en modo diff 1, el divisor siempre es menor o igual al cociente, nunca mayor. ¿Cómo podemos saber si un número es divisible diff 1. El primer test que ha de pasar el número es comprobar si es triangular:

    \displaystyle n={\frac {{\sqrt {8x+1}}-1}{2}}
    si en la formula de arriba, el número x, que es entero positivo, da como resultado el número n, y además vemos que es también un entero positivo, entonces x es triangular, y por lo tanto es divisible diff 1 por n. El siguiente test es para los número no triangulares. Decía yo antes, que los número no triangulares que son divisibles diff 1, son fragmentos de números triangulares. Eso expresado matemáticamente quiere decir que son la diferencia entre dos dos números triangulares. Por ejemplo, el 12 y 18, que no son triangulares, son divisibles diff 1, por que 12 = 15 – 3, donde 15 y 3 son triangulares. De igual forma 18 = 21 – 3, donde 21 y 3 son triangulares. Por lo tanto el test de divisibilidad diff 1, para los no triangulares, será ver que existen unos números x e y que son triangulares, con:

    \displaystyle y-x=p \\ \\
    con y > x, donde y es el menor número triangular conteniendo al número p. Si p es divisible por q diff 1, entonces

    \displaystyle q={\frac {{\sqrt {8(x+p)+1}}-1}{2}}
    q es el número de grupos que se pueden formar con p. El número de elemento del primer grupo (el más numeroso) será

    \displaystyle \frac{p}{q} = c_1,\;\; \text{diff 1} \\ \\
    y el número de elementos del grupo menos numeroso será:

    \displaystyle c_q=c_1 - q +1
    ¿Existen números primos diff 1?. Veamos. Construyamos una tabla de diferencias para números triangulares hasta el T10 = 55. Al hacer esto sabremos que números son triangulares y que otros son diferencias entre ellos. Por lo tantos, los que no estén en esa tabla deberán ser números primos diff 1.

    Según esta tabla de diferencias, el primer número primo diff 1 es el 16, porque no aparece en ella. El segundo candidato a número primo Diff 1 es el 23. Y los siguientes serían 28, 29, 31, 32, 36, 37, 38, 41, 43, 46, 47, 48, 50, 51, 53. Es decir, tendríamos los primos diff 1 siguientes:

    \displaystyle \{16, 23, 28, 29, 31, 32, 36, 37, 38, 41, 43, 46, 47, 48, 50, 51, 53,\dots\}
    Las celdas de la tabla que he rellenado en color rojo, corresponden a diferencias entre núeros triangulares consecutivos, pero entonces no darían lugar a distribuir en 2 ó más grupos, por lo tanto esos números de la diagonal se desechan. ¿Por qué es el número 16 primo diff 1?. Intentemos formar dos grupos de objetos que sumen 16 pero exista una diferencia de una unidad entre ellos. No se puede porque 16 es número par. Si Formamos dos grupos de 8, y le quitamos 1 a uno de ellos y se lo sumamos al otro tendremos 2 de diferencia, pero estaos en modo diff 1. Por lo tanto, no se pueden formar 2 grupos porque 16 es par. Intentemos formar 3 grupos. Si el primer hrupos tiene 7 objetos, el segundo ha de tener 6, y el tercero 5, pero entonces 7 + 6 + 5 = 18 > 16, no suma 16. Probemos con 5 elementos para el primer grupo. tendremos 5 + 4 + 3 = 12 < 16, tampoco suma 16. Y para las restantes agrupaciones resultan números aún menores. Luego 16 es el primer número primo diff 1. ¿por qué es 23 un número candidato a ser primo diff 1?. En principio , vemos que no es número par, luego podemos formar dos grupos, uno con 11 elementos y el otro con 12. Pero, el número triangular que es divisible diff1 por 2, para dar 12 de cociente, es el 78, es decir, un número mayor al 55, que no lo tenemos tabulado. Por lo tanto, 23 no es primo diff 1, pero sus divisores diff1 dan cocientes mayores a 10, En resumen, 23 es divisible por 2 diff 1, y no tiene más divisores:

    \displaystyle  \frac{23}{2} = 12 ,\;\; \text{diff 1}
    Luego todos los números impares de la lista de candidatos a números primos diff 1, se nos caen de ella porque siempre es posible encontrar para cada uno de ellos un divisor para formar dos grupos de objetos. Luego, los números primos diff 1 han de ser todos pares. Los números impares son todos divisibles por 2 diff 1. Y nuestra lista de números primos diff 1 quedaría asi:

    \displaystyle \{16,  28, 32, 36, 38, 43, 46,  48, 50, \dots\}
    ¿Por qué es 50 un número primo diff 1?. El mínimo número triangular que lo contiene es el 55, que posee 10 grupos, con 10 elementos para el mas numeroso y 1 para el menos numeroso. Pero, no existe ningún número triangular para sustraer tal que dé 50. El que más se le aproxima es el triangular 6 que tiene 3 grupos, pero daría 55 – 6 = 49:

    Los números triangulares pertenecen a una clase de números llamados números poligonales, De esta forma podemos seguir nuestro método de división, y definir qué significa que un número sea divisible diff 2. Se trata de formar grupos que tengan dos unidades de diferencia entre consecutivos, Y así entramos directamente en el territorio de los números cuadrados. Estas divisiones también generan sus números primos, los llamados números primos diff 2. En general, los número poligonales son de la forma

    \displaystyle P(s,n) = \frac{n^2(s-2)-n(s-4)}{2}
    Donde s es el número de lados del polígono. Los números primos estándar, 2,3,5,7,11,…, pertenecen al criterio de divisibilidad diff 0, y teóricamente pertenecerian a la sucesión de números definidos por polígonos de 2 lados, pero eso geométricamente es imposible. Si aplicamos el valor s = 2, a la fórmula, tenemos:

    \displaystyle P(2,n) = \frac{n^2(2-2)-n(2-4)}{2} = \frac{2n}{2}=n
    que es la sucesión de los números naturales, como no podía ser de otra forma. Así, hemos visto, en este pequeño artículo, cómo es posible definir diferentes sucesiones de números primos según el criterio de divisibilidad que apliquemos. Todos los númros primos estándar 2,3,5,7,11,… son divisibles diff 1 excepto el 2, por que son impares. Se me olvidó decir que el número 2 es obviamente el primer número primo diff 1, porque aunque admite dos grupos, la diferencia de sus elementos no es la unidad, sino 0. Y como broche final, un pequeño ejercicio:

    Halla el número de divisores diff 1 del número primo Mersenne que descubrió Euler en 1772. Es decir, tenemos el número primo estándar, diff 0, siguiente:

    \displaystyle M_{31}= 2^{31}-1= 2147483647

    Saludos

Posted in Matemáticas | Etiquetado: , , , , , , , , , , , , , , | Leave a Comment »

Los primeros treinta árboles Mersenne

Posted by Albert Zotkin en enero 20, 2018

Hola, único lector de Tardígrados. Gracias por seguirme. Hoy voy a ir a mi jardín y plantar los primeros treinta árboles Mersenne. Ya sabes que un número Mersenne m es un número entero positivo que posee la forma m = 2n -1, donde n es otro entero positivo. Y ahora, siguiendo el método, ideado por mí, para construir árboles (grafos en forma de árbol) de números primos correspondientes a sus factorizaciones unarias, dibujaré los primeros treinta. Es decir, dibujaré árboles para los números {3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647}. Esta lista escrita desde los exponentes sería asi:

\displaystyle \{ 2^2-1,\;2^3-1,\;2^4-1,\;2^5-1,\;2^6-1,\;2^7-1,\;2^81,\;2^91,\;2^{10}-1,\; \\  2^{11}-1,\;2^{12}-1,\;2^{13}-1,\;2^{14}-1,\;2^{15}-1,\;2^{16}-1,\; \\ 2^{17}-1,\;2^{18}-1,\;2^{19}-1,\;2^{20}-1,\;2^{21}-1,\;2^{22}-1,\; \\ 2^{23}-1,\;2^{24}-1,\;2^{25}-1,\;2^{26}-1,\;2^{27}-1,\;2^{28}-1,\; \\ 2^{29}-1,\;2^{30}-1,\;2^{31}-1 \}
Para aquellos números de esta lista que no sean primos, al dibujar su árbol, sugeriré una continuación hacia la cúspide para culminar con el correspodiente número primo:

He coloreado en verde las extensiones de los árboles que completan los números Mersenne que no son primos, sugiriendo una continuación hacia un número primo, el cual a su vez no tiene por que ser necesariamente Mersenne.

Las etiquetas numéricas de los nodos se pueden obviar (omitir), si el árbol es completo, es decir, si están todos los nodos de la factorización unaria, hasta llegar a los nodos terminales de la unidad. Por ejemplo, el último árbol que he dibujado, que representa el número Mersenne 2147483647, el cual es un número primo, sin las etiquetas numéricas sería así:

Saludos

Posted in Matemáticas | Etiquetado: , , , , , , , , , , | Leave a Comment »

Cómo romper los códigos criptográficos RSA: factorizacion de semiprimos y las raices rectangulares

Posted by Albert Zotkin en noviembre 18, 2016

riemann-estela
En la actualidad, usamos algunas de las propiedades de los números primos para codificar mensajes, de modo que ningún intruso pueda leer fácilmente nuestras comunicaciones. Para ello usamos la propiedad siguiente de los número semiprimos: Elegimos dos números primos suficientemente grandes, y obtenemos el semiprimo multiplicándolos. El número semiprimo será parte de la llave pública para nuestro método de encriptación, y con los dos números primos se construyen las llaves privadas. Dado un semiprimo suficientemente grande, es prácticamente imposible hallar en tiempo razonablemente corto, sus dos factores primos. Eso es incluso casi intratable usando supercomputadores. esta dificultad se llama Problema RSA.
Si estás interesado en desencriptar los códigos que protegen el acceso a tarjetas de crédito bancarias o a páginas web seguras, quizás estés interesado en participar en esta clase de Competición de factorización RSA. Veamos un semiprimo catalogado por la RSA y que tiene un premio de 100.000 dólares para quien halle sus dos factores primos. Este semiprimo es el RSA1024, es decir, posee 1024 cifras binarias (309 cifras decimales):

\displaystyle \text{RSA}_{1024} = \\ 13506641086599522334960321627880596993888147560566702752448514385152651060 \\ 48595338339402871505719094417982072821644715513736804197039641917430464965 \\ 89274256239341020864383202110372958725762358509643110564073501508187510676 \\ 59462920556368552947521350085287941637732853390610975054433499981115005697 \\ 7236890927563
Si queremos factorizar con éxito un número semiprimo de la RSA, lo primero que debemos hacer es estimar lo grande que serán sus dos factores primos. Así, para ese RSA1024, los dos factores primos estarán muy cerca relativamente de su raíz cuadrada, es decir, números primos cercanos a las 154 cifras decimales, o lo que es lo mismo, números primos de entre 100 y 200 cifras decimales. Por ejemplo, si uno de los primos resulta tener 120 cifras decimales, el otro estaría muy próximo a las 188. Pero, veamos, ¿cuántos números primos hay que tengan entre 100 y 200 cifras decimables?. Usemos la función contador de números primos, p(x), aproximémosla a x/log(x), porque según Gauss, esa es una buena aproximación para un x suficientemente grande. Así los números primos que tienen entre 100 y 200 cifras decimales son aproximadamente :

\displaystyle 2.17 \times 10^{197}
Supongamos que disponemos del superordenador más potente del mundo, el reciente Sunway TaihuLight, capaz de operar a máximo rendimiento, que es de 125.43 petaFLOPS. Conseguiría resolver el número RSA1024 1 petaFlop es 1 opración de coma flotando por cada femtosegundo. 10¹5 femtosegundos son 1 segundo. En total tardaríamos un maximo de :

\displaystyle 2.17 \times 10^{197} \times 10^{-15} = 2.17 \times 10^{182} \; \text{segundos,}
un tiempo demasiado largo como para tener alguna esperanza de llegar en vida hasta el final del cálculo y verlo con nuestros propios ojos 😛

Veamos ahora qué es una raíz rectangular. Cuando calculamos una raíz cuadrada en realidad estamos calculando dos números, pero como ambos son iguales, no nos damos cuenta que en realidad es un par de números. Por ejemplo, la raices cuadradas de 64 son el par (8, 8):

\displaystyle \sqrt{64}=(8,8)
Podemos calcular para 64 su raices rectangulares, ya que si nos fijamos 64 puede escribirse como 2 elevado a diferentes exponentes, es decir:

\displaystyle 64 = 2^6 = 2^3 \times 2^3 =  2^2 \times 2^4 = 2^1 \times 2^5
Es decir, el número 64 posee dos pares de raíces rectangulares y un par de raíces cuadradas:

\displaystyle 64 = (8,8) = (4,16) = (2,32)
Así, para entendernos, pondremos el par de exponentes de las raices rectangulares entre corchetes, de modo que siempre tendremos la equivalencia:

\displaystyle 1 = \left[\frac{3}{6}, \frac{3}{6}\right] = \left[\frac{2}{6}, \frac{4}{6}\right] = \left[\frac{1}{6}, \frac{5}{6}\right]
Con esto, lo único que estamos haciendo es dividir la unidad en dos partes, de modo que su suma sea esa misma unidad. ¿Por qué el número 64 posee esas raices rectangulare y no otras?. En realidad posee muchas más, pero las que he escrito arriba son las que dan raices enteras. Veamos estos casos:

\displaystyle 64 = 64^{\tfrac{1}{4}}\times 64^{\tfrac{3}{4}}= (2\sqrt{2}) (16\sqrt{2}) \\  64 = 64^{\tfrac{1}{5}}\times 64^{\tfrac{4}{5}}= (2\sqrt[5]{2}) (16\sqrt[5]{2^4}) \\
en general, para cualquier par de número enteros m y n, que sean coprimos,tendremos las raices rectangulares de un número N:

\displaystyle N= N^{\tfrac{m}{n}}\times N^{1-\tfrac{m}{n}}
Veamos ahora cómo aplicamos esto a la factorizaación de números RSA: sean los números primos p = 486023 y q = 598727, por lo que su producto es N = 290995092721. Empezaremos nuestros cálculos con su raíz cuadrada:

\displaystyle \sqrt{N}=539439.60989252541168458987732327730802813682656081\ldots
Igualmente sabemos que ha de ser:

\displaystyle p= N^{\tfrac{m}{n}} \\  q= N^{1-\tfrac{m}{n}}

y puesto que sabemos los valores de p y q, es fácil resolver m y n:

\displaystyle \frac{m}{n}=\frac{\log p}{\log(pq)} \\ \\ \\  1-\frac{m}{n}=1-\frac{\log p}{\log(pq)}=\frac{\log q}{\log(N)}
Por otro lado, si pensamos un poquito, nos daremos cuenta de que factorizar un número RSA no es muy difícil en principio, la dificultad reside en que los números primos, p y q, que forman el semiprimo N, sean muy grandes. Así, es incluso posible presentar una ecuación matemática con la que podemos resolver cualquier número RSA, y es esta:

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor !)=\min (p,q) (1)
Aquí N es producto de los dos primos p y q, mcd es el máximo común divisor de dos números, \lfloor\ r\rfloor ! es el factorial de la parte entera del número real r. Podemos incluso optimizar un poco esa ecuación (1) si usamos el primorial en lugar del factorial,

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor \#)=\min (p,q) (2)
Si N ya es en principio un número muy grande (más de 1024 digitos binarios), el factorial (o el primorial) de la parte entera de su raíz cuadrada será incluso más grande aún, prácticamente intratable. De ahí que las fórmulas (1) y (2) aunque sean correctas, no son muy útiles para el cálculo. En realidad, para calcular un mcd de dos números primero hay que factorizar esos dos números. Es evidente que factorizar N es más fácil que factorizar el primorial de la parte entera de su raíz cuadrada.

Posted in informática, Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , , , , | Leave a Comment »

Los laberintos entéricos de los números grandes

Posted by Albert Zotkin en marzo 17, 2016

Todos sabemos, o deberíamos saber, que la factorización de un número entero es simplemente expresar dicho número mediante el producto de todos los números primos que sean sus divisores, y cada primo elevado a su correspondiente exponente si lo tuviere. Esa tarea de factorización no resulta fácil. Por ejemplo, usando supercomputadoras, es posible factorizar un entero de 200 dígitos decimales en aproximadamente 1 año y medio. Esa inmensa dificultad es la base de muchos algoritmos criptográficos, como el RSA. El mejor algoritmo para factorizar es la Criba General del Cuerpo de Números, pero no reduce la dificultad. Sólo mediante una computadora cuántica sería posible reducir drásticamente los tiempos de cálculos.

Hoy vamos a ver cómo cada uno de los números enteros puede ser por sí mismo un intrincado laberinto de pasillos por los que podríamos perdernos fácilmente si no conocemos las reglas con las que están hechos. Fijémonos en el plano de la siguiente galería de pasillos: corridor1

¿Qué representa?: pues representa a un número entero muy grande. Tal número posee nada menos que 3700544 dígitos en el sistema de numeración decimal, y lo podemos escribir mediante factores primos así:

\displaystyle 2^2 \times 5^{3^2 \times 5 \times 7^{2\times 3}} \times 11^{2\times 5^2}

Existe pues una secuencia principal de números primos que representamos como el pasillo principal de esa galería. Para este caso, esa secuencia principal es 2 ×5×11. Después, cada vez que uno de esos números primeros está elevado a un número entero, se genera una nueva secuencia de números primos, y eso se evidencia por la generación de un pasillo secundario, siempre en el lado derecho según el sentido creciente de la secuencia de primos de la que es exponente. Para mayor claridad, veamos el plano anterior con las secuencias de números primos principal y secundarias:

corridor2

Si aparecemos en el interior de un laberinto entérico de esta clase, y buscamos la salida (que también es la única entrada), lo primero que debemos hacer es avanzar hacia el final del pasillo dejando a la izquierda los pasillos secundarios que encontremos. Y cuando llegamos al final de ese pasillo debemos girar la izquierda para entrar en el pasillo que deberá ser uno inmediato inferior al que estábamos. Siempre procederemos avanzando según ese criterio, hasta llegar a la entrada del laberinto.

Consideremos ahora sólo una clase de números enteros, aquellos que son el producto de números primos sin repetición, es decir, que no posean exponentes. Por ejemplo.

\displaystyle 29\times 23\times 19\times 17\times 13\times 11 = 30808063

El laberinto entérico para esa clase de números es sencillo, ya que sólo existiría el pasillo principal. Es fácil, para esta clase de números expresarlos mediante codificación binaria. Veamos, si la secuencia principal está compactada totalmente con todos los números primos, la codificación binaria sería una sucesión infinita de 1’s. Así, el número del ejemplo anterior podrá ser codificado binariamente asi:

\displaystyle C(29\times 23\times 19\times 17\times 13\times 11) = 1111110000

Si al número anterior le substraemos, por ejemplo el divisor 17, tendremos como resultado este otro número

\displaystyle 29\times 23\times 19\times  13\times 11 = 1812239

y su codificación binaria sería:

\displaystyle C(29\times 23\times 19\times  13\times 11) = 1110110000

Es decir, los unos y los ceros de esa codificación binaria son los exponentes del producto de primos, en la secuencia principal:

\displaystyle 29^1\times 23^1\times 19^1\times 17^0 \times 13^1\times 11^1 \times 7^0  \times 5^0 \times 3^0 \times 2^0= 1812239

Así, hemos descubierto una función tal que a cada número entero del pasillo principal se le asigna un número binario que codifica a todos sus divisores primos.
Si estudiamos seriamente esta nueva función, que no podrás encontrar en ningún libro de matemáticas, ni en ninguna otra parte, porque es descubrimiento mio, llegamos a misteriosas relaciones que nos dan claves para acelerar los cálculos de los algoritmos de factorización. A esta función la llamaré Función Entérica Principal (FEP). Es decir, la FEP de 1812239 es 1110110000.

\displaystyle \text{FEP}(1812239)=1110110000

Igualmente, si pretendes ampliar el tema de los laberintos entéricos aquí propuestos, he de decir que no podrás encontrar mucho más porque es una invención mía, y por lo tanto lo mucho o lo poco que puedas encontrar es lo que yo haya escrito (o pueda escribir en el futuro) en este blog.

Saludos

Posted in Matemáticas | Etiquetado: , , , , , , | Leave a Comment »

 
A %d blogueros les gusta esto: