Primera generación

Como continuación del tema que comenzó en esta serie de artículos , hoy hablaremos sobre la generación de números primos. La generación es probabilística y está garantizada. Por lo tanto, nuestro caso es con una garantía que le permite utilizar los números obtenidos en aplicaciones relacionadas con la criptografía, lo que garantiza, por ejemplo, la seguridad de administrar su dinero a través de aplicaciones bancarias. Además, verá cómo se garantiza recibir números primos de tamaño suficiente para la criptografía, así como qué problemas pueden surgir si descuida las garantías.


El esquema general de seguridad para el intercambio de datos se basa en la complejidad de factorizar un gran número compuesto. Además, si hay muchos factores, entonces serán pequeños, y esto simplifica enormemente el pirateo del sistema de seguridad. Por lo tanto, se obtiene un número compuesto grande multiplicando dos números primos de cierto tamaño. Pero aquí hay un problema obvio: ¿cómo elegir un número primo suficientemente grande?

Primero, determina el tamaño. En la criptografía moderna, el orden del número compuesto está determinado por la fórmula $$$2 ^ {2048}$ , es decir, el orden real es 2048 en notación binaria. Y los divisores de este número compuesto son del orden de 1024, es decir, alrededor de los valores. $$$2 ^ {1024}$ . ¿Por qué 1024? Debido a que hace diez años se factorizó un factor del orden de 768, y hoy es muy probable que los números compuestos del orden de 1024 se descompongan. Por lo tanto, se decidió por confiabilidad duplicar el orden de una vez, es decir, hasta 2048. Bueno, comenzar desde este orden es fácil de determinar orden de los factores requeridos.

Pero, ¿qué sucede si el orden de los factores es mucho menor que 1024? Luego, en un tiempo aceptable, puede descomponer un número compuesto, incluso si es del orden de 2048. Esto significa que es necesario garantizar que los factores elegidos por nosotros tienen un orden cercano a 1024 y son simples, es decir, no pueden factorizarse. Pero aquí la elección en sí se lleva a cabo de acuerdo con un esquema probabilístico, y esto solo conduce a problemas potenciales.

La probabilidad de simplicidad de un número se verifica sobre la base de la suposición de que el número es "más probable" primo si su período (que se describe aquí ) es un divisor del número mismo, menos uno ( $$$N-1$ ) En forma de fórmula, se ve así:

$$

$$a ^ p \ pmod N = 1$$

$$

$$N-1 \ pmod p = 0$$

Aqui $$$N$ - número investigado, $$$a$ - valor de $$$2$ antes $$$N-2$ (determina la base del sistema numérico en el que se calcula el período), $$$p$ - período del número investigado. Operación $$$mod$ aquí significa tomar el resto de dividir el primer operando por el segundo.

Las comprobaciones existentes dependen de tal enfoque, ya que para grandes cantidades la determinación incondicional de simplicidad por pruebas conocidas lleva mucho tiempo. Pero la desventaja de tal verificación es obvia: a veces puede obtener un número compuesto, en lugar de uno simple. Además, nadie sabe qué divisores serán parte de tal número. Más precisamente, un atacante podrá descubrirlo aplicando los métodos de factorización bien conocidos, que comienzan a funcionar en un tiempo aceptable si los factores son del orden de menos de unos pocos cientos de bits.

¿Con qué frecuencia es un error de simplicidad probabilística? Raramente suficiente. Hay un error para varias decenas de miles de simples, y a veces dos, pero nada nos garantiza tres. Además, mucho depende de la prueba utilizada. Entonces, por ejemplo, en la biblioteca de lenguaje Java estándar en la clase BigInteger, se implementa una verificación que permite una falla 2-3 veces por mil simples. Es decir, no debes pensar que si teóricamente hay muy pocos errores, en la práctica todo estará en chocolate.

¿Cómo es esto peligroso? Parece que no es tan aterrador como algunos pueden decir, porque bueno, si un sitio que cierra la navegación de sus páginas con el protocolo https recibe una clave fácil de calcular, ¿cuál será el problema? Bueno, los piratas informáticos descubrirán qué noticias lees en este sitio y cuál es el punto. Pero, de hecho, el cifrado no solo se realiza al navegar por la web. Una situación más desagradable sucederá si los piratas informáticos descubren la clave de su servicio bancario favorito para administrar su dinero de forma remota. Aunque, de nuevo, parece que para poder abrir el intercambio con el banco (y si el banco usa un cheque de simplicidad débil), el pirata informático tendrá que esperar unos 500 años hasta que la probabilidad de emitir una clave fácilmente calculada finalmente, porque las claves generalmente tienen un período de validez de 1 año y por lo tanto, para garantizar la piratería, debe esperar hasta que se lleven a cabo 500 ediciones de una nueva clave. Parece que todo es lógico, pero hay otro "pero": hay muchos más bancos que 500 en el mundo. Por lo tanto, ahora mismo, tal vez en su banco favorito, los piratas informáticos pueden acceder a su propio dinero.

¿Tienes miedo? Seguramente no, porque todos somos muy valientes, hasta que el gallo asado picotea. Pero todavía hay algo que temer. Aunque la probabilidad de un ataque exitoso por parte de piratas informáticos precisamente en su banco no es tan alta, sin embargo, si se realiza, probablemente no se encuentre su dinero. Por qué Es muy simple: la primera suposición estándar del servicio de seguridad del banco es que alguien con los derechos de acceso apropiados tiene la culpa. No es un hacker, la probabilidad de interferencia que también consideran mínima, es decir, alguien propio. Por lo tanto, un hacker puede quedar impune.

¿Cómo solucionar este problema? Debe aprender cómo obtener números primos garantizados. ¿Pero cómo garantizar su simplicidad? Hay cuatro métodos para esto.

El primer método es reventar con un mínimo de restricciones. Esta suele ser una variante del tamiz mejorado de Eratóstenes. El método es confiable y está garantizado, pero está limitado a pedidos muy modestos (menos de cien). Por lo tanto, este método no es aplicable en criptografía.

El segundo método es la enumeración con restricciones más fuertes. Entonces, si el período de un número es igual al número mismo, menos uno, entonces se garantiza que el número sea primo. La fórmula aquí es: $$$N-1 = p$ . Pero para determinar la igualdad del período de la diferencia entre el número y la unidad, se utilizan métodos muy pesados ​​que no funcionan para todas las clases de números. Por lo tanto, su uso en criptografía se basa en el número limitado de números de clases específicas o durante la verificación, si aumentamos el tamaño del número. Y además, incluso los números de una determinada clase por sí mismos no garantizan nada, lo que significa la necesidad de ordenar muchos números candidatos. Aquí, por ejemplo, los números de Mersenne, para los cuales hay una prueba incondicional de simplicidad, ya se han resuelto y se ha descubierto que están prácticamente ausentes en el rango utilizado en la criptografía. Aquí está su lista completa con órdenes cercanas: 1279, 2203, 2281, 3217. Como puede ver, de 1024 a 2048 solo hay un número adecuado. Pero incluso si tomamos el resto, su número nos sugiere muy claramente: ¡no vale la pena! Así que nuevamente no tuvimos suerte con el método de verificación.

El tercer método es probabilístico. Es lo que se usa hoy, incluso en su banco favorito. Como trabaja el Muy simple: se verifica el resto de dividir un número arbitrario en una potencia $$$N-1$ en $$$N$ Si el resto es uno, es probable que el número sea primo. Y aquí la palabra "probablemente" es la más desagradable aquí. Aunque los métodos probabilísticos para verificar la simplicidad también contienen mejoras adicionales, sin embargo, como se muestra arriba, la biblioteca estándar de Java a menudo se equivoca.

Y finalmente, el cuarto método. No funciona tan rápido como las pruebas probabilísticas (aunque aquí también puede optimizar algo), pero proporciona primos garantizados, e incluso con un período fácilmente definible. ¿Para qué es un período prime? Por ejemplo, para generar una secuencia pseudoaleatoria o de cifrado. Más precisamente, conociendo el período, sabemos exactamente cuántos números habrá en la secuencia, lo que facilita planificar cuánto tiempo podemos usar el generador de secuencia en función de este número. Es cierto que esto ya se aplica al cifrado simétrico, pero también puede ser útil en varios casos. A continuación, consideraremos una teoría que garantiza la simplicidad de verificar los números de candidatos.

Antecedentes teóricos

Para comprender cómo generar números primos garantizados, debe sumergirse en un poco de matemática. Pero no se alarme, las matemáticas están aquí en el quinto grado.

Para completar, se recomienda mirar aquí para obtener detalles sobre el período y la serie de residuos. Bueno, diga brevemente que se forman varios residuos dividiendo la "esquina" (un método conocido por cualquier estudiante) de la unidad por el número elegido para el estudio. Al mismo tiempo, en cada paso, aparece una diferencia entre el número más alto, con un cero agregado, y el producto del número bajo investigación en un valor de 0 a 9 (para el sistema de números decimales): este es el resto. Pero hay muchos pasos para dividir por la "esquina", por lo tanto, también hay muchos residuos, y juntos forman una serie de residuos, en los que el mismo conjunto de números se repite periódicamente un número infinito de veces. Una señal del comienzo de un nuevo ciclo es un resto igual a uno. La cantidad de residuo entre unidades es la duración del período (o ciclo). De hecho, eso es todo, pero también vale la pena entender que dicho método de construir una serie de saldos se puede aplicar usando cualquier sistema de números, y en particular, el sistema con base 2 (en lugar de 10, como es habitual en la escuela) se usará con mayor frecuencia. Cuando se usan otros sistemas de números, se conservan todas las reglas, pero el número de variantes de producto en cada paso será diferente, igual a b (desde la base), es decir, la base del sistema de números.

Entonces, de lo que se muestra anteriormente, sabemos que los números compuestos siempre dan períodos relativamente cortos que no incluyen una cantidad de valores "prohibidos". Conociendo la factorización de un número compuesto, es fácil calcular cuántos valores deben estar ausentes en un número de residuos que forman el período de un número dado. Una serie de residuos no contendrá factores y todos los números que sean múltiplos de estos factores si la serie misma se construye sobre la base de un sistema de números que no es múltiplo de ninguno de los divisores (es decir, la base no se divide por divisores del número). Por ejemplo, si solo hay dos factores, la fórmula determina el número de residuos múltiples $$$m = a + b-2$ donde $$$m$ - el número de residuos múltiples, $$$a$ y $$$b$ Son los factores que forman nuestro número compuesto. Conociendo el número de residuos "prohibidos", es fácil calcular que una serie de residuos de más de la mitad del valor $$$N-1$ tendrá una longitud igual a $$$L = N-1- (a + b-2) = N-a-b + 1$ . Es decir, tal serie estará en $$$a + b-2$ más corta que la serie que resultaría si el número dado fuera primo. Esto explica por qué todos los números con un período igual al período completo (es decir, $$$N-1$ ), resultan simples: si al menos un elemento (que está "prohibido") se excluyera de la secuencia de residuos, entonces el período sería menor $$$N-1$ . Como resultado de la existencia de tal regularidad, observamos la operabilidad de todas esas pruebas de probabilidad, que hoy verifican la simplicidad de un número. Estas pruebas calculan valores en una serie de saldos por posición. $$$N-1$ o $$$(N-1) / 2$ , y si los valores son iguales $$$1$ o $$$N-1$ , entonces es muy probable que el número sea primo. ¿Por qué solo con alta probabilidad, y no garantizado? Porque el período de pruebas probabilísticas no se calcula, sino entre posiciones $$$N-1$ y $$$(N-1) / 2$ puede haber más unidades, lo que significará la desigualdad del período con respecto al valor $$$N-1$ pero si el periodo no es igual $$$N-1$ , entonces el número puede ser compuesto. Además, la falta de igualdad en sí misma no es crítica, otra cosa es importante: los números pseudo-simples pueden dar esa disposición de unidades. Entre los números verificados por dicha prueba, puede encontrar los pseudo-simples que son compuestos y que ayudan a los piratas informáticos que le roban su dinero. Después de todo, ¿cuáles son los divisores de tales números compuestos? Es muy posible que sean lo suficientemente pequeños como para que un atacante pueda abrir fácilmente un intercambio de datos cifrados.

Ahora recuerde por qué los números pseudoprimos pueden aparecer en absoluto. Tales números tienen períodos cortos que se repiten muchas veces dentro del período completo. $$$N-1$ por lo tanto, a veces pueden "encajar" y encajar varias veces en un período completo. Entonces, por ejemplo, el número 25 tiene un período de 4 para el sistema de números con base 7. $$$N-1$ para 25 es 24, intente dividir: 24/4 = 6. Es decir, este período se presenta un número entero de veces en un período completo. Este hecho puede verificarse mediante la fórmula anterior para acortar el período, pero teniendo en cuenta el hecho de que ayb son iguales en este caso. El período máximo posible será 24-4 = 20, aquí 24 es el número total de residuos, 4 es el número de residuos que son múltiplos de 5. Pero el período no siempre es el máximo, y todas las demás opciones se pueden obtener dividiendo el período máximo por completo. 20 se divide por 2,4,5,10, y solo dividiendo 20 por un número de la lista anterior obtenemos un período de 4 de longitud, que nos da al final del período completo $$$N-1$ unidad Y al verificar la simplicidad, solo se verifican los valores en la posición $$$N-1$ , es decir, el último valor en el período completo. Y para 25 es igual a 1, que es un signo de la simplicidad del número. Aunque, de hecho, es una clara señal de simplicidad, esto es cuando para todas las bases de los sistemas numéricos, menos $$$N$ , el último valor en el período completo es igual a uno. Pero no hay forma de verificar todos los sistemas de números para números grandes, por lo que aparecen números pseudo-simples, que a veces se usan incluso en criptografía, lo que aumenta la vulnerabilidad de nuestras finanzas.

¿Cómo eliminar la influencia de los números pseudoprimos? En principio, es simple: puede verificar los períodos para todos los sistemas de números, pero luego para esta operación no habrá tiempo suficiente para números grandes. Por lo tanto, iremos por el otro lado. Y la ruta también es simple (en sentido literal, usa otros números primos). Hemos visto que los períodos cortos pueden ajustarse a un período completo un número entero de veces, y esto nos da números pseudo-simples. Pero, ¿qué nos impide tomar y cancelar estos lunes? Sí, en general, nada impide.

Para períodos cortos, el período completo ( $$$N-1$ ) debe dividirse en muchos divisores. Entonces, para el número 25, el período completo 24 se divide en 2, 3, 4, 6, 8, 12. Hay muchas posibilidades de penetrar en el territorio protegido de números pseudo-simples. Por lo tanto, solo tenemos que tomar una prima como un período completo, porque no se divide en nada y, por lo tanto, nos salva automáticamente del elemento enemigo. Es cierto, hay un "pero": necesitamos números primos y, como saben, son impares (excepto por una excepción: 2), así que si $$$N-1$ simple entonces $$$N$ ya no puede ser simple. Por lo tanto, tendremos que admitir la posibilidad de la aparición de períodos incompletos. ¿Por qué es esto malo? Como vimos anteriormente, el período completo garantiza la simplicidad del número, pero aún no hemos demostrado el período incompleto. Entonces necesitamos probar este momento.

La prueba es bastante simple: para compuestos $$$N$ período de duración $$$N-1$ dos veces, obtenido en un sistema de números que no es múltiplo de los divisores de N, tiene solo dos filas de residuos, y ninguno de ellos debe contener números que sean múltiplos de los divisores de $$$N$ (Números "prohibidos"). Si se excluye al menos un elemento de una fila de residuos, entonces el segundo disminuye automáticamente en la misma cantidad (después de todo, una fila es igual a otra multiplicada por cualquier número que no esté en el primero). Entonces, si hay divisores en el número $$$N$ , obtenemos una duración total más corta de dos períodos con todos los saldos "permitidos" que el valor del período completo y, por lo tanto, movemos la unidad de su lugar al final del período completo, asegurando así la ausencia de pseudo-simplicidad. Pero, ¿puede el número de restos de divisores múltiples dar exactamente la mitad o un tercio del período completo? De hecho, entonces recibiríamos, por ejemplo, dos tercios de los saldos "permitidos" (dos filas) y un tercio de los saldos "prohibidos", y en total, el período completo. Pero para obtener un tercio necesitamos asegurar la divisibilidad del período completo ( $$$N-1$ ) por 3, que podemos excluir fácilmente: tomamos un número primo, lo multiplicamos por dos y agregamos uno al resultado; es decir, tenemos un número garantizado que excluye la pseudo-simplicidad. Con él, el número de divisores divisibles por divisores no puede ser igual a un tercio del período completo, porque no puede dividir por tres períodos completos. Queda la opción con la mitad del resto que es un múltiplo de los divisores. $$$N$ . Esta opción se elimina un poco más difícil, por lo que habrá una ligera digresión a continuación.

Cálculo del período, o todos los números: hijos de Mersenne

Se puede calcular el período de cualquier número. En el caso más simple, el cálculo se realiza simplemente dividiendo la esquina $$$1 / N$ hasta que encontremos un resto igual a uno (en el sistema de números, no un múltiplo de los divisores $$$N$ ) Pero para grandes números, esto es irrealmente largo. Por lo tanto, es necesario derivar una fórmula para calcular el período. Y dicha fórmula existe, aunque no en su forma ideal, cuando tenemos un número en la entrada y un período en la salida. La formula es:

$$

$$N = \ frac {b ^ {m + n + 1} -1} {b ^ n + k}$$

Aqui $$$N$ - número investigado, $$$b$ - la base del sistema numérico utilizado (base), $$$m$ - grado máximo $$$b$ en el cual el resultado de exponenciación es menor $$$N$ (en otras palabras, el índice de nivel superior en $$$N$ en el sistema numérico $$$b$ ), $$$n$ - distancia de izquierda a derecha en una serie de residuos del índice $$$m + 1$ (igual al número de bits en $$$N$ ) a uno, $$$k$ Es algún coeficiente entero.

Salida de fórmula

Por la definición de la fórmula, está claro que (1) $$$b ^ {m + 1} -N = x$ es decir, el primer grado $$$b$ que es más grande $$$N$ , te permite restar $$$N$ y obtener alguna diferencia en la forma $$$x$ . También se desprende de la definición que (2) $$$x * b ^ n-k * N = 1$ aqui $$k es un coeficiente entero. Si multiplicas(1)por$k$$$b n y reemplazar$b^n$$$x ∗ b n a su valor de(2), que es igual a$x*b^n$$$k N + 1 , entonces obtenemos$kN+1$$$$b^{m+n+1}=N*b^n+kN+1=N*(b^n+k)+1 => N=\frac{b^{m+n+1}-1}{b^n+k}$ .

Propiedades útiles

Como podemos ver, con esta fórmula puede obtener números con un período conocido. Es cierto, hay una dificultad: debe seleccionar un coeficiente$$k , que para grandes números nuevamente se convierte en algo inalcanzable. Pero la fórmula nos da algo más: vemos claramente cómo se forman todos los números. Sí, esta fórmula puede obtener absolutamente todos los enteros positivos, porque todos los números tienen algún punto. Y curiosamente, todos los números se obtienen dividiendo el número de Mersenne por uno de sus divisores. Recuerde que un número de Mersenne es un número que es igual a$k$$$$2^n-1$ .En la fórmula en el numerador, vemos una generalización para los números de Mersenne con cualquier base (incluyendo 2, por supuesto). Y si estamos interesados ​​en números primos, no necesitaremos otras bases además de 2.

Sabiendo que dividimos el número de Mersenne, sería útil para nosotros poder calcular el período de números precisamente para el caso de la división de números de Mersenne (recuerde el concepto extendido de período aquí ). Pero lo que es muy notable es que la fórmula para calcular el período de Mersen coincide con la fórmula para calcular un período del tipo$$$1/N$ . Bueno, para derivar la fórmula para dividir los números de Mersenne, se usa el mismo principio que cuando se deriva la fórmula para dividir $$1 / N , con la excepción de la fórmula para calcular el valor en una serie de residuos con índice$1/N$$$n que se parece a esto$n$$$b n + 1 - 1b - 1 , y para números binarios obtenemos$\frac{b^{n+1}-1}{b-1}$$$$2^{n+1}1$ .

Ahora tenemos todas las cartas a mano y podemos comenzar el juego abriendo los arqueros pseudo-simples en las filas de los números primos.

Como sabemos por series anteriores, cuando es divisible, todo el período de Mersen de un número debe ajustarse al número de dígitos del número de Mersenne un número entero de veces. Por lo tanto, en la fórmula anterior, una solución en enteros solo es posible si el denominador tiene un período igual al numerador o varias veces menor. Pero nos dará un período mucho más corto, incluidos los divisores del número mismo$$N , porque si$N$$$N divide el número de Mersenne, luego sus divisores también dividen el número de Mersenne. Y este es un punto muy importante, porque se deduce que las longitudes de los períodos de los divisores N dividen la duración del período$N$$$N completamente. Es decir, si tomamos$N$$$N es tal que su período es igual al período del numerador, entonces todos los divisores$N$$$N será al mismo tiempo divisores del número de Mersenne y, por lo tanto, debe encajar en el período y$N$$$N , y Mersenne numera un número entero de veces.$N$

De nuevo aproximadamente la mitad del período

Ahora recuerde que nos detuvimos en la búsqueda de una forma de demostrar que podemos excluir el caso cuando la mitad de la longitud de una serie de números residuales es un múltiplo de sus divisores. Queríamos probar esto para eliminar los números pseudo-primos al elegir un número primo como base para construir el período del próximo número primo. Entonces, ahora sabemos que si el número construido tiene divisores, entonces sus períodos siempre dividen el período del número construido completamente. Luego nos queda verificar qué divisores pueden encajar en las restricciones dadas previamente sobre el número construido. Y tales restricciones: su período se divide solo en$$2 y en adelante$2$$$$(N-1)/2$ . Por lo tanto, solo los números con puntos pueden ser divisores $$$2$ y $$$(N-1)/2$ . Periodo $$2 tiene un número$2$$$2 , ningún otro número de ese período tiene más. Periodo$2$$$2 no cabe un número entero de veces en$2$$$( N - 1 ) / 2 , porque$(N-1)/2$$$( N - 1 ) / 2 es primo, por lo tanto, la divisibilidad en tres se excluye durante dicho período. Por lo tanto, solo queda una posibilidad: los divisores tienen un período$(N-1)/2$$$$(N-1)/2$ . Pero el número no puede ser menor o igual a su período, por lo que el valor mínimo para los divisores es $$$(N-1)/2+1$ . Si multiplicamos dos divisores mínimos, obtenemos: $$( N - 1 ) 2 / 4 + ( N - 1 ) + 1 = ( N 2 - 2 N + 1 + 4 N ) / 4 = ( N 2 + 2 N + 1 ) / 4 , este valor debe no más ser$(N-1)^2/4+(N-1)+1=(N^2-2N+1+4N)/4=(N^2+2N+1)/4$$$N , porque estamos hablando de divisores$N$$$$N$ . Entonces obtenemos la desigualdad $$$(N^2+2N+1)/4\leq N => N^2-2N+1\leq 0$ . Esta desigualdad puede ser negativa o igual a cero solo para $$N = 1 , por lo tanto, para todos los números construidos de esta manera, se excluye la pseudo-simplicidad si el número resultante es mayor que$N=1$$$$1$ . Bueno, para números más pequeños, podemos probar la simplicidad incluso en la mente.

Ahora hay dos opciones: el nuevo número es un número primo, que es lo que necesitábamos, o este es un número compuesto y luego su período no se ajusta a un número entero de veces en un período completo, y por lo tanto, este número se puede verificar fácilmente por simplicidad calculando el último valor en una serie completa de residuos. Es decir, el número construido se puede verificar fácilmente con pruebas de simplicidad probabilísticas estándar, y lo que es importante, el resultado de la prueba no será probabilístico, sino garantizado. Entonces, al final, nos libramos de la maldición de la pseudo-simplicidad, que ejerce presión sobre todas las pruebas de probabilidad.

Pero, por supuesto, la vida sería miel si todos los problemas se resolvieran de manera tan simple. Al eliminar la pseudo-simplicidad, no excluimos números que no están ocultos para nadie y que no están enmascarados debajo de nada. Y con ellos hay un problema más: por el momento, podemos verificar un término arbitrario en la secuencia de residuos solo al elevar a un poder y luego tomar el resto. Pero este método es muy lento. Más precisamente, es lo suficientemente rápido para los números utilizados en criptografía, pero no es adecuado para encontrar números primos grandes en casa, ya que requiere muchos años de computación en una computadora doméstica normal, lo que no nos permite obtener 400k $ (como se muestra aquí ).

Sin embargo, casi todo está listo para calcular primos criptográficos. Aunque nuestro viejo amigo permanece: el maximalismo. Él pregunta: si puedes usar un período $$$(N-1) / 2$ , lo que impide el uso de períodos $$$(N-1) / 4, (N-1) / 6, (N-1) / 8$ etc.? Y resulta que con el debido cuidado, ¡nada lo impide!

De la misma manera que con el período $$$(N-1) / 2$ para el periodo $$$(N-1) / 4$ podemos establecer un límite inferior multiplicando un primo por 4 y sumando 1. Luego nos garantizamos que seamos simples con períodos inferiores a $$$(N-1) / 4$ . Por lo tanto, queda por considerar la posibilidad de ocurrencias pseudo-simples con un período múltiplo de 4, 3, 2 (1 se excluye para los componentes, como se muestra arriba). De la fórmula para calcular el número por el período se observa que el período del dividendo debe ser igual al mínimo común múltiplo de sus divisores, lo que implica que el período posible del número $$$N$ no solo debe caber un número entero de veces en $$$N-1$ (de lo contrario no habrá seudo-simplicidad), sino que también contendrá un número entero de períodos de divisores. Por lo tanto, el número de posibles divisores de un número pseudo-primo está muy limitado. Dado que el período de cualquier número no puede ser más largo $$$N-1$ , entonces para un posible divisor $$$N$ dando como resultado de la división 3, el período no puede ser más largo $$$N / 3-1$ Además, tenemos en cuenta que el período de 3 es 2. $$$N / 3$ debe ser extraño porque es extraño $$$N$ . De lo anterior se deduce que el período par N / 3-1 es el mínimo común múltiplo con un período 2 del número 3, lo que significa que el posible período de un N potencialmente pseudo-simple debería ser igual al período del número $$$N / 3$ . En total hay un valor del período $$$N$ para lo cual es posible la pseudo-simplicidad, esto $$$(N-1) / 4$ . Para otros valores, ya sea $$$N / 3$ demasiado poco o su período (y con él el período $$$N$ ) irá al área prohibida a continuación $$$(N-1) / 4$ . La misma historia con números impares, menos $$$N / 3$ pero sus períodos no pueden ser más largos $$$(N-1) / 4$ y, por lo tanto, todos ellos simplemente están excluidos de consideración. Ahora muestra que $$$N / 3$ no puede tener un período $$$(N-1) / 4$ , lo que significa que no puede dividir todo el período por completo. Primero, recuerda la fórmula $$$m = a + b-2$ , que nos da el número de residuos de divisores múltiples para un número divisible solo por $$$a$ y $$$b$ . En nuestro caso $$$N$ se supone que se divide en $$$N / 3$ y en 3, todos los demás divisores están excluidos, por lo que obtenemos: $$$m = N / 3 + 3-2 = N / 3 + 1$ . Ahora del período completo necesita restar los valores "prohibidos", que serán $$$N / 3 + 1$ , y luego dividir por 4. Obtenemos el posible período de trabajo $$$3 * N / 3$ : $$$p = (N-1-N / 3-1) / 4 = N / 6-1 / 2$ que menos $$$(N-1) / 4$ es decir, un período de duración $$$(N-1) / 4$ imposible debido a la necesidad de tener en cuenta los residuos "prohibidos", que lleva todos los períodos pseudo-simples posibles a la región prohibida (menos $$$(N-1) / 4$ ) Esto significa que esta situación nos garantiza que el número construido no es pseudo-simple y, por lo tanto, podemos estar seguros de los resultados de una prueba de simplicidad probabilística posterior.

Del mismo modo, y teniendo en cuenta la divisibilidad del período completo, se pueden obtener los mismos resultados para otros valores. Pero si queremos obtener números primos criptográficos de esta manera, multiplicando por 2,4,6 aumentaremos el tamaño del número durante mucho tiempo, por lo que tiene sentido mirar en la dirección de otra opción: la multiplicación de dos números primos. Si multiplicamos un primo por otro, obtenemos un número impar, por lo que también debemos multiplicar por 2 para obtener un período completo par y un candidato impar para primo. El período completo en este caso se dividirá en $$$2, a, b, 2a, 2b, ab$ donde $$$a$ y $$$b$ Son números primos. Ahora tenemos que demostrar que los períodos indicados no darán pseudo simplicidad o encontrar signos que nos adviertan sobre la presencia de pseudo simplicidad. Solo tenga en cuenta que si el período es igual a $$$2 * a * b$ , entonces el número será primo (como se muestra arriba). También se muestra arriba que un número de medio período no puede ser pseudo-simple, por lo tanto, un período de longitud $$$ab$ puede ser excluido Aunque para completar, puede verificar el período $$$ab$ formas alternativas Entonces, si el período es $$$ab$ , entonces dado que $$$a$ y $$$b$ simple, queda claro que el mínimo común múltiplo de períodos divisores $$$N$ solo puede ser igual $$$ab$ , mientras que los períodos de los divisores pueden ser iguales a $$$ab$ ambos o uno $$$a$ y otro $$$b$ . Como el período siempre es menor que el número en sí mismo, entonces $$$(ab + x) * (ab + y)$ obviamente habrá más $$$2ab + 1$ . Por lo tanto, la pseudo-simplicidad no es posible con ese período. Por lo tanto, queda por verificar los períodos $$$2, a, b, 2a, 2b$ . 2 es menor que el período de período mínimo posible para todos los números, más de 3, por lo tanto, excluimos dicho período. Ahora suponga que el número construido se divide por $$$m$ y $$$n$ , luego con la igualdad del período $$$N$ significado $$$a$ , sus períodos también serán iguales $$$a$ , porque este es el único múltiplo menos común para dos números, porque $$$a$ No se divide en nada. Se sigue que $$$(a + x) * (a + y) = N = ab * 2 + 1$ donde $$$a + x = m$ - el primer factor posible con un punto $$$a$ y $$$a + y = n$ - segundo. Siguiente: $$$a ^ 2 + ax + ay + xy = 2ab + 1$$$$=>$$$$a ^ 2 + ax + ay + (ka + r) = 2ab + 1$$$$=>$$$$a + x + y + k = (2ab + 1-r) / a$ . Aqui $$$r$ puede ser igual a uno solo, de lo contrario el entero no funcionará a la izquierda. Entonces: $$$x + y + k = 2b-a$ , de lo cual se deduce que si $$$a \ geq 2b$ , luego pseudo-simple con un punto $$$a$ no puede ser Queda por verificar la pseudo-simplicidad en $$$a <2b$ , que se puede hacer comprobando los valores en la serie de residuos en la posición $$$a$ si hay 1, ese número puede ser pseudo-simple y debería excluirse de otras operaciones. Razonamiento para $$$b$ completamente análogo, lo que significa la necesidad de verificar la igualdad de la unidad y su resto, siempre que $$$b <2a$ .

Para el periodo $$$2a$ tenemos: $$$4a ^ 2 + 2ax + 2ay + xy = 2ab + 1$$$$=>$$$$4a ^ 2 + 2ax + 2ay + (ka + r) = 2ab + 1$$$$=>$$$$4a + 2x + 2y + k = (2ab + 1-r) / a$$$$=>$$$$2x + 2y + k = 2b-4a$ . Lo conseguimos por $$$4a \ geq 2b$ (o equivalentemente - $$$2a \ geq b$ ) nuevamente, no puede haber simplicidad, pero si $$$2a <b$ , entonces debe verificar el saldo en la posición $$$2a$ . Del mismo modo para $$$b$ - comprobar si $$$2b <a$ . En total, obtenemos para $$$a$ y para $$$b$ la necesidad de verificar solo las líneas de pedido $$$2a$ y $$$2b$ porque períodos $$$a$ y $$$b$ se repetirá justo en posición $$$2a$ y $$$2b$ . La verificación se realiza solo en las condiciones anteriores, lo que casi duplicará el proceso al verificar valores grandes $$$a$ o $$$b$ porque para ellos deben $$$a \ geq 2b$ con el esquema de generación simple a continuación, y los valores más bajos se verificarán muy rápidamente debido a su pequeño tamaño.

Por lo tanto, los fundamentos teóricos se han demostrado anteriormente para poder generar números primos garantizados para áreas críticas como la criptografía.

Además, se abre un camino para verificar la simplicidad de un número arbitrario, siempre que se encuentren los divisores de su período completo ( $$$N-1$ ) Entonces, para primos <126,000,000, el número de "primos multiplicados" que pertenecen a la clase es 676625, con el número total de primos 7163812, lo que nos da un poco menos de 9.5%. Para primos de hasta mil millones, tenemos 3.49% perteneciente a la clase 2p + 1, 1.8116% de la clase 4p + 1, 2.4709% de la clase 6p + 1, y solo 7.7746%, donde p es un número primo. Es cierto que debe tenerse en cuenta que la descomposición del período completo de grandes números es muy difícil. En este caso, puede ofrecer un cheque recursivo, que aumentará ligeramente el tamaño de los números disponibles para verificar, pero al mismo tiempo reducirá en gran medida la proporción de números que pasan dicho cheque, porque si el coeficiente que determina la membresía de las clases de números primos recursivos se toma igual a 0.2, entonces ya en el segundo cheque lo haremos tener solo 0.04, o 4% del número total de primos. Sin embargo, en algunos casos, este enfoque puede ser beneficioso.

Resultados prácticos

El generador en sí, por supuesto, fue escrito y probado, ya que la complejidad allí es mínima. Durante la verificación, resultó que el siguiente algoritmo sería completamente funcional:

Obtenemos, por ejemplo, 1000 primos iniciales, que pueden generarse utilizando el tamiz de Eratóstenes o simplemente descargarse desde aquí . Luego multiplicamos cada valor con cada uno restante y no olvidemos multiplicar por dos, y luego sumar uno. El candidato resultante a menudo se divide por 3, porque los primos tienen una característica específica similar a la presencia de una carga en las partículas en física. Las personas simples con la misma "carga" son repelidas, y con otras diferentes se sienten atraídas. En este caso, la "carga" es el resto de la división entre 3. Es decir, si el resto de la división entre 3 es el mismo para ambos primos, el nuevo primo no funcionará, porque se dividirá entre 3. Y si el resto es diferente, entonces podemos obtener el correcto candidato a simple. Además, todos los simples obtenidos por multiplicación están "sincronizados", es decir, reciben el mismo resto igual a 2. Por lo tanto, es inútil multiplicarlos por sí mismos nuevamente. Entonces, para obtener nuevos números primos, necesitamos filtrar esa parte de los 1000 iniciales, en la que el módulo del triple (el resto de la división entre 3) es 1. Por lo tanto, después de la primera multiplicación de todos con todos, crecemos en la cantidad de números que ya no tienen sentido multiplicarse entre sí, por lo tanto, para aumentar aún más el tamaño (al que se usa en criptografía), debemos multiplicar una y otra vez los números primos obtenidos por los números de "carga opuesta" previamente seleccionados. Después de multiplicar y agregar una unidad, llevamos a cabo verificaciones de acuerdo con el criterio de la posibilidad de pseudo-simplicidad y, si se cumple el criterio, verificamos el resto en la posición 2a para cada candidato. Si hay 1, entonces el candidato es rechazado. A continuación, cada candidato se verifica mediante la prueba probabilística habitual, es decir, el valor se calcula en la serie de residuos en la posición $$$(N-1) / 2$ si es 1 o $$$N-1$ , entonces frente a nosotros hay un número primo garantizado.

Al realizar la generación, debe tenerse en cuenta que en cada iteración, se obtiene un aumento en el número de primos generados, es decir, el coeficiente de multiplicación para 1000 primos iniciales es mucho más que la unidad. Por lo tanto, para obtener primos criptográficos, es necesario limitar la generación; de lo contrario, llevará mucho tiempo y es posible que no haya suficiente memoria. Al mismo tiempo, no se debe reducir el conjunto inicial de simples, porque la generación debe ser lo más aleatoria posible, de modo que, conociendo su algoritmo, el atacante no pueda predecir los valores resultantes. Para esto, es necesario implementar un mecanismo para cortar las ramas del árbol de generación, que permite cada vez obtener unas simples únicas ubicadas bastante lejos de las generadas previamente. Y, por supuesto, cortar el exceso acelera significativamente el proceso.

El tiempo de ejecución de la prueba depende del número de candidatos generados. Cada uno de los candidatos pasa una prueba de probabilidad, que ralentiza la generación en la mayor medida. En las pruebas para obtener unos pocos cientos de simples en rango $$$2 ^ {900}$ - $$$2 ^ {1200}$ Se gastaron de 5 a 20 minutos. Esta diferencia horaria se explica por varias formas por las que pasa el algoritmo en el árbol de generación. Inicialmente, la generación se limita a unos 10 números, pero a medida que se acerca el tamaño criptográfico, la generación se desvanece debido a una reducción significativa en el coeficiente de multiplicación con el aumento del número. Por lo tanto, es necesario aumentar el número de primos intermedios, pero es difícil decir qué tan específico es, y por lo tanto, un simple aumento de la cantidad permitida por un factor de dos se usa para limitarlo con un aumento en el tamaño del número y un exceso de un umbral aproximado. Como resultado, dentro de los límites de las limitaciones, el número de nuevos simples puede flotar y, por lo tanto, hacer una diferencia significativa en el tiempo total de generación.

El siguiente es el texto de un procedimiento Java que genera números primos. Naturalmente, no satisface los requisitos criptográficos que van mucho más allá del código del programa y se relacionan principalmente con problemas organizacionales. En la parte puramente de software, el procedimiento no implementa el mecanismo para recortar las ramas del árbol de generación, excepto por la restricción más simple. Sin embargo, como ejemplo de la implementación del algoritmo de generación, el programa puede ayudar con algo.

Los parámetros de entrada son la lista inicial de simple y PrintWriter para guardar el resultado en un archivo. Después de completar el algoritmo, el archivo contendrá todos los productos de los primos generados con esos números iniciales que tienen un módulo de tres igual a uno. El resultado puede verificarse con la ayuda de los servicios en línea que implementan la factorización de números, pero debe entenderse que pueden usar una prueba probabilística por simplicidad antes de realizar la factorización y, por lo tanto, para verificar el enfoque propuesto, se vuelven inútiles (porque todos los números ya están verificados por una prueba probabilística). Pero algunos de ellos comienzan a factorizar el número propuesto en factores, tales sitios pueden infundir cierta confianza adicional en la corrección del método propuesto.

public static void generatePrimes(List<Integer> primes, PrintWriter pw) { List<BigInteger> mod3_1 = new ArrayList<BigInteger>(); List<BigInteger> l = new ArrayList<BigInteger>(); BigInteger three=BigInteger.valueOf(3), two=BigInteger.valueOf(2); for (int k=0;k<primes.size()-1;k++) { BigInteger seed=BigInteger.valueOf(primes.get(k)); BigInteger s2=seed.shiftLeft(1); BigInteger r0=seed.remainder(three); if (r0.intValue()==1) mod3_1.add(seed); for (int i=k+1;i<primes.size();i++) { BigInteger p=BigInteger.valueOf(primes.get(i)); BigInteger r=p.remainder(three); if (r.intValue()==r0.intValue()) continue; // divisible by 3 else addIfPrime(p,seed,s2,two,l); } } List<BigInteger> ps=l; do { System.out.println("found "+l.size()+", bits="+l.get(0).bitLength()); l=new ArrayList<BigInteger>(); for (int k=0;k<ps.size();k++) { BigInteger seed=ps.get(k); BigInteger s2=seed.shiftLeft(1); for (int i=0;i<mod3_1.size();i++) addIfPrime(mod3_1.get(i),seed,s2,two,l); int n=100000; // change following to adjust for required bit count if (l.size()>0) if (l.get(0).bitLength()<700) n=10; else if (l.get(0).bitLength()<800) n=20; else if (l.get(0).bitLength()<900) n=40; if (l.size()>n) break; } ps=l; for (int i=0;i<l.size();i++) pw.println(l.get(i)); pw.flush(); } while (l.size()>0); System.out.println("Done"); } private static void addIfPrime(BigInteger a, BigInteger b, BigInteger b2, BigInteger two, List<BigInteger> l) { BigInteger a2=a.shiftLeft(1), fp=b.multiply(a2), n=fp.add(BigInteger.ONE); BigInteger r=null; if (a2.compareTo(b)<0) r=two.modPow(a2,n); // 2a<b else if (a.compareTo(b2)<0) r=two.modPow(a,n); // a<2b if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=null; if (b2.compareTo(a)<0) r=two.modPow(b2,n); // 2b<a else if (b.compareTo(a2)<0) r=two.modPow(b,n); // b<2a if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=two.modPow(fp.shiftRight(1),n); if (r.compareTo(BigInteger.ONE)!=0) return; l.add(n); } 

Bueno, ahora que (bueno, casi) sabes todo sobre la generación de números primos, tal vez tus intereses irán más allá de la criptografía sola y te resultará interesante estudiar teoría de números, ya que, como se mencionó anteriormente, está disponible para estudiantes de quinto grado, pero al mismo tiempo también le permite encontrar diamantes verdaderos independientemente sin esperar la ayuda de matemáticos serios.