## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1716

# RSA

By Vinícius "Cabessa" Fernandes dos Santos Brazil

Timelimit: 1

RSA is one of the most used cryptographic algorithms and it is considered to be one of the most secure existing alternatives. Its basic operation is described below.

Two odd prime numbers P and Q are chosen and N = PQ is computed. Then the totient function φ(N) = (P − 1)(Q − 1) is computed and an integer e satisfying 1 < E < φ(N) is chosen so that gcd(φ(N), E) = 1. Finally the integer D, the inverse multiplicative of e module φ(N) is computed, that is, the integer D satisfying DE ≡ 1 mod φ(N).

In that way we obtain the public key, which consists of the pair of integers N and E, and the secret key, containing the integers N and D.

To encrypt a message M, with 0 < M < N, we calculate C = Me mod N, and C is the encrypted message. To decrypt the message, that is, to recover the original message, it suffices to compute M = Cd mod N. Note that, in order to do that, the secret key must be known; knowing the public key is not enough to decrypt the message.

## Input

The input contains several test cases. A test case consists of one line, which contains three integers N, E, and C, where 15 ≤ N ≤ 109 , 1 ≤ E < N and 1 ≤ C < N , such that N and E constitute the RSA public key described above, and C is a message encrypted with that public key.

## Output

For each test case in the input your program must produce a single line, containing a single integer M , 1M < N , the original message.

 Sample Input Sample Output 1073 71 436 726

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define true 1
#define false 0

typedef long long ll;

int _phi(int);
int inv_mod(int, int);
ll fast_exp(ll, ll, ll);
void euclid_ext(int, int);

int x, y, d;

int main(int argc, char **argv)
{

int n, e, c, phi;

scanf("%d %d %d", &n, &e, &c);
phi = _phi(n);

int d = inv_mod(e, phi);
printf("%lld\n", fast_exp(c, d, n));

return 0;

}

int _phi(int n)
{

int result = n;
for (int i = 2; i * i  < = n; i++)
{

if(n % i == 0)
{

while(n % i == 0)
n /= i;

result -= result / i;

}
}

if(n > 1)
result -= result / n;

return result;

}

ll fast_exp(ll p, ll q, ll m)
{

ll r = 1;
while (q)
{

if (q & 1)
r = (r * p) % m;

p = (p * p) % m;
q >>= 1;

}

return r;

}

void euclid_ext(int a, int b)
{

if (!b)
{

x = 1;
y = 0;
d = a;

return;

}

euclid_ext(b, a % b);

int x1 = y, y1 = x - (a / b) * y;
x = x1, y = y1;

}

int inv_mod(int a, int m)
{

euclid_ext(a, m);
return (x % m + m) % m;

}
``````
Copy The Code &

Input

cmd
1073 71 436

Output

cmd
726

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cmath>
#include <cstdio>
typedef long long ll;
ll fast_expo(ll x, ll y, ll z) {
if (y == 0) return 1LL;
if (y == 1) return x % z;
if (y % 2 == 0) {
ll temp = fast_expo(x, y / 2, z);
return (temp * temp) % z;
}
return (x * fast_expo(x, y - 1, z)) % z;
}
ll phi(ll val) {
double result = val;
for (ll p = 2; p * p  < = val; p++) {
if (val % p == 0) {
while (val % p == 0) val /= p;
result *= (1.0 - (1.0 / (double)p));
}
}
if (val > 1) result *= (1.0 - (1.0 / (double)val));
return (ll)result;
}
ll inv(ll val, ll mod) { return fast_expo(val, phi(mod) - 1, mod); }
int main() {
ll n, e, c;
scanf("%lld %lld %lld", &n, &e, &c);
ll exibir = fast_expo(c, inv(e, phi(n)), n);
printf("%lld\n", exibir);
return 0;
}

``````
Copy The Code &

Input

cmd
1073 71 436

Output

cmd
726