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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.