PKU 2447 - RSA (欧几里得扩展 + 大合数分解)
题意
有几个数之间的关系。
P、Q是两个质数。$T = (P-1) (Q-1), N = P Q$
E是一个和T互质的数。
D是一个数，这个数符合$(E * D) \bmod T = {1}$
题目给出C, E, N，要求求出$M = C^{D} \bmod N
思路
通过N，分解出P、Q。
然后就可以得到T
因为知道E和T，根据D的那条式子化简得$ED + T*(-k) = 1$
求欧几里得扩展$ED + T*(-k) = gcd(E, T) = 1$
所以求出来得解正好是方程的解。
求出D之后用快速幂取模就能得出答案。
代码
set<LL> fac;
inline LL FixMod(LL a, LL mod)
{
while (a < 0) a += mod;
while (a >= mod) a -= mod;
return a;
}
LL multi(LL a, LL b, LL m)
{
LL ans = 0;
a %= m;
while(b)
{
if(b & 1)
{
ans = FixMod(ans + a, m);
b--;
}
b >>= 1;
a = FixMod((a<<1), m);
}
return ans;
}
LL quick_mod(LL a, LL b, LL m)
{
LL ans = 1;
a %= m;
while(b)
{
if(b & 1)
{
ans = multi(ans, a, m);
b--;
}
b >>= 1;
a = multi(a, a, m);
}
return ans;
}
bool Miller_Rabin(LL n)
{
if(n == 2) return true;
if(n < 2 || !(n & 1)) return false;
LL m = n - 1;
int k = 0;
while((m & 1) == 0)
{
k++;
m >>= 1;
}
for(int i=0; i<10; i++)
{
LL a = rand() % (n - 1) + 1;
LL x = quick_mod(a, m, n);
LL y = 0;
for(int j=0; j<k; j++)
{
y = multi(x, x, n);
if(y == 1 && x != 1 && x != n - 1) return false;
x = y;
}
if(y != 1) return false;
}
return true;
}
LL pollard_rho(LL n, LL c)
{
LL i = 1, k = 2;
LL x = rand() % (n - 1) + 1;
LL y = x;
while(true)
{
i++;
x = (multi(x, x, n) + c) % n;
LL d = __gcd((y - x + n) % n, n);
if(1 < d && d < n) return d;
if(y == x) return n;
if(i == k)
{
y = x;
k <<= 1;
}
}
}
bool Find(LL n, int c) //如果是素数返回false
{
if(n == 1) return false;
if(Miller_Rabin(n))
{
fac.insert(n);
return false;
}
LL p = n;
LL k = c;
while(p >= n) p = pollard_rho(p, c--);
Find(p, k);
Find(n / p, k);
return true;
}
void GCD_Ext(LL a, LL b, LL &d, LL &x, LL &y)
{
if (!b) d = a, x = 1, y = 0;
else
{
GCD_Ext(b, a % b, d, y, x);
y -= x * (a / b);
}
}
int main()
{
LL C, E, N;
while (~scanf("%lld%lld%lld", &C, &E, &N))
{
fac.clear();
Find(N, 120);
LL p = *fac.begin(), q = *(++fac.begin());
LL N = p * q, T = (p-1) * (q-1);
LL d, x, y;
GCD_Ext(E, T, d, x, y);
x = (x % T + T) % T;
printf("%lld\n", quick_mod(C, x, N));
}
return 0;
}