En la teoría de números , un número primo demostrable es un número entero que se ha calculado como primo mediante un algoritmo de prueba de primalidad . Las técnicas de arranque que utilizan la prueba de primalidad de Pocklington son las formas más comunes de generar números primos comprobables para la criptografía. [1] [2] Contraste con el primo probable , que es probable (pero no seguro) que sea primo, según el resultado de una prueba de primalidad probabilística .
En principio, se puede demostrar que cada número primo es primo en tiempo polinomial mediante el uso de la prueba de primalidad AKS . Otros métodos que garantizan que su resultado sea primo, pero que no funcionan para todos los primos, son útiles para la generación aleatoria de primos demostrables. [3]
Ver también
Referencias
- ^ C. Couvreur y JJ Quisquater (1982), Introducción a la generación rápida de grandes números primos , Philips Journal of Research, 37 , págs. 231-264
- ^ Crandall, Richard; Pomerance, Carl (2005). Números primos: una perspectiva computacional . Saltador. págs. 174-178. ISBN 978-0387-25282-7.
- ^ Mollin, Richard A. (2002), RSA y criptografía de clave pública , Matemáticas discretas y sus aplicaciones, CRC Press, págs. 124-125, ISBN 9781420035247.