Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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

Let $f(x) = ax + b$ be an affine encryption function. $a$ and the cardinal of the field of our keys $K$ (in English, 26) must be coprime so that the encryption function is bijective and the decryption function defined and bijective as well.

Could you please clarify how (in terms of congruences) the two having a $pgcd>1$ make the encryption function not bijective?

share|improve this question

Let $n$ be the modulus and $d = \gcd(a,n)$. Then, $ax \mod n$ will be a multiple of $d$. If $d > 1$, this implies that there is no $x$ such that $ax \equiv 1 \pmod n$, and so there is no $x$ such that $f(x) = ax+b \equiv b+1 \pmod n$. So $f$ is not a bijection since it is not surjective.

P.S.: I am not certain how you got the idea of using the word "field" instead of "set", but you should refrain from using it until you have learned what a field is.

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.