Criptografia é uma área da Ciência da Computação que estuda os métodos de comunicação secreta que transformam uma mensagem (plaintext) em uma mensagem cifrada (ciphertext), de forma que apenas o real receptor da mensagem seja capaz de restaurar o seu conteúdo original. O ato de transformar uma mensagem em uma mensagem cifrada é chamado de encriptação e o ato contrário é chamado de decriptação. Um método bastante simples de encriptação é o método Twist, que requer que ambos remetente e receptor combinem uma chave secreta k, que deve ser um inteiro positivo.

O método Twist utiliza quatro vetores: plaintext, ciphertext, plaincode e ciphecode; sendo plaintext e ciphertext vetores de caracteres e plaincode e ciphercode vetores de inteiros. Todos os vetores são de tamanho n, onde n é o tamanho da mensagem a ser encriptada. Os vetores são iniciados na posição zero, de forma que os seus elementos são numerados de 0 a n-1. Para este problema, as mensagens apenas conterão letras minúsculas, pontos e underscores (representando espaços).

A mensagem a ser encriptada é armazenada no vetor plaintext. Dada a chave k, a encriptação é feita da seguinte forma. Primeiro, as letras em plaintext são convertidas em códigos inteiros que são armazenados em plaincode. A conversão é feita da seguinte forma: ‘_’ = 0, ‘a’ = 1, ‘b’ = 2, ..., ‘z’ = 26 e ‘.’ = 27. Depois, cada código em plaincode é convertido em um código encriptado em ciphercode através da seguinte fórmula: para todo i de 0 a n-1,

ciphercode[i] = (plaincode[(k*i) mod n] - i) mod 28.

(Aqui x mod y é o resto positivo da divisão de x por y. Por exemplo, 3 mod 7 = 3, 22 mod 8 = 6 e -1 mod 28 = 27. Você pode usar o operador ‘%’ do C, desde que você some y caso o resultado seja negativo.) Por último, os códigos obtidos em ciphercode são convertidos novamente em letras (pela mesma regra descrita anteriormente) e são armazenadas em ciphertext.

O arquivo DECRYPT.IN conterá uma ou mais instâncias do problema, seguidas por uma linha contendo somente o número 0. Cada instância estará contida em uma linha do arquivo e consistirá de uma chave k, um espaço e a mensagem cifrada com tamanho n entre 1 e 70 caracteres. A chave k será um inteiro positivo menor ou igual a 300 tal que mdc(k, n) = 1.

11 cbmowxbkg

5 edrykonnklupposembjnugujqwki

29 edcnkjyzmjrpianvbyzo

0

Para cada instância do arquivo de entrada, o arquivo DECRYPT.OUT deve conter uma linha contendo a mensagem original.

cachorro.

este_e_um_teste_muito_chato.

espero_que_funcione.