POJ 2447 RSA
1550 ワード
pollardをテストしましたrhoの中のそのランダムなgcc、時間の差は200+ms近くあります
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#define oo (1<<28)
#define gcc 121232
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
LL ext_gcd(LL a,LL b,LL &x,LL &y)
{
if(!b){
x=1;y=0;return a;
}
LL d=ext_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
LL Mul(LL a,LL b,LL m)
{
LL r=0;
while(b)
{
if(b&1) r=(r+a)%m;
a=(a<<1)%m;
b>>=1;
}
return r;
}
LL power(LL a,LL b,LL m)
{
LL r=1;
while(b)
{
if(b&1) r=Mul(r,a,m);
a=Mul(a,a,m);
b>>=1;
}
return r;
}
LL pollard_rho(LL n)
{
LL x,y,d,i=1,k=2;
x=rand()%(n-1)+1;
y=x;
while(true)
{
++i;
x=((Mul(x,x,n)-gcc)%n+n)%n;
d=gcd(y-x+n,n);
if(d>1&&d<n) return d;
if(x==y) return n;
if(i==k)
y=x,k<<=1;
}
}
int main()
{
LL c,e,n;
while(~scanf("%I64d%I64d%I64d",&c,&e,&n))/// n 2 , pollard_rho
{
LL p=pollard_rho(n),q=n/p;
LL t=(p-1)*(q-1);
LL x,d;
ext_gcd(e,t,d,x);/// e t
d=(d%t+t)%t;
printf("%I64d
",power(c,d,n));
}
return 0;
}