Ural 1141. RSA Attack 扩展欧几里得算法

1141. RSA Attack

Time limit: 1.0 second
Memory limit: 64 MB

The RSA problem is the following: given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e, (p-1)*(q-1)) = 1, and an integer c, find an integer m such that m e = c (mod n).

Input

One number K (K <= 2000) in the first line is an amount of tests. Each next line represents separate test, which contains three positive integer numbers – e, n and c (e, n, c <= 32000, n = p*q, p, q – distinct odd primes, gcd(e, (p-1)*(q-1)) = 1, e < (p-1)*(q-1) ).

Output

For each input test the program must find the encrypted integer m.

Sample

input	output
3 9 187 129 11 221 56 7 391 204	7 23 17

Problem Author: Michael Medvedev

RSA加密算法

第一步，随机选择两个不相等的质数p和q。
第二步，计算p和q的乘积n。
第三步，计算n的欧拉函数φ(n)。
第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
第五步，计算e对于φ(n)的模反元素d。
第六步，将n和e封装成公钥，n和d封装成私钥。

来自链接： http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

题意：美国RSA实验室，以研究加密算法而著名。
RSA问题是这样的：给定一个正整数n，它是两个不同的奇质数p，q的乘积；还有一个正整数e，关系：gcd(e, (p-1)*(q-1)) = 1,另外有一个整数c。请找整数m，令到 m^e = c (mod n) 。

拓展欧几里得定理求解ax + by = gcd(a,b)

int ext_gcd(int a, int b, int &x, int &y)
{
	int tmp, ret;
	if(!b)
	{
		x = 1;
		y = 0;
		return a;
	}
	ret = ext_gcd(b, a % b, x, y);
	tmp = x;
	x = y;
	y = tmp - (a / b) * y;
	return ret;
}

#include<stdio.h>
char sv[35000];
int prime[8000];
void sieve(int N)//素数筛
{
    int i,j,count;
    for(i=4; i<=N; i+=2)
        sv[i] = 1;
    prime[0] = 2;
    count = 1;
    for(i=3; i<N; i+=2)
    {
        if(!sv[i])
        {
            prime[count++] = i;
            for(j=i*i; j<N; j+=2*i)
                sv[j] = 1;
        }
    }
    return;
}
int ex_gcd(int a, int b, int &x, int &y)//拓展欧几里得
{
    if (a%b==0)
    {
        x = 0;
        y = 1;
        return b;
    }
    int newx, newy;
    int ret = ex_gcd(b, a % b, newx, newy);
    x = newy;
    y = newx-newy*(a / b);
    return ret;
}
int bigmod(int a,int b,int n)//a^b(mod n)
{
    if(b==0) return 1;
    if(b==1) return a;
    int x = bigmod(a,b/2,n);
    if(b%2)
    {
        return (((x*a)%n)*x)%n;
    }
    else
        return (x*x)%n;
}
int main()
{
    int eg,T,x,y,e,n,c,k,i,q,p,ans;
    sieve(32000);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&e,&n,&c);
        for(i=0;; i++)
        {
            if(n%prime[i])
                continue;
            k = n/prime[i];
            if(!sv[k])
            {
                q = k;
                p = prime[i];
                break;
            }
        }
        eg = ex_gcd(e,(p-1)*(q-1),x,y);
        if(x<0) x+= (p-1)*(q-1);
        ans = bigmod(c,x,n);
        printf("%d\n",ans);
    }
    return 0;
}