Supongamos que π(x) es el número de números primos menor que x, entonces
? ≈x/ lnx
por ejemplo:
? El número de números primos representados por el binario de 64 bits es
(1? ) Teorema de Euler
? Al mencionar el teorema de Euler, primero debemos introducir la definición de la función de Euler:
¿La función de Euler Φ(n) es una función definida en números enteros positivos, Φ? (n) El valor de es igual al número de números que son primos relativos con n en la secuencia 0, 1, 2, 3,..., n-1
¿Propiedades de la función de Euler? :
? ( 1) Cuando m es un número primo, Φ(m)=m-1
? (2) Cuando m=pq, y p y q son ambos primos números, Φ(m)=Φ(p) Φ(q)=(p-1)(q-1)
? (3) Si m y n son primos entre sí, entonces Φ(m× n)=Φ(m)×Φ(n)
? (4) Si p es un número primo, entonces Φ(p^e)=p^e-p^(e-1)
? (5)
El contenido del teorema de Euler se puede ampliar a partir de la función de Euler:
Teorema de Euler:
¿Para dos cualesquiera relativamente? enteros primos a y n, hay
1(mod n)?
? Si n=p es un número primo, entonces
1(mod p) )
Obviamente el teorema de Euler puede verse como una forma generalizada del teorema de Fermat.
El teorema de Euler se puede utilizar para simplificar la operación modular de potencias
Por ejemplo:
¿Encontrar los últimos tres dígitos?
? Solución: ¿El resultado de (mod 1000)
? Hay (mod 1000)
(2) Teorema de Fermat
? Si p es un número primo, a es un entero positivo y mcd(a, p)=1, entonces
1(mod p)
? /p>
? Si p es un número primo y a es cualquier entero positivo, entonces para mcd(a, p)=1, tenemos
(mod p)
(3) Teorema de las dos subdetección
Si p es un número primo y 0lt;xlt;p, entonces la solución de la ecuación 1 (mod p) es x = -1, p-1.
Es decir, si es consistente con 1 (mod p), entonces es muy probable que p sea un número primo, pero aún no es seguro que p sea un número primo.
(1) Teorema de Wilson
? Para un entero positivo n dado, la condición necesaria y suficiente para juzgar que n es un número primo es -1 (mod n).
? Aunque es una condición necesaria y suficiente, y el teorema de Wilson tiene un alto medio teórico. Debido a que contiene factorial, requiere una gran cantidad de cálculos durante la detección y no es adecuado para la detección de números primos más grandes.
(2) Algoritmo de Miller-Rabin
? El algoritmo de Miller-Rabin es un algoritmo polinómico que puede garantizar la exactitud del resultado del juicio con una probabilidad cercana a 1.
? Miller-Rabin(n)
? Escribe n-1 como, donde m es un número impar
? /p >
? (mod n)
? Si (mod n)
Devuelve ('n es un número primo')
?
? Para i=0 a k-1
Si b≡-1(mod n)
Devuelve ('n es un número primo')
Else
b=b^2(mod n)
Fin
Fin
Retorno(' n es un número compuesto')
Descripción del algoritmo euclidiano:
? Los dos números enteros están representados por a y b, el negocio está representado por q y el resto está representado por r
? Paso1? Obtener Cuanto mayor es a y b, menor es b
? ¿Paso2? b)
? Paso3? El divisor original se cambia al dividendo y el resto se usa como divisor a=b, b=r
? =0, y regresa a b
Definición de inverso multiplicativo:
? Suponiendo que mcd(a, n)=1, entonces existe un número entero s tal que (mod n), es decir, s es el elemento inverso multiplicativo de a (mod n).
¿Acerca de ax by=d
? Supongamos que a y b son dos números enteros positivos (al menos uno es distinto de cero) y d=gcd(a, b). es un número entero xey hace que ax by=d sea verdadero. Si a y b son primos relativos, entonces hay números enteros xey tales que ax by=1 se cumple. En este momento, x en ax≡1 (mod b) puede ser válido. encontrar, que es el elemento inverso.
Algoritmo euclidiano extendido:
Construir dos secuencias:
Ejemplo:
Encontrar el inverso multiplicativo de 28mod75 (a=75, b=28)
? mcd(28, 75)=1 entonces hay una inversa
75=2×28 19
28=1×19 9
? 19=2×9 1
9=9×1 0? -8)×28=1?
? Entonces, el inverso multiplicativo de 28mod75 es -8
Versión completa del teorema del resto chino
Por ejemplo:
? Dado el siguiente conjunto de ecuaciones de congruencia, resuelve para x
? Paso uno: encuentra M
M=2×3×5×7=210
? El segundo paso: encontrar
? El tercer paso: encontrar
1(mod )(i=1, 2 , ...,k)
? Paso 4:
(mod M)
(105×1×1 70×1×2 42× 3× 3 30×4×5)(mod 210)
173(mod 210)