Quimioluminiscencia
Quimioluminiscencia es la emisión de luz como resultado de una reacción química. También puede haber una emisión limitada de calor. Dados los reactivos A... (leer más)
En teoría computacional de números, la prueba de Lucas es una prueba de primalidad para un número natural n; requiere que los factores primos de n − 1 ya se conozcan. Es la base del certificado Pratt que proporciona una verificación concisa de que n es primo.
Sea n un número entero positivo. Si existe un número entero a, 1 < a < n, tal que
y para cada factor primo q de n − 1
entonces n es primo. Si no existe tal número a, entonces n es 1, 2 o compuesto.
La razón de la exactitud de esta afirmación es la siguiente: si la primera equivalencia es válida para a, podemos deducir que a y n > son coprimos. Si a también sobrevive al segundo paso, entonces el orden de a en el grupo (Z/nZ)* es igual a n−1, lo que significa que el orden de ese grupo es n−1 (porque el orden de cada elemento de un grupo divide el orden del grupo), lo que implica que n es primo. Por el contrario, si n es primo, entonces existe una raíz primitiva módulo n, o generador del grupo (Z/nZ )*. Un generador de este tipo tiene orden |(Z/nZ)*| = n−1 y ambas equivalencias se cumplirán para cualquier raíz primitiva de este tipo.
Tenga en cuenta que si existe un a < n tal que la primera equivalencia falla, a se llama testigo de Fermat de la composición de n.
Por ejemplo, toma n = 71. Entonces n − 1 = 70 y los factores primos de 70 son 2, 5 y 7. Seleccionamos aleatoriamente un a=17 < n. Ahora calculamos:
Para todos los números enteros a se sabe que
Por lo tanto, el orden multiplicativo de 17 (mod 71) no es necesariamente 70 porque algún factor de 70 también puede funcionar arriba. Entonces revisa 70 dividido por sus factores primos:
Desafortunadamente, obtenemos que 1710≡1 (mod 71). Entonces todavía no sabemos si 71 es primo o no.
Probamos con otro a aleatorio, esta vez eligiendo a = 11. Ahora calculamos:
Nuevamente, esto no muestra que el orden multiplicativo de 11 (mod 71) sea 70 porque algún factor de 70 también puede funcionar. Entonces revisa 70 dividido por sus factores primos:
Entonces el orden multiplicativo de 11 (mod 71) es 70 y, por lo tanto, 71 es primo.
(Para llevar a cabo estas exponenciaciones modulares, se podría utilizar un algoritmo de exponenciación rápida como la exponenciación binaria o de cadena de suma).
El algoritmo se puede escribir en pseudocódigo de la siguiente manera:
algoritmo lucas_primality_test es entrada: n > 2, un número extraño para ser probado para la primalidad. k, un parámetro que determina la exactitud de la prueba. Producto: primo si n es primo, de lo contrario composite o posiblemente compuesto. determinar los principales factores n−1. LOOP1: repetición k veces: Elige. a al azar en el rango [2, n − 1 si a n − − 1 ≢ 1 () mod n ) {displaystyle a^{n-1}not equiv 1{pmodn}} entonces retorno composite más # a n − − 1 ↑ ↑ 1 () mod n ) {displaystyle color {Gray}{n-1}equiv 1{pmod {n}}} LOOP2: para todos los factores principales q de n−1 si a n − − 1 q ≢ 1 () mod n ) {displaystyle a^{frac {n-1}not equiv 1{pmod {n}}} entonces si comprobamos esta igualdad para todos los factores principales n−1 entonces retorno primo más continuar LOOP2 más # a n − − 1 q ↑ ↑ 1 () mod n ) {displaystyle color {Gray}{frac} {n-1}{q}equiv} 1{pmod {n}}} continuar LOOP1 retorno posiblemente compuesto.
Quimioluminiscencia es la emisión de luz como resultado de una reacción química. También puede haber una emisión limitada de calor. Dados los reactivos A... (leer más)
El sesgo de uso de codones se refiere a las diferencias en la frecuencia de aparición de codones sinónimos en el ADN codificante. Un codón es una serie de... (leer más)
Astra es la marca de una serie de satélites de comunicación geoestacionarios, tanto individualmente como en grupo, que son propiedad y están operados por... (leer más)