El test de primalidad es bueno para comenzar se necesitan algunas operaciones de exponenciacion modular y solo necesitas comprobar que los resultados ahi expuestos sean 1 con 4-5 numeros distintos.
https://en.m.wikipedia.org/wiki/Primality_test#Probabilistic_tests
https://en.m.wikipedia.org/wiki/Primality_test#Probabilistic_tests