Para poder determinar la primalidad de números cada vez más grandes (de miles de cifras) se buscan aquellos algoritmos cuyo tiempo de ejecución crezca lo más lentamente posible, a ser posible, que se pueda expresar como un polinomio.