Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1716
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/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.
In this problem your task is to break the RSA cryptography.
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 , 1 ≤ M < 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;
}
Input
Output
#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;
}
Input
Output