Problem #PRU-5009

Problems Cryptography Number theory

Problem

After mastering the Caesar shift cypher one may wonder how to generalize it. One possible way is to use Affine cypher. The difference between these two methods can be described as follows:

  • In case of Caesar cypher we took a letter with position n from 1 to 26 and added to its position a number d obtaining the number n+d, then we compute its residue modulo 26.

  • In case of affine cypher we take a letter with position n and consider a number nx+d modulo 26.

To decipher such code we need to know values x and d, then if we have a letter in the code with position m, we can find n as n=(md)x1 modulo 26. Here we have to explain what is x1: for a number x<26 we are looking for such a number y, that 26 divides xy1.

  • Does there always exist a number x1 modulo 26 for any x?

  • Using data x=3, d=8 encrypt the word "SOLUTION".