洛谷5451 [THUPC2018]密码学第三次小作业

Luogu

LOJ

分析

一道不错的数论题。

因为 $e_1\perp e_2$ ,所以会存在一对数 $s,t$ ,满足 $e_1s+e_2t=1$ 。

我们要求的是 $m\bmod N$ 。我们可以对这个式子做一些变形:

$$ \displaystyle \begin{aligned} m\bmod N=&m^{e_1s+e_2t}\bmod N\\ =&m^{e_1s}m^{e_2t}\bmod N\\ =&{c_1}^s{c_2}^t\bmod N \end{aligned} $$

于是只要求出 $s$ 和 $t$ 即可。因为 $e_1s+e_2t=1$ ,所以可以直接 exgcd 求出 $s$ 和 $t$ 。

然而这里求出的 $s$ 和 $t$ 一正一负,为了方便我们假设 $s$ 是负数。

根据常规方法,有 ${c_1}^{-|s|}\bmod N={c_1}^{\varphi(N)-|s|}\bmod N$ ,然而求 $\varphi(N)$ 的复杂度过大,所以这样是不行的。

根据小学奥数可以得到 ${c_1}^{-|s|}\bmod N=\left(c_1^{-1}\right)^{|s|}\bmod N$ ,于是我们只要求出 $c_1^{-1}$ 即可。

设 $d=c_1^{-1}\bmod N$ ,可以得到 $c_1d+kN=1$ 。那么直接 exgcd 求出 $d$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int c1,c2,e1,e2,mod;

inline int exgcd(int a,int b,int& x,int& y) {
    if (!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,x,y);
    int z=x; x=y,y=z-y*(a/b);
    return d;
}

inline int mul(int a,int b) {
    int d=(int)((long double)a/mod*b+0.5);
    return (a*b-d*mod+mod)%mod;
}

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=mul(a,a)) if (b&1) c=mul(a,c);
    return c;
}

signed main() {
    int T=read();
    while (T--) {
        c1=read(),c2=read(),e1=read(),e2=read(),mod=read();
        int s,t; exgcd(e1,e2,s,t);
        while (t<0) t+=e1,s-=e2;
        int d,tmp; exgcd(c1,mod,d,tmp);
        printf("%lld\n",mul(qpow(d,-s),qpow(c2,t)));
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 24 PM

发表评论