O chefe da polícia do Rio supervisiona várias patrulhas na cidade. Elas estão espalhadas e vigiam os pontos onde ocorre o tráfico de drogas. Regularmente, estas patrulhas têm que enviar um relatório sobre a movimentação das quadrilhas, sem que seja possível aos traficantes interceptar estas mensagens. Optou-se por entregar a cada patrulha um aparelho codificador de mensagens de texto, que é enviado por rádio para uma central que analisa estas informações. Para que não se corresse o risco de alguém enviar uma mensagem com a chave criptográfica errada, ficou decidido que cada aparelho teria a chave criptográfica escrita em baixo do aparelho. Isto assegura que se o policial esquecesse a “chave”, ele sempre poderia olhar em baixo do aparelho e usar a string correta. Para facilitar ainda mais o processo, ficou decidido que todos os aparelhos usariam a mesma chave criptográfica. Você foi contratado para escrever o software desta máquina, de tal forma que mesmo que uma dessas máquinas fosse interceptada pelos bandidos, eles não poderiam decifrar as mensagens enviadas para o chefe de polícia.

Quando ouviu sua incubência, você ficou estupefato!

- Mas o que me pedes, ó amado chefe, se afigura deveras difícil, quiçá impossível! Na primeira vez que os meliantes capturarem uma máquina dessas saberão todos nossos segredos!

Seu chefe, apiedado da sua ignorância de principiante, mas sabedor do grande potencial que você esconde, apesar das suas lamúrias, apenas disse, enigmaticamente:

- Estude a criptografia assimétrica, e suas dúvidas se desvanecerão como gotas de orvalho ao sol da manhã.

Depois de muito pensar, você pediu ajuda a um mestre de ciências ocultas que, por acaso, também era matemático. Este mestre consultando seu oráculo, deu a seguinte idéia:

- Escolha dois números primos. Eles não devem ser muito pequenos, mas para nossa demonstração, o 13 e o 17 servem. Pegue o número que seja o produto desses dois números primos, no caso, o número 221. Tire um de cada um dos primos iniciais, o que dá 12 x 16=192.

- Deveras intrigante, amado mestre.

- Tenha fé, jovem incréu!, gritou o mestre. Continue me acompanhando. Vamos representar este número 192 pela letra Y. Este número será muito importante na codificação. Pegue agora um número que não tenha divisor comum com Y, ou seja, este novo número e o Y serão primos entre si.

- Finalmente aquilo que aprendi na escola primária vai ter uma utilidade! Você exclamou exultante de alegria.

- Outro conhecimento útil da escola será a fatoração. Completou o mestre. Vamos fatorar 192. Isto dá 2x2x2x2x2x2x3. Basta agora escolher um número que não seja divisível nem por 2 nem por 3 (os fatores de 192). Escolhemos o 5. As suas chaves públicas serão 5 e 221. Este número 5 e o número inicial 221 serão aqueles que você vai escrever em baixo de cada aparelho. Jogue fora os números primos que você escolheu inicialmente. Agora vejamos como deverá ser seu algoritmo de criptografia. Pegue cada letra, ou seja, seu código ASCII, e eleve a 5 e guarde o resto da divisão deste resultado por 221.

Aqui está um exemplo:
Celacanto
67 101 108 97 99 97 110 116 111

agora convertemos:
67⁵ (mod 221)=84
101⁵ (mod 221)=186
108⁵ (mod 221)=75
97⁵ (mod 221)=54
99⁵ (mod 221)=216
97⁵ (mod 221)=54
110⁵ (mod 221)=145
116⁵ (mod 221)=12
111⁵ (mod 221)=76

84 186 75 54 216 54 145 12 76

Esta mensagem é enviada.

Para decodificar, vamos olhar qual seria a chave para descriptografar. Repartimos do número Y. A chave de decodificação é o número cujo produto pelo primeiro número publicado (5) tem como resto 1 na divisão por Y (192). No nosso caso, este número é o 77 (5*77= 385= 2x192+1).

Vamos usar este número para decodificar.

84⁷⁷ (mod 221)=67=C
186⁷⁷ (mod 221)=101=e
75⁷⁷ (mod 221)=108=l
54⁷⁷ (mod 221)=97=a
216⁷⁷ (mod 221)=99=c
54⁷⁷ (mod 221)=97=a
145⁷⁷ (mod 221)=110=n
12⁷⁷ (mod 221)=116=t
76⁷⁷ (mod 221)=111=o

- Voilá! A coisa funciona! Você exclama admirado, depois de ver que conseguimos com simples contas recuperar a mensagem original.

Depois de pensar um pouco, você vê uma pequena dificuldade. Como usuário de sistemas operacionais avançados, você usa Linux e na linha de comando com a supercalculadora bc você descobre que 216 elevado a 77 (basta chamar bc na linha de comando e digitar 216^77) é igual a
566.159.551.582.825.161.743.621.404.474.404.760.031.142.448.407.527.580.
407.064.693.864.409.775.046.008.707.686.153.584.777.361.889.405.985.989.
370.510.938.768.427.806.052.676.828.062.427.197.896.352.669.811.974.404.
740.004.068.150.214.656,
ou seja, uns 566 “zilhões”. Seu pobre compilador C só consegue fazer contas com inteiros até uns 4 bilhões…

- Amado mestre, como poderei eu, com um reles compilador C, calcular números tão assombrosamente grandes?

- A resposta, jovem ignaro, está na aritmética de relógio, na fatoração e em um pouco de imaginação. Com estes recursos, toda essa conta se resolve em poucas linhas de código C.

Para resolver este nó górdio, vamos usar a aritmética modular. A aritmética modular tem a propriedade distributiva na multiplicação. Assim, se 77 for decomposto em seus bits: 77=100 1101= 2⁶ + 2³ + 2² + 2⁰= 64 + 8 + 4 + 1.

Ou seja, 216⁷⁷(mod 221)= (216⁶⁴x216⁸x216⁴x216¹)(mod 221) usando a propriedade distributiva, temos:
216⁷⁷(mod 221)= [(216⁶⁴ (mod 221))x(216⁸(mod 221))x(216⁴(mod 221))x(216¹(mod 221))] (mod 221)
ora, agora tudo ficou mais fácil:

216⁴(mod 221)= [(216²(mod 221))x(216²(mod 221))](mod 221)
= (25×25)(mod 221)
= 183

216⁸(mod 221)=[(216⁴(mod 221))²](mod 221)
=183²(mod 221)
= 118

Não é necessário aqui, mas para mostrar que a definição usa os resultados anteriores, vamos calcular 216¹⁶(mod 221) e 216³²(mod 221)

216¹⁶(mod 221)= [(216⁸(mod 221))²](mod 221)
= 118²(mod 221)
=1

216³²(mod 221)= [(216¹⁶(mod 221))²](mod 221)
=1²(mod 221)
=1

216⁶⁴(mod 221)= [(216³²(mod 221))^2](mod 221)
=1²(mod 221)
=1

ou seja,

216⁷⁷(mod 221)= 1x118x183x216(mod 221)
=4664304(mod 221)
=99

De posse desses conhecimentos inestimáveis, faça um programa que receba um texto ASCII de várias linhas e converta-o usando a criptografia descrita acima. Note que as operações sobre os números inteiros podem ser simplificadas com um simples for ou função que calcule a módulo de determinada conta sem mesmo saber o resultado final da exponenciação. A nota do trabalho é individual e levará em conta também uma apresentação pessoal e oral do programa, quando serão formuladas perguntas acerca da solução apresentada.