En efecto existen todo tipo de métodos pero en teoría de números computacional se emplean algoritmos probabilisticos deterministas, los cuales tienen un coste polinomial. Revisa: https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests

Concretamente te recomiendo que utilices Miller-Rabin, es el más utilizado por la comunidad criptógrafa. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test También tienes AKS, con el que he obtenido buenos resultados. https://en.wikipedia.org/wiki/AKS_primality_test En ambos enlaces encontrarás sus respectivos costes computacionales.

Si te interesa aprender la base consulta https://en.wikipedia.org/wiki/Fermat_primality_test
El test de primalidad de Fermat es el core de estos algoritmos, se basa en que un número es primo si a toda base coprima con p le corresponde el elemento identidad a través del índice totient(p). El problema de fermat son los números de Carmichael, ya que son módulos compuestos que pasan el test de Fermat, por lo que el test devuelve pseudoprimos o probable primes.

Saludos!

Me alegro de que lo pongas en práctica, es un tema muy apasionante. Miller-Rabin corre en tiempo polinomial, aunque lo que suelen recomendar es hacer varias rondas de Fermat y si el número parece primo pasarlo por Miller-Rabin. Otras implementaciones primero hacen trial division con una lista de primos considerables, lo pasan a Fermat y a Miller-Rabin, en fin, como más cómodo te sientas.

Ojo que si lo que buscas es hacer una criba de números primos, hay métodos más eficientes, lo único que necesitas una estructura auxiliar para ir guardando los números.

Saludos!

Sobre la exponenciación, te recomiendo que checkees https://en.wikipedia.org/wiki/Montgomery_modular_multiplication y si estás utilizando exponentiation by squaring mejor migra a éste. Revisa https://en.wikipedia.org/wiki/Modular_exponentiation también.

Sobre los witness en Fermat, bueno hay una regla que indica que la mitad de la clase de residuos son witnesses, por lo tanto testigos de que 'n' es compuesto, como ves hay una alta probabilidad de acierto a la hora de testear si n es compuesto (a no ser que sea un nº de carmichael), 5 en total estarían bien.

También tienes el Lehmann test, que particularmente me gusta mucho por su simpleza y eficacia, se centra en el teorema de Cauchy el cúal afirma que existen elementos dentro del grupo cuyo orden multiplicativo es un factor primo del orden del grupo, por lo tanto si cogemos varios elementos del grupo (bases) y las elevamos a (p-1)/2 y no obtenemos 1 congruente, entonces no satisface el teorema, pero cuidado, que hay algo llamado raíz primitiva, cuyo orden multiplicativo en el grupo es el propio orden en el grupo, pero sólo hay una cantidad de totient(totient(p)), por lo tanto un par de vueltas de este test son muy RECOMENDABLES.

Lehmann:

http://en.algoritmy.net/article/48610/Lehmann-test
https://en.wikipedia.org/wiki/Cauchy's_theorem_%28group_theory%29

Saludos!