Despite the fact primality test is a mathematical issue, it plays a part on the security of many cryptosystems such as RSA. I was trying to understand how it works until I came to the following congruency:

〖(X+a)〗^p≡X^p+a (mod X^r-1,p)

The above reduces evaluating the initial congruency 〖(X+a)〗^p≡X^p+a (mod p) to have less coefficient. How do we evaluate the above one?


1 Answer 1


This is never "evaluated" as such. The above equation must hold for the number to be prime for certain $a$, or else it's composite.

See the algorithm on Wikipedia to exactly see for which $a$ the equation is tested.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.