【日常学习】【数学】【矩阵乘法】【大数乘方取模】codevs1982 加密算法题解

阳光穿透心脏的1/2处 2022-08-09 17:40 170阅读 0赞

题目描述 Description

Rivest是密码学专家。近日他正在研究一种数列E=\{E\[1\],E\[2\],……,E\[n\]\}，  
且E\[1\]=E\[2\]=p（p为一个质数），E\[i\]=E\[i-2\]\*E\[i-1\] （若2<i<=n）。  
例如\{2,2,4,8,32,256,8192,……\}就是p=2的数列。在此基础上他又设计了一种加密  
算法，该算法可以通过一个密钥q (q<p)将一个正整数n加密成另外一个正整数d，计  
算公式为：d=E\[n\] mod q。现在Rivest想对一组数据进行加密，但他对程序设计不太  
感兴趣，请你帮助他设计一个数据加密程序。

输入描述 Input Description

读入m，p。其中m表示数据个数，p用来生成数列E。  
以下有m行，每行有2个整数n，q。n为待加密数据，q为密钥。  
规模：0<p,n<2^31；0<q<p；0<m<=5000。

输出描述 Output Description

将加密后的数据按顺序输出到文件a.out。  
第i行输出第i个加密后的数据。

样例输入 Sample Input

2 7  
4 5  
4 6

样例输出 Sample Output

3  
1

这道题目不需要用高精 是的这道题目坑死人

首先应该发现 根据同底数幂相加原则 我们要求的E\[i\]是底数p的fibonacci数fib\[i\]次方

这个数可能会很大

这时候就需要用到矩阵乘法加速状态转移求快速幂 因为矩阵乘法符合结合律 可以用倍增快速幂解决

但如果不边乘边取模 数据规模在十几时就会爆掉一万位

矩阵乘法完全可以取模 只有加和乘 这个不用担心

可是还是会爆，还会T

这时候要知道一个降幂公式：

![20151102194328527][]

所以要求欧拉函数 t14t41t神犇提供了一种更快的暴力欧拉方法

这个降幂公式不要和逆元弄混 b在mod p意义下的逆元是b的phi(p)-1次方 特别地 如果p是质数 逆元是b^(phi(p)-2) 因为这时候phi(p)==p-1 除自身外所有小于等于他的数都与他互质

所以这题就这么出来了

我第一次写矩乘 没用高精实在是万幸

这个代码基本是模了奥神的 姑且作为参考

//encrypt
    //第一次写矩乘+欧拉+快速幂+取模 加油啊~Cheer up!
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    #include
           
             typedef long long ll; using namespace std; ll m,p,n,q; int mo; struct mat { ll num[2][2]; mat(){memset(num,0,sizeof(num));} inline void prepare() { num[0][0]=0; num[1][0]=num[0][1]=num[1][1]=1; } inline mat operator * (const mat &b) const { mat c=mat(); for (int i=0;i<2;i++) { for (int j=0;j<2;j++) { for (int k=0;k<2;k++) { c.num[i][j]=(c.num[i][j]%mo+(num[i][k]%mo*(b.num[k][j]%mo))%mo)%mo; } } } return c; } inline mat operator ^ (int b) const { mat c=mat(); if (b<=0) { c.num[1][1]=1; return c; } --b; mat t=*this; c=*this; while (b) { if (b&1) c=c*t; t=t*t; b>>=1; } return c; } }ma; inline ll read() { char ch=getchar(); ll a=0; while (ch<'0'||ch>'9') { ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } return a; } inline int phi(int x) { int ret=x; for (int i=2;i*i<=x;++i) { if (x%i==0) { ret=ret/i*(i-1); while (x%i==0) x/=i; } } if (x>1) ret=ret/x*(x-1); return ret; } ll mi(ll a,ll b,ll c) { ll ans=1; while (b) { if (b&1) ans=(ans*a)%c; a=(a*a)%c; b>>=1; } return ans; } int main() { freopen("1.txt","r",stdin); ll ans; m=read();//数据组数 p=read();//底数 while (m--) { ans=0; n=read(); q=read(); mo=phi(q); ma.prepare(); ma=ma^(n-2); ans=(ma.num[1][0]+ma.num[1][1])%mo; ans+=mo; printf("%lld\n",mi(p,ans,q)); } return 0; }

——借问梅花何处落，风吹一夜满天山

[20151102194328527]: /images/20220731/218ebe579d584d56b38c49d8d2fe9565.png