| dbo:abstract
|
- En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto. Por ejemplo, tómese n = 71. Entonces, n − 1 = 70 = (2)(5)(7).Tómese ahora a = 11. En primer lugar: Esto no demuestra que el orden multiplicativo de 11 mod 71 es 70, porque algún factor de 70 aún podría funcionar arriba. Verificamos entonces 70 dividido por sus factores primos: Entonces, el orden multiplicativo de 11 mod 71 es 70 y de esta manera, 71 es primo. Para realizar estas debería usarse el método acelerado de exponenciación binaria. Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos. Si a también pasa el 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, implicando que n es primo. Recíprocamente, si n es primo, entonces existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo. (es)
- En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto. Por ejemplo, tómese n = 71. Entonces, n − 1 = 70 = (2)(5)(7).Tómese ahora a = 11. En primer lugar: Esto no demuestra que el orden multiplicativo de 11 mod 71 es 70, porque algún factor de 70 aún podría funcionar arriba. Verificamos entonces 70 dividido por sus factores primos: Entonces, el orden multiplicativo de 11 mod 71 es 70 y de esta manera, 71 es primo. Para realizar estas debería usarse el método acelerado de exponenciación binaria. Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos. Si a también pasa el 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, implicando que n es primo. Recíprocamente, si n es primo, entonces existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo. (es)
|
| rdfs:comment
|
- En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto. Por ejemplo, tómese n = 71. Entonces, n − 1 = 70 = (2)(5)(7).Tómese ahora a = 11. En primer lugar: Entonces, el orden multiplicativo de 11 mod 71 es 70 y de esta manera, 71 es primo. (es)
- En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto. Por ejemplo, tómese n = 71. Entonces, n − 1 = 70 = (2)(5)(7).Tómese ahora a = 11. En primer lugar: Entonces, el orden multiplicativo de 11 mod 71 es 70 y de esta manera, 71 es primo. (es)
|
