Voltar

uCoder | 1227 | Nível: 5 | Tempo Limite: 4

RSA

Adaptado por Erich Rodrigues

Competição: SBC - ACM/ICPC - Maratona de Programação de 2014


O algoritmo RSA é um dos algoritmos de criptografia mais utilizados e é considerado uma das alternativas mais seguras existentes. Seu funcionamento básico é descrito a seguir.


Dois números primos ímpares p e q são escolhidos e calcula-se n = pq. A seguir é calculada a função totiente φ(n) = (p − 1)(q − 1) e um inteiro e satisfazendo 1 < e < φ(n) é escolhido de forma que mdc(φ(n), e) = 1. Finalmente é calculado o inteiro d, o inverso multiplicativo de e módulo φ(n), ou seja, o inteiro d satisfazendo de = 1 (mod φ(n)).


Assim obtemos a chave pública, formada pelo par de inteiros n e e, e a chave secreta, formada pelos inteiros n e d.


Para criptografar uma mensagem m, com 0 < m < n, calcula-se c = me (mod n), e c é a mensagem criptografada. Para descriptografá-la, ou seja, para recuperar a mensagem original, basta calcular m = cd (mod n). Note que, para isso, a chave secreta deve ser conhecida, não sendo suficiente o conhecimento da chave pública. Note ainda que a expressão x = 1 (mod y) usada acima equivale a dizer que y é o menor natural tal que o resto da divisão de x por y é 1.


Neste problema você deve escrever um programa para quebrar a criptografia RSA.


Entrada

A única linha da entrada contém três inteiros N , E, e C, onde 15 ≤ N ≤ 109 , 1 ≤ E < N e 1 ≤ C < N, de forma que N e E constituem a chave pública do algoritmo RSA descrita acima e C é uma mensagem criptografada com essa chave pública.


Saída

Seu programa deve produzir uma única linha, contendo um único inteiro M , 1 ≤ M < N , a mensagem original.


Exemplo de Entrada Exemplo de Saída

91 43 19

33

1073 71 436

726