Implementación de algoritmos de teoría de números/No deterministas

En la práctica, los test de primalidad para números de un tamaño adecuado para aplicaciones criptográficas deben realizarse de forma probabilística. Tales algoritmos puede saber si un número dado es primo con una probabilidad extremadamente alta, pero no pueden proporcionar una cierta certeza de ello. Muchos de estos algoritmos funcionan con un número variable de rondas de test; cada ronda adicional de test hace que sea menos probable clasificar el número falsamente, por lo que el implementador puede elegir un número adecuado de rondas para proporcionar un equilibrio entre el nivel de certeza y el tiempo de ejecución del algoritmo.