Hogar › Ajustes › Algoritmos utilizados en la implementación de esquemas criptográficos asimétricos. Requisitos para el algoritmo y su implementación. Pruebas probabilísticas de primalidad

Algoritmos utilizados en la implementación de esquemas criptográficos asimétricos. Requisitos para el algoritmo y su implementación. Pruebas probabilísticas de primalidad

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Fue hace mucho tiempo, en la universidad, cuando empezamos a aprender el idioma. programación Pascal y mi tarea era crear un algoritmo para encontrar numeros primos.

El algoritmo fue inventado e implementado inmediatamente en el idioma de destino. El programa pidió al usuario el número N y buscó todos los números primos hasta N inclusive. Después de la primera prueba exitosa, inmediatamente surgió una necesidad irresistible de ingresar N = “muchos”. El programa funcionó, pero no tan rápido como nos gustaría. Naturalmente, hubo numerosos controles (del orden de N*N/2), por lo que tuvimos que deshacernos de los innecesarios. El resultado fueron 5 algoritmos similares, cada uno de los cuales funcionó más rápido que el anterior. Recientemente quise recordarlos e implementarlos, pero esta vez en Python.

Entonces, vámonos. El primer algoritmo que llamó la atención del estudiante se demuestra en el Listado 1.
# Listado 1 # ingresa N n = input("n=") # crea una lista vacía para almacenar números primos lst = # en k almacenaremos el número de divisores k = 0 # recorre todos los números del 2 al N para i in xrange(2, n+1): # recorre todos los números desde 2 hasta el actual para j in xrange(2, i): # busca el número de divisores si i % j == 0: k = k + 1 # si no hay divisores, agrega el número a la lista si k == 0: lst.append(i) else: k = 0 # muestra la lista print lst
Rápidamente te das cuenta de que no es necesario contar los divisores de cada número y, por tanto, la variable k puede quedar libre de sus funciones. De hecho, si hay al menos un divisor, entonces el número ya no es primo. Veamos el Listado 2.
# Listado 2 n = input("n=") lst = for i in xrange(2, n+1): for j in xrange(2, i): if i % j == 0: # si se encuentra el divisor, número no simple.
romper otra cosa: lst.append(i) imprimir lista
La construcción break nos permite completar la ejecución del bucle interno y pasar a la siguiente iteración del bucle externo.
Entonces surge la pregunta: “¿por qué dividir entre 4 si el número no es divisible por 2?” Llegamos a la conclusión de que debemos buscar divisores solo entre los números primos que no excedan el dividendo. Nuestro algoritmo se convierte en... ver Listado 3.
Y luego recordamos la teoría de los números y entendemos que solo necesitamos clasificar los números que no excedan la raíz del deseado. Por ejemplo, si el número M tiene un divisor pi, entonces hay un divisor qi tal que pi * qi = M. Es decir, para encontrar un par basta con encontrar el más pequeño. Entre todos los pares, el par estimado con el mayor y menor es el par con pi y qi iguales, es decir, pi * pi = M => pi = sqrt(M). Veamos el Listado 4.
# Listado 4 de math import sqrt n = input("n=") lst= for i in xrange(2, n+1): for j in lst: if j >
El código del Listado 4 con N=10000 se ejecuta aproximadamente 1000 veces más rápido que la primera opción. Existe otro "acelerador" para marcar sólo aquellos números que terminan en 1, 3, 7 o 9 (ya que el resto obviamente son divisibles por 2 o 5). Veamos el Listado 5.
# Listado 5 de math import sqrt n = input("n=") lst= for i in xrange(2, n+1): if (i > 10): if (i%2==0) o (i% 10==5): continuar para j en lst: if j > int((sqrt(i)) + 1): lst.append(i) romper if (i % j == 0): romper else: lst.append (i)imprimir lista
Un cambio menor en el Listado 5 da como resultado un pequeño aumento de velocidad:
# Listado 6 de math import sqrt n = input("n=") lst= for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continuar durante j en lst: if j > int((sqrt(i)) + 1): lst.append(i) romper si (i % j == 0): romper else: lst.append(i) imprimir lst
Total: El programa del último listado se ejecuta aproximadamente 1300 veces más rápido que la versión original.
No me propuse la tarea de escribir un programa que resuelva problemas lo más rápido posible. esta tarea, es más bien una demostración para los programadores novatos de que un algoritmo compuesto correctamente juega un papel importante en la optimización de sus programas.

PD
Gracias a los comentarios, obtenemos el Listado 7:
# Listado 7 n = input("n=") lst= para i en xrange(3, n+1, 2): si (i > 10) y (i%10==5): continúa para j en lst: si j*j-1 > i: lst.append(i) romper if (i % j == 0): romper else: lst.append(i) imprimir lst

Con N=10000, enseñamos la hora:
tiempo 1 = 26,24
tiempo 2 = 3.113
tiempo 3 = 0,413
tiempo 4 = 0,096
tiempo 5 = 0,087
tiempo 6 = 0,083
tiempo 7 = 0,053

Criba de Eratóstenes:
# Listado 8 n = input("n=") a = range(n+1) a = 0 lst = i = 2 while i<= n: if a[i] != 0: lst.append(a[i]) for j in xrange(i, n+1, i): a[j] = 0 i += 1 print lst

Resultados para n = 1.000.000:
tiempo 7 = 7.088
tiempo 8 = 1.143

k (\displaystyle k), cuyo algoritmo de generación está sujeto a ciertas restricciones. La obtención de números primos aleatorios es una parte integral de los procedimientos de derivación de claves en muchos algoritmos criptográficos, incluidos RSA y ElGamal.

Debido a que probar la primalidad de números grandes requiere una cantidad significativa de tiempo, el requisito de primalidad para el número resultante a menudo se relaja hasta una fuerte pseudoprimariedad por varias razones aleatorias diferentes. Los algoritmos existentes para probar una pseudoprimalidad fuerte son órdenes de magnitud más rápidos que los algoritmos de prueba de primalidad más conocidos. Al mismo tiempo, es muy probable que los números que pasan con éxito pruebas pseudoprimas estrictas utilizando varias bases aleatorias sean primos, y esta probabilidad aumenta con el número de bases probadas.

Requisitos para el algoritmo y su implementación.

Los requisitos de los algoritmos para generar números primos aleatorios se reducen a los dos siguientes:

La distribución de los números primos resultantes debe ser casi uniforme en el conjunto de todos k números primos de bits. Hay varias formas de garantizar que se cumpla este requisito.
Proceso de generación específico un número primo aleatorio no se puede reproducir incluso si conocemos los detalles del algoritmo y su implementación. Normalmente, este requisito se cumple mediante el uso de un PRNG seguro inicializado con alguna clave obtenida del exterior (es decir, que no forma parte del algoritmo ni de su implementación). La clave puede ser, por ejemplo, el valor de una función hash criptográfica de la frase secreta solicitada al usuario.

Algoritmos típicos para generar números primos aleatorios

En todos los puntos siguientes, se supone que se utiliza un PRNG criptográficamente fuerte, inicializado con una clave secreta (los detalles dependen del PRNG utilizado y del método para obtener y presentar la clave).

Pruebas de simplicidad

Comprobar la (probable) primacía de un número pag que contiene k bits, puedes hacer esto:

Asegurar que pag no es divisible por números primos pequeños 3, 5, 7, 11, etc. hasta un pequeño límite (por ejemplo, 256). Esta verificación le permite cortar de manera efectiva muchos números que se sabe que son compuestos antes de verificarlos utilizando algoritmos que requieren más mano de obra. Entonces, prueba de divisibilidad pag para números primos 2, 3, 5 y 7, elimina todos los números pares y el 54% de los impares, verificación de divisibilidad pag para todos los números primos hasta 100 se elimina el 76% de los números impares, y la prueba de divisibilidad pag para todos los números primos hasta 256, elimina el 80% de los números impares.
Realizar la prueba de Miller-Rabin con al menos un número de rondas k.

si el numero pag no pasa al menos una prueba, no es sencillo. De lo contrario, con una alta probabilidad (dependiendo del número de rondas) el número pag es sencillo.

Construcción directa

El segundo paso se puede acelerar considerando sólo números impares o números comparables a 1 y 5 mod 6, etc.

(norte-1)-métodos

(norte-1) -los métodos para construir números primos utilizan el conocimiento sobre los divisores primos de un número norte-1 para pruebas de simplicidad norte usando

Conferencia_4_parte_2.

Algoritmos aritméticos y su aplicación en criptografía.

Un número natural p mayor que uno se llama primo si es divisible sólo por 1 y por sí mismo.

Teorema (Euclides). El conjunto de los números primos es infinito.

Denotemos por p(x) la función que es igual al número de números primos p en el intervalo 1< x

x/lnx< p(x) < 1,106 x / ln x .

Los números primos son un concepto importante en criptografía. Muchos sistemas criptográficos modernos se basan en un número primo. Por lo tanto, los algoritmos para generar números primos y verificar la primalidad del número generado son herramientas importantes al crear un sistema criptográfico.

Los números primos son bastante comunes.

Tenga en cuenta que hay alrededor de 10151 números primos con una longitud de 1 a 512 bits inclusive, y el número de números primos menores que 2512 es aproximadamente igual a 2503/ Para números cercanos a n, la probabilidad de que un número elegido arbitrariamente sea un número primo es 1/ln(n). Si selecciona aleatoriamente dos números primos en el rango de 1 a 151 bits, la probabilidad de que estos números coincidan es insignificante. Los números primos juegan.

papel importante en la criptografía moderna. Muchos sistemas criptográficos de clave pública (o asimétrica) modernos se forman utilizando números primos.

Para números primos consideraremos tres problemas:

· construcción de números primos;

· comprobar números para simplificar;

· factorización (descomposición) de números en factores primos.

De hecho, estos tres problemas responden a una pregunta: si el número en cuestión es primo. Pero para cada una de estas tareas se utilizan métodos diferentes. Para el primer problema, utilizando las condiciones de simplicidad necesarias, se pueden dar respuestas como:

· el número dado n no es primo;

· la probabilidad de que un número dado n no sea primo es menor que un número dado e.

Para el segundo problema, puedes construir una determinada secuencia de números de una forma especial. Y para los números de una secuencia determinada, aplicar algunas pruebas hasta encontrar un número primo entre ellos.

Presentemos algunas definiciones, teoremas y algoritmos relacionados con problemas de solución.

tareas asignadas

Definición 1. Los números Fk = 2a + 1, a = 2k, k = 0, 1, 2,… se llaman números de Fermat.

Teorema 1. El número de Fermat n = Fk para k > 0 es

simple si y solo si

Definición 2. Sea p un número primo. Los números de la forma Mp = se llaman números de Mersenne.

El interés por los números de Mersenne se debe a su conexión con los llamados números perfectos, números iguales a la suma de todos sus divisores, diferentes, por supuesto, del número mismo. Euclides también demostró (tú también puedes probarlo) que si un número primo p tiene la forma Mp, entonces el número p(p+1)/2 es perfecto. Por ejemplo,

3 = 2 2 – 1, 7 = 2 3 – 1

números primos y en consecuencia

Donde Mp es el número de Mersenne. Recordemos que un número perfecto es un número que es igual a la suma de todos sus divisores menores que él mismo.

Los números de Mersenne son raros. En 2001, se encontró el trigésimo noveno número de Mersenne para p = 1.3466.917.

Para comprobar la primacía de los números de Mersenne, se utiliza el siguiente teorema.

Teorema 2. Sea p un número primo, p > 2, Mp =

1. Considere la secuencia L0, L1,…, que

está determinada por las relaciones

L0 = 4, modificación p, 0 ≤ j< p.

El número Mn es primo si y sólo si Lq-2 =0 mod p.

COMPROBANDO LA SIMPLICIDAD

Los números primos son necesarios para la mayoría de los sistemas criptográficos de clave pública.

El material teórico sobre la construcción de números primos grandes se puede encontrar en y. Aquí sólo algunas prácticas

Métodos para generar números primos grandes. Se pueden utilizar los dos enfoques siguientes para generar números primos grandes:

· se generan números aleatorios de un orden determinado y se utilizan pruebas existentes

comprueba si son primos.

· los números primos se generan usando un determinado algoritmo y con la ayuda de ciertas pruebas se comprueba la simplicidad de los números.

Primero, veamos las pruebas que se utilizan para implementar el primer enfoque.

formando un número primo.

División de prueba

Uno de los más maneras simples comprobar la primalidad de un número p consiste en dividir secuencialmente el número p por todos los números impares contenidos en

intervalo Si en el proceso de división obtenemos un resultado entero, entonces el número p es compuesto. Si, al buscar entre todos los números impares del intervalo

Es imposible dividir completamente el número p en estos números, entonces el número p es primo. este método llamada división de prueba. Este método requiere mucha mano de obra en número. operaciones aritméticas y se utiliza principalmente para probar números primos pequeños.

Tamiz de Eratóstenes

Si queremos hacer una tabla de todos los números primos entre los números.

2, 3,…, N, entonces debes tachar secuencialmente todos los números que son divisibles

· en 2, excepto 2;

· en 3, excepto 3;

· en 5 excepto 5;

· al siguiente número que no esté tachado,

además de este número;

etc. Como resultado, entre los números del 1 al N solo quedarán los números primos. Para implementar el método, se necesita una gran cantidad de memoria de computadora, pero es mejor para compilar tablas de números primos. Además, se están desarrollando procesadores especiales en los que las operaciones de cribado se realizan de forma muy eficaz.

Comentario. La división de prueba y la criba de Eratóstenes se pueden utilizar para resolver el problema de factorizar un número entero.

Criba de Eratóstenes.

Para encontrar todos los números primos no mayores que un número dado n, siguiendo el método de Eratóstenes, es necesario realizar los siguientes pasos:

Escribe todos los números enteros del dos al n (2, 3, 4, ..., n) seguidos.

Sea la variable p inicialmente igual a dos, el primer número primo.

Tacha de la lista todos los números del 2p al n que sean divisibles por p (es decir, los números 2p, 3p, 4p, ...)

Encuentre el primer número no cruzado mayor que p y asigne el valor de la variable p a este número.

Repita los pasos 3 y 4 hasta que p sea mayor que n

Todos los números no cruzados de la lista son números primos.

En la práctica, el algoritmo se puede mejorar ligeramente de la siguiente manera. En el paso número 3, los números se pueden tachar, comenzando inmediatamente con el número p2, porque todos los números compuestos menores que él ya estarán tachados en ese momento. Y, en consecuencia, el algoritmo se puede detener cuando pag 2 será mayor que norte.

Ejemplo para n = 20

Escribamos los números naturales del 2 al 20 seguidos:

El primer número de la lista 2 es primo. Repasemos una serie de números, tachando todos los números que son múltiplos de 2 (cada segundo, comenzando con 2^2 = 4):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

El siguiente número 3 no cruzado es primo. Repasemos una serie de números, tachando todos los números que son múltiplos de 3 (cada tercio, comenzando con 3^2 = 9):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

El siguiente número 5 no cruzado es primo. Repasemos una serie de números, tachando todos los números que sean múltiplos de 5 (uno de cada cinco, comenzando con 5^2 = 25). Etc.

Es necesario tachar los múltiplos de todos los números primos p para los cuales . Como resultado, todos los números compuestos serán tachados y todos los números primos permanecerán sin tachar. Para norte= 20, después de tachar los múltiplos de 3, se tachan todos los números compuestos.

teorema de wilson

Para cualquier P las siguientes condiciones son equivalentes:

1). P – simple;

2). (P-1)!=-1 (mod P)

Ineficaz debido a la alta intensidad laboral.

El pequeño teorema de Fermat establece que si norte simple, entonces se cumple la condición: para todos a de (1, 2,…, norte−1) se realiza la comparación

un−1 ≡ 1 (mod. norte) (1)

De este teorema se deduce que si la comparación (1) no se cumple para al menos un número a en el intervalo (1, 2,…, norte−1), entonces norte- compuesto. Por tanto, podemos proponer la siguiente prueba de primalidad probabilística:

elige un número aleatorio a de (1, 2,…, nortea, norte) = 1;

norte- compuesto";

comprobar la viabilidad de la comparación (1);

si no se realiza la comparación, entonces la respuesta es “ norte- compuesto";

si se hace la comparación, entonces se desconoce la respuesta, pero se puede repetir la prueba nuevamente.

Números de Carmichael

Los llamados números de Carmichael son especialmente malos para el test de Fermat. Tienen la siguiente propiedad: para cualquier a tal que ( a, norte) = 1 correcto

Los primeros tres números de Carmichael son: 561, 1105, 1729. Entre los primeros 100.000.000 de números sólo hay 255. Sólo recientemente (1994) se demostró que existe un número infinito de tales números.

Prueba probabilística de Miller-Rabin

Dejar norte- extraño y norte − 1 = 2calle, t- extraño.

si el numero norte es simple, entonces para todos a> Se realiza 1 comparación

un−1 ≡ 1 (mod. norte)

Por lo tanto, considerando los elementos ( en, a 2t, …, a 2s−1t) se puede observar que cualquiera de ellos es igual a −1 (mod norte), o en≡ 1 (mód. norte).

La siguiente prueba de primalidad probabilística se basa en esta observación:

elige un número aleatorio a del intervalo (1, 2,…, norte−1) y usando el algoritmo euclidiano comprobamos la condición ( a, norte) = 1;

si no se cumple, entonces la respuesta es “ norte- compuesto";

calcular en(modificación norte);

Si en≡ ±1 (mód. norte), luego vaya al paso 1;

calcular a 2t, …, a 2s−1t hasta que aparezca −1;

Si ninguno de estos números es igual a −1, entonces la respuesta es “ norte- compuesto";

si hemos llegado a −1, entonces la respuesta es desconocida (y la prueba se puede repetir nuevamente).

Un número compuesto no se identificará como compuesto con probabilidad de 1 ⁄ 4 (ver).

Teorema

Si la hipótesis ampliada de Riemann es cierta, entonces basta con comprobarlo todo. a de (2, 3,…, +1) (ver).

Construcción de grandes números primos.

Prueba basada en el pequeño teorema de Fermat

El pequeño teorema de Fermat establece que si n es un número primo, entonces se cumple la condición: para todo a О (2,3,…, n – 1) se cumple la comparación An - 1 º 1 mod n.

Con base en este teorema, es posible construir un algoritmo probabilístico para verificar la primalidad del número n.

Si para algún número entero a del intervalo la relación an - 1 º 1 mod n no se cumple, entonces el número n es compuesto. Si el teorema es verdadero, entonces no se puede llegar a la conclusión de que el número n es primo, ya que el teorema sólo da condición necesaria. Por lo tanto, si

para algunos a se cumple la relación an - 1 º 1 mod n, entonces se dice que el número n es pseudoprimo con base a. Hay infinitos pares de números a y n, donde n es compuesto y pseudoprimo. En general, para cualquier a > 1, hay infinitos pseudoprimos basados en a. En general, las dos afirmaciones siguientes son ciertas. Si el par (2, n) satisface la comparación an-1 º 1 mod n, entonces el par de números (2, 2n - 1) también la satisface.

· Para cualquier número primo n y cualquier a > 2 tal que (a2 - 1, n) = 1, el número (a2n - 1)/(a2 - 1) es pseudoprimo con base a.

Definición. Los números compuestos n para los cuales la comparación an - 1 º 1 mod n es cierta en todas las bases se llaman números de Carmichael.

Dado el número n y el parámetro g = 1 para identificación

comprobar resultado.

1) se realiza una selección aleatoria de un número entero a del intervalo ;

2) utilizando el algoritmo euclidiano, se calcula el MCD para los números ayn;

3) si el mcd es mayor que 1, entonces se realiza el paso 7;

4) para el número a se comprueba la comparación an - 1 º 1 mod n;

5) si no se realiza la comparación, entonces se determina el parámetro g = 0 (número compuesto), vaya al paso 7.

6) si se completa la comparación, entonces se puede repetir la prueba;

7) mostrar el resultado de la verificación (g = 0 – un número compuesto).

Cuando se completa el algoritmo, son posibles las siguientes conclusiones:

· número n – compuesto (g = 0);

· si g = 1, entonces el número n es primo o compuesto y es un número de Carmichael.

Es apropiado señalar aquí que los números de Carmichael son bastante raros. Así que sólo hay 2.163 números de Carmichael que no superan los 25.000.000.000, y sólo 16 números que no superan los 100.000.

Diagrama algorítmico basado en el pequeño teorema de Fermat

Que no se dé número par pag. Necesitamos comprobar si el número p es primo.

1. Se selecciona un número aleatorio a, menor que p.

2. Si MCD (a, p) ¹ 1, entonces p es un número compuesto.

3. Se calcula la comparación L(a, p) º a(p - 1)/2 mod p.

4. Se calcula el símbolo de Jacobi J(a, p).

5. Si L(a, p) ¹ J(a, p), entonces p es un número compuesto.

6. Si L(a, p) = J(a, p), entonces la probabilidad de que

Número p: el compuesto no supera el 50%.

Si la prueba se repite k veces, entonces la probabilidad

el hecho de que p sea un número compuesto no supera 1/2k.

Prueba de Rabin-Miller

El fundamento del algoritmo Rabin-Miller puede ser

encontrar en . Aquí daremos sólo los más generales.

consideraciones. Se sabe que si el número p es primo, entonces

la ecuación x2 º 1 mod p tiene sólo dos soluciones: x º ±1

mod pág. Entonces, sea p un número entero impar que

Es necesario comprobar la simplicidad. Si p es primo, entonces por

Teorema de Fermat para cualquier número entero coprimo con

p se realiza la comparación am - 1º 1 mod p. Desde p - 1 –

es par, entonces obtenemos a(m - 1)/2 º ±1 mod p. si resulta

que (m - 1)/2 es par, entonces podemos repetir el razonamiento,

donde obtenemos que a(m - 1)/4 º ±1 mod p, etc.

Por lo tanto, para verificar la primalidad de los impares

número p, seleccione aleatoriamente el número a de

intervalo y calcular a t (mod p), a 2 t (mod p0, ..., a bt (mod p), donde t es impar y el número b = 2s. Si uno de estos números no coincide con +1 o -1, entonces podemos concluir que el número p es un número compuesto. Si los valores de los números coinciden con +1 o -1, entonces repetimos esta prueba k veces. Después de repetir esta prueba k veces, la probabilidad de que. el número compuesto p no será identificado no supera 1/. Después de las consideraciones anteriores, pasamos a la formulación del algoritmo de Rabin-Miller.

Esquema del algoritmo Rabin-Miller

Sea p un número impar. Necesitamos comprobar si el número p es primo. A continuación, supongamos que p - 1 = 2º.

1. Elija un número aleatorio a, menor que p y

definimos k = 0.

2. Usando el algoritmo euclidiano, calculamos el mcd de dos números a y p. Si MCD (a, p) ¹ 1, entonces p es un número compuesto.

3. Calcular bº en mod p. Si b = 1 o b = p - 1, entonces p probablemente sea primo.

4. Si b¹ 1 y b ¹ p - 1, entonces calcula b º b2 mod p y k= k + 1.

5. Si el número b = p - 1, entonces el número p probablemente sea primo.

Vaya al paso 7.

6. Mientras k< s выполнять пункт 4.

7. Completa el algoritmo.

Veamos ejemplos.

Ejemplo.

Sea p = 181. Tenemos p - 1 = 45 ´ 22. Por

Determinamos el valor de la descomposición presentada.

parámetro t = 45.

1. Elige un número aleatorio a = 52< p, и

definimos k = 0.

2. Usamos el algoritmo euclidiano para calcular.

MCD de dos números 52 y 181:

dividimos el número 181 por el número 52, obtenemos 181 = 52 ·

dividimos el número 52 por el número 25, obtenemos 52 = 25 2

dividimos el número 25 por el número 2, obtenemos 25 = 12 2 +

dividimos el número 2 por el número 1, obtenemos 2 = 1 · 2 + 0; encontramos que el mcd de dos números 181 y 52 es igual a 1.

Dado que MCD no nos permite determinar si el número 181 es compuesto, continuamos realizando el algoritmo de Rabin-Miller.

3. Calculamos secuencialmente

bº 52t mod 181 º 5245 mod 181:

522 mod 181º 2704 mod 181º 170 mod 181,

524 mod 181º 1702 mod 181º 28900 mod 181º

528 mod 181º 1212 mod 181º 14641 mod 181º

5216 mod 181º 1612 mod 181º 25921 mod 181º

5232 mod 181º 382` mod 181º 1444 mod 181º

5240 mod 181º (5232 mod 181)(528 mod 181)º

º (177 ´ 161) mod 181 º 28497 mod 181 º 80 mod

5241 mod 181º (5240 mod 181)(52 mod 181) º (80 ´

º 4160 mod 181 º 178 mod 181,

5245 mod 181º (5241 mod 181)(524 mod 181)º (178´

º 21538 mod 181 = 180 mod 181.

Entonces, tenemos b = 180 = p - 1. Se deduce que

el número p = 181 probablemente sea primo.

Comentario.

Para generar números primos incluso pequeños, los cálculos son bastante engorrosos. Por lo tanto para números reales, sin duda, controles similares

Los números para simplificar deben hacerse usando programas en una computadora.

Se dan algunas orientaciones sobre cómo generar números primos para aplicaciones prácticas. Esta guía se reduce a unos pocos pasos.

1. Genere un número aleatorio de n bits p.

2. Establezca los bits más y menos significativos en 1.

El bit más significativo en este caso garantiza la longitud requerida del número primo, y el bit menos significativo garantiza

su rareza.

3. Asegúrese de que el número p no sea divisible por los números primos pequeños 3, 5, 7, 11, etc.

La prueba de divisibilidad de todos los números primos menores que 2000 es fiable.

4. Realiza la prueba de Rabin-Miller para algún número aleatorio a. Si p pasa la prueba, genere otro número aleatorio a y repita la prueba. Para aplicaciones prácticas, basta con repetir la prueba de Rabin-Miller cinco veces.

5. Si p no pasa una de las pruebas, necesita generar otro número p y repetir

este manual nuevamente.

Otro número p, si resulta no ser primo, se puede obtener sin generar uno nuevo, sino pasando secuencialmente por todos los números enteros, comenzando por p + 1, p + 2, etc., hasta encontrar un número primo. .

Pasemos ahora a la cuestión de generar números primos grandes.

Construcción de números primos grandes y algoritmos deterministas para verificar números.

Sencillez/

Veamos otra forma de formar números primos. Este método se basa en un procedimiento específico para generar números primos, que se verifican mediante pruebas de primalidad.

Este enfoque se utiliza, por ejemplo, en la norma

electrónico firma digital(EDS) GOST R 34.10–94 y

se basa en el siguiente teorema.

Teorema 5.

Sea p = qN + 1, donde q es impar

número primo, N – número par y p< (2q + 1)2. Число p

es simple si se cumplen dos condiciones:

1) 2qN = 1 mod p;

2) 2N ≠ 1 mod pág.

La generación de un número primo utilizando el teorema 5 se lleva a cabo de una manera algo simplificada. estándar aceptado esquema Que sea requerido

formar un número primo p de longitud t ≥ 17 bits. Para ello se construye una secuencia decreciente de números (ti), donde i = 0, 1,…, s, para la cual t0 = t, ti = .

fórmulas pi - 1 = piN + 1, donde el número N satisface las siguientes condiciones:

· N – par;

· N – tal que la longitud del número pi - 1 = piN + 1 in

la precisión debe ser igual a ti - 1.

El estándar GOST proporciona un cierto algoritmo para calcular el número N. Para la versión educativa N -

un número par aleatorio obtenido usando un sensor números aleatorios(si N es impar, entonces N = N + 1).

El número pi - 1 se considera obtenido si se cumplen simultáneamente las dos condiciones siguientes:

1) 2b = 1 mod pi, b = pi - 1N;

2) 2N ≠ 1 mod pi.

Si no se cumple al menos una de las condiciones, entonces el valor del número N se incrementa en 2 y se calcula

el nuevo valor de pi es 1, cuya simplicidad se comprueba nuevamente bajo dos condiciones. Este proceso continúa hasta que se obtiene un número primo pi - 1 (es decir, se satisfacen las condiciones 1 y 2 del algoritmo de generación de números primos).

Tenga en cuenta que desde 2002, la norma nacional EDS mencionada anteriormente ha sido reemplazada por nuevo GOST R 34.10–2001.

Prueba de Miller-Rabin:

Entrada: n=2sr+1 – número impar, verificado por primalidad, s≥0, r – impar. t - número de iteraciones, parámetro de confiabilidad.

1. Repita los siguientes pasos t veces:

1.1. Seleccione aleatoriamente un (2,…, n-2);

1.2. Construya la secuencia b0, b1,…,bs, según la regla:

b0=ar mod n, bj=(bj-1)2 mod n, j=1,2,…,s.

1.3. Si no se encuentra en la secuencia construida

“1”, luego vaya a la Salida con el mensaje “n - composite”.

1.4. Si la primera unidad de la secuencia está precedida por no

“-1”, luego vaya a la Salida con el mensaje “ norte- compuesto".

2. Dirígete a la salida con el mensaje “ norte– primo con probabilidad ε t».

Prestemos atención al hecho de que en la secuencia b 0,b 1,…,bs cada término subsiguiente es el cuadrado del anterior módulo norte, y el último término no es más que un-1 modificación norte.

La probabilidad de un error de prueba en una iteración es ε≤φ( norte)/4norte, es decir, el límite superior del error en una iteración para la prueba de Miller-Rabin es 2 veces menor que el de la prueba de Solove-Strassen y 4 veces menor para la prueba de Fermat.

Ejemplo de uso de la prueba de Miller-Rabin:

norte=65=64+1=26+1. r=1, s=6. t=5.

1. 1.ª iteración:

1.1. a=8.

1.2. Hacemos la secuencia: b0=8, b1=64=-1, b2=1,

b3=1, b4=1, b5=1, b6=1.

1.3. Se encontró “1” en la secuencia.

1.4. La primera unidad está precedida por “-1”.

1. 2da iteración:

1.1. a=11.

1.2. Hacemos la secuencia: b0=11, b1=56, b2=16,

b3=61, b4=16, b5=61, b6=16.

1.3. No había ningún "1" en la secuencia.

Salida: " norte- un número compuesto."

Tareas para la sección 2

1) Implementar un procedimiento para generar números primos mediante un método de búsqueda aleatoria entre números de 128 bits, cuyo bit más significativo es 1, y verificar

a) prueba de Fermat

b) Prueba de Solovey-Strassen

c) Prueba de Miller-Rabin.

El número de iteraciones de la prueba probabilística debe ser tal que la probabilidad de error no supere 0,1. La probabilidad de error se determina con base en la estimación ε para la prueba. Establezca el número de iteraciones para la prueba de Fermat en 50.

2) Utilice este procedimiento para obtener 10 números primos. Para cada experimento, encuentre la cantidad de números probados hasta que se obtenga un primo. Presente los resultados en forma de tabla.

Aquí el número es el número del experimento, pag – número primo encontrado, norte – el número de números probados hasta obtener un primo.

Datos de autoevaluación para la sección 2

Los datos deben usarse de la siguiente manera:

· Establecer el valor del parámetro de confiabilidad de la prueba t=1.

· Sustituir como parámetro de entrada norte número de la columna "Números para verificar".

· Ejecute el programa con los parámetros de entrada dados varias (10-20) veces.

· Las conclusiones sobre la exactitud de la prueba realizada deben basarse en una comparación del resultado de la prueba con los datos de la tabla (columna “Resultado de la prueba”).

Tipo de número	Números para comprobar	Resultado de la prueba
numeros primos			Siempre "sencillo"




números de carmichael			Para la prueba de Fermat siempre es "simple", para las pruebas de Miller-Rabin y Solovey-Strassen: más a menudo "compuestas" que "simples"




Números compuestos, impares, no Carmichael			Más a menudo “compuesto” que “simple”

SECCIÓN 3. PRIMOS DEMOSTRABLES

En algunos casos es necesario construir demostrablemente simple números, es decir, números cuya sencillez ha sido comprobada. Para ello, existe una clase de pruebas de primalidad que pueden aceptar un número primo como número compuesto, pero no al revés.

El método para obtener números primos demostrables es diferente del método analizado anteriormente. No se utiliza ninguna búsqueda aleatoria para construir tales números. Usando una tabla de números primos tamaño pequeño, construido de antemano, el número se construye metro(igual al producto de varios números primos o al producto de números primos y un número aleatorio), entonces el número norte=2metro Se comprueba la simplicidad de +1 mediante una de las pruebas siguientes. La ventaja de este enfoque no es sólo obtener un número primo garantizado norte, pero también consiguiendo el elemento generador del grupo. z norte*. Por lo tanto, los números probablemente primos se utilizan normalmente como módulos de criptosistemas basados en el problema del logaritmo discreto, como el cifrado Shamir, el criptosistema El-Gamal y los estándares de firma digital asociados GOST R 34.11-94, GOST R 34.11-2001, DSA y ECDSA.

3.1. Prueba de primalidad de Miller

La prueba de Miller se basa en el teorema de Selfridge.

El algoritmo para construir un número primo mediante la prueba de Miller es el siguiente:

2. Se está construyendo el número metro=(donde qi son números primos aleatorios diferentes de la tabla, αi son números enteros aleatorios), cuyo tamaño es 1 bit menor que el tamaño requerido para un número primo;

3. Se calcula el valor norte=2metro+1;

4. Número construido norte probado por la prueba de Miller con parámetro dado fiabilidad. Si el resultado de la prueba es negativo, entonces debes volver al paso 2 y construir un nuevo número. metro.

Prueba de Miller:

Entrada: norte– número a comprobar, norte-1=https://pandia.ru/text/78/045/images/image051_14.gif" width="44" height="43">mod norte. Si alguno de los resultados no es igual a uno, luego vaya al paso 3, realice lo siguiente qi. Si todos los resultados son iguales a "1", vaya a Salir con el mensaje "probablemente norte- un número compuesto."

4. Dirígete a la salida con el mensaje “ norte- un número primo."

si el numero norte La simplicidad se verificó previamente mediante la prueba probabilística de Miller-Rabin, luego en la prueba de Miller es suficiente pasar por 4-6 valores aj.

Si norte es un número primo impar, entonces la probabilidad de que norte por base 1 seleccionada al azar < a< norte será probado en el paso 3.1, hay j(n-1)/(n-1).

3.2. prueba de pocklington

La prueba de Pocklington se basa en el teorema de Pocklington y permite comprobar la primacía de un número. norte, si la expansión canónica del número ( norte-1) se conoce sólo parcialmente.

Algoritmo para construir un número primo mediante la prueba de Pocklington próximo:

1. Construya una tabla de números primos pequeños. qi(o se utiliza una mesa ya preparada);

2..gif" width="104" height="32"> - descomposición canónica; t– parámetro de confiabilidad.

1. Seleccione t varios enteros aleatorios aj: 1< aj< norte.

2. Para todos aj calcular ( ajn-1 modo norte. Si alguno de los resultados no es igual a "1", vaya a Salir con el mensaje "n es un número compuesto".

3. Para cada uno i ejecutar:

3.1. Para cada qj calcular () mod norte. Si alguno de los resultados es igual a uno, vaya al paso 3, tome el siguiente i. Si todos los resultados no son iguales a "1", vaya a Salir con el mensaje " norte- un número primo."

4. Dirígete a la salida con el mensaje “probablemente norte- un número compuesto."

Si norte= RF+1 – número primo impar, F>https://pandia.ru/text/78/045/images/image055_12.gif" width="99" height="29">, MCD(R, F)=1 , entonces la probabilidad de que un 1 seleccionado al azar < a< norte satisfará las condiciones del teorema de Pocklington, hay https://pandia.ru/text/78/045/images/image057_10.gif" width="28" height="27 src=">-1<63.

norte- 1=4020=22·3·5·67. F=67, R=22·3·5=60.

Condiciones de control:

a= 2.

1) 24020 mod 4021=1.

2)24020/67 mod 4021 =260 mod 4021 =1452.

Salida: norte= 4021 es un número primo.

(Tenga en cuenta que la probabilidad de que un objeto seleccionado al azar a satisfará las condiciones del teorema de Pocklington para este ejemplo, es (1-1/67)≈0.985).

3.3. Procedimiento para generar números primos GOST R 34.10-94

El estándar nacional de firma digital GOST R34.10-94 recomienda un procedimiento para generar números primos demostrables de un tamaño determinado. GOST R 34.10-2001 también prescribe el uso de este procedimiento. Este procedimiento se basa en el teorema de Diemitko.

teorema de diemitko

Dejar norte= qr+ 1, donde q– número primo, R- incluso, R<4(q+1).

si hay a< norte: 1) un-1≡1(mód. norte); 2) 1(mod. norte), Eso norte– número primo.

Entonces, si tenemos un número primo q, entonces, pasando por números pares R, construir números norte= qr+ 1 y pruébelos para determinar su simplicidad según el teorema de Diemitko hasta que obtengamos un número primo. Usando el número resultante, puedes construir otro número primo, y así sucesivamente, hasta alcanzar el tamaño numérico requerido.

Aquí hay un algoritmo para pasar de un número primo más pequeño. q: |q|= a más pag: |pag|=t, utilizado en GOST. ξ que aparece en el procedimiento es una variable aleatoria distribuida uniformemente en (0,1), obtenida mediante un generador lineal congruente. Cada vez en el paso 1 se obtiene un nuevo valor de ξ.

Algoritmo para pasar de un número primo menor a uno mayor:

Entrada: t– dimensión requerida de un número primo, q– número primo: | q|=.

1..gif" ancho="15 altura=20" altura="20">1(mod pag), luego nos dirigimos a la Salida.

6. Calcular tu= tu+2. Volvamos al paso 3.

Salida: pag– número primo.

El primer término en la construcción del número N en el paso 1 proporciona el tamaño mínimo requerido del número. pag, y el segundo introduce el elemento necesario de aleatoriedad en el procedimiento de búsqueda de nuevos números primos.

La verificación en el paso 4 es necesaria para garantizar que el número pag no excedió su límite superior, y la verificación en el Paso 5 es una verificación de las condiciones del teorema de Diemitko para a=2.

Ejemplo

Entrada: t= 4, q= 3=2

1. N=0 " style="margin-left:-101.3pt;border-collapse:collapse;border:none">

Resultado de la prueba de probabilidad

Aquí № es el número del experimento, p es el número primo construido, en la tercera línea está el resultado de verificar el número construido con una prueba de probabilidad (+ o -), k es el número de números rechazados identificados como primos por el prueba de probabilidad.

El número de iteraciones de la prueba probabilística debe ser tal que la probabilidad de error no supere 0,1.

Datos de autoevaluación de la sección 3

Para pruebas de Miller y Pocklington

1) la prueba implementada debe verificarse con una tabla de números compuestos. Como parámetros de entrada de la prueba implementada se deben sustituir los números de la columna “Números a verificar” si como resultado la prueba muestra un mensaje de que este número es rechazado, entonces se debe ir a; siguiente etapa cheques. Si la prueba reconoce al menos uno de estos números como primo, la prueba se ejecuta con errores.

2) Entonces deberías utilizar las tablas según la prueba implementada. Para verificar estas tablas, debe sustituir los datos de las tablas como parámetros de entrada (para la prueba de Miller, el número primo que se está probando es pag y la expansión canónica del número ( pag-1), para la prueba de Pocklington: el número primo que se está probando pag, el número R y la expansión canónica del número F). Establecer el número de iteraciones de prueba. t=1. número de cheque pag esta prueba varias veces (30-100). Luego calcule la frecuencia del evento cuando el número primo que se está probando se acepta como un número compuesto y compare este valor con los datos de la columna "Probabilidad de error". Si estos datos son aproximadamente iguales al valor de frecuencia calculado, entonces la prueba se ha implementado correctamente.

Para el procedimiento de generación de números GOST 31.10-94

para comprobar trabajo de laboratorio debes establecer el parámetro ξ = 0 (es decir, eliminar la aleatoriedad). Luego deberías sustituir los datos de la tabla como parámetros de entrada ( q Y t). El resultado debe coincidir con el valor de la columna "Número construido".

Tabla de números compuestos