Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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