chap 1-8 数论算法-综合应用

2022-01-02 Blog 0 visits

1. Divisible?

$4^{1536}-9^{4824}$是否能被35整除？

$35=5\times 7$，根据费马小定理：$a^{5-1}\equiv 1 (\mod 5)$，$a^{7-1}\equiv 1(\mod 7)$，由于5和7都是素数，易得：$a^{(5-1)(7-1)}\equiv 1(\mod 35)$，即$a^{24}\equiv 1(\mod 35),1\leq a<35$。因此$4^{1536}-9^{4824}\equiv 4^{24\cdot 64}-9^{24\cdot 201}\equiv 1-1(\mod 35)$，故$4^{1536}-9^{4824}$能被35整除。

2. “快速”幂

计算$x^y$时，假设我们想要最终的真实结果（不取模），有两种计算方法，第一种是使用迭代法：

$$
x\to x^2\to x^3\to \cdots\to x^y
$$

依次累乘，直至计算出最终结果。第二种方法是递归分治（快速幂）：

$$
x\to x^2\to x^4\to x^8\to \cdots\to x^y
$$

哪种方法会更快呢？假设$x$的位数为$n$，则第一种方法的时间复杂度为：

$$
O(n\cdot n+n\cdot 2n+n\cdot 3n + \cdots + n\cdot (y-1)n)=O(n^2\cdot \frac{y(y-1)}{2})=O(n^2y^2)
$$

第二种方法的时间复杂度为：

$$
O(n\cdot n+2n\cdot 2n+2^2n\cdot 2^2n + \cdots +(2^2)^{\lfloor\log y\rfloor-1}n^2)=O(n^2\cdot \frac{(2^2)^{\lfloor\log y\rfloor}-1}{3})=O(n^2y^2)
$$

对比可以发现，若考虑算术运算的复杂度，两种方法的总时间复杂度其实是同阶的。

3. 相邻的斐波那契数

两个相邻的斐波那契数一定互质吗？

使用数学归纳法，$n=1$时，$gcd(F_2,F_1)=1$；假设$n\leq k$时，$gcd(F_{k+1},F_{k})=1$；则$n=k+1$时，$gcd(F_{k+2},F_{k+1})=gcd(F_{k+1},F_{k+2}-F_{k+1})=gcd(F_{k+1},F_{k})=1$。

故两个相邻的斐波那契数一定互质。

4. 加法器

使用行波进位加法器实现两个$n-bit$整数的加法，电路的深度为$O(n)$。

若使用超前进位加法器实现两个$n-bit$整数的加法（并行化），电路的深度将减少为$O(\log n)$。（减少了延迟）

若使用超前进位加法器实现$m$个$n-bit$整数的加法（每两个一组），电路的深度最少为$O((\log m)(\log n)$。

5. 阶乘

设$N$为一个$n-bit$的正整数，则$N!$大约有多少位？之前证明过，$\log(N!)=\Theta(N\log N)$，也可以通过Stirling公式推出：

$$
\log(N!)=\sum_{k=1}^{N}\log k=\log(\sqrt{2\pi N}(\frac{N}{e})^N)=\Theta(N\log N)
$$

设计一个计算阶乘的算法：

factorial (N)
	f = 1
	for i = 2 to N
		f = f * i

算法的时间复杂度：

$$
O(\sum_{i=1}^N i\log i\cdot\log i)=O((\log N)^2\sum_{i=1}^N i)=O((N\log N)^2)=O((N\cdot n)^2)
$$

6. 乘方

若一个$n-bit$的正整数$N>1$能够被表示为$q^k$（$q,k$为正整数，且$k>1$），则$N$被称为是一个乘方数。如何设计一个算法，判断$N$是否为乘方数？

先确定$k$的范围，$N=q^k$即$k=\log N/\log q$，推出$1<k\leq \log N$。对于每个$k$，我们可以使用二分法判断$q\in [2, N]$是否满足$q^k=N$，二分法共需$O(\log N)=O(n)$次，每次需要计算乘方$q^k$，复杂度为$O(k^2n^2)$，故总复杂度为$O(\log N \cdot n \cdot k^2n^2)=O(n^6)$。

7. lcm与gcd

$lcm(x,y)$（least common multiple）表示$x,y$的最小公倍数。有如下结论成立：

$$
gcd(x,y)\cdot lcm(x,y)=x\cdot y
$$

$Proof$：

设$x=p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdots p_k^{a_k}$，$y=p_1^{b_1}\cdot p_2^{b_2}\cdot p_3^{b_3}\cdots p_k^{b_k}$，$p_k$为素数，

则$gcd(x,y)=p_1^{\min(a_1,b_1)}\cdot p_2^{\min(a_2,b_2)}\cdot p_3^{\min(a_3,b_3)}\cdots p_k^{\min(a_k,b_k)}$，

$lcm(x,y)=p_1^{\max(a_1,b_1)}\cdot p_2^{\max(a_2,b_2)}\cdot p_3^{\max(a_3,b_3)}\cdots p_k^{\max(a_k,b_k)}$，

易得：$gcd(x,y)\cdot lcm(x,y)=p_1^{a_1+b_1}\cdot p_2^{a_2+b_2}\cdot p_3^{a_3+b_3}\cdots p_k^{a_k+b_k}=x\cdot y$。▮

8. Wilson定理

Wilson定理也能够被用来判断素数：

Wilson定理：$N$为素数，当且仅当 $(N-1)!\equiv -1(\mod N)$。

$Proof$：

若$N$为素数，则对于所有$1\leq x<N$，$x\mod N$的乘法逆元均存在（双射关系）。设$x^2\equiv 1(\mod N)$，推出$x\equiv 1$或$x\equiv N-1 (\mod N)$，说明$1$和$N-1$的乘法逆元是自身。由此可得：$(N-2)\cdot(N-1)\cdots 2\equiv 1(\mod N)$，即$(N-1)!\equiv N-1\equiv -1(\mod N)$。

若$N$不是素数，假设$(N-1)!\equiv -1(\mod N)$仍成立，令$(N-1)!=-1+kN$，即$1=-(N-1)!+kN$，说明$gcd((N-1)!,N)=1$，显然不成立。故若$N$不是素数，$(N-1)!\not\equiv -1(\mod N)$。▮

对比费马小定理，如果使用Wilson定理进行素性测试，将不会出错，那为何不这样做呢？主要原因就是Wilson定理需要计算阶乘，而计算阶乘的复杂度太高，不适合对大数进行运算。

9. 中国剩余定理

假设$p,q$为两个不同的互质的数，那么对于每对$(j,k)$（$0\leq j<p,0\leq k<q$），都存在一个唯一的整数$0\leq i<pq$使得$i\equiv j(\mod p)$，且$i\equiv k(\mod q)$：

$$
i=[j\cdot q\cdot (q^{-1}\mod p)+k\cdot p\cdot(p^{-1}\mod q)]\mod pq
$$

$Proof$：上述等式易证，下面证明唯一性，反证法。假设存在两个不同的$i,i’$满足上述条件，则$i=Ap+j=Bq+k,i’=Cp+j=Dq+k$，$i-i’=(A-C)p=(B-D)q$，表明$p$整除$B-D$，$q$整除$A-C$。推出$i-i’\equiv 0(\mod pq)$，与假设矛盾。故原结论成立。▮

推广至一般情况，中国剩余定理其实提供了一元同余线性方程组有解的判定条件，以及通解的形式：

$$
\begin{equation}
\begin{cases}
x\equiv a_1(\mod p_1) \\ x\equiv a_2(\mod p_2) \\ \vdots \\ x\equiv a_n(\mod p_n)
\end{cases}
\end{equation}
$$

若方程组中的$p_{1:n}$都互质，则对于任意整数$a_{1:n}$，该方程组都有解，通解为：

$$
x=[\sum_{k=1}^N a_k \cdot P_k \cdot (P_k^{-1}\mod p_k)]\mod\prod_{k=1}^N p_k, 其中P_k=\prod_{i=1,i\neq k}^N p_i
$$

10. 被素数整除

把一个正整数$n$从右至左分成几组，每组有$r$个数字，假设$p$为非2和5的素数，若能通过判断$p$是否能整除几组数字之和，来推出$p$是否能整除$n$ ，那么$r$一定是$p-1$的因子。比如$n=1716,p=11$时，令$r=2$，1716可分为两组：(16,17)，16+17=33能被11整除，那么1716一定能被11整除，此时$r$也是$p-1$的一个因子。（大家一定都用过$p=3,r=1$的情况）

$Proof$：假设整数$N$被分为了$k$组：$N_kN_{k-1}\cdots N_1$，则$N=N_1+N_210^r+\cdots+N_k(10^r)^{k-1}$，所有组数字之和为$N_1+N_2+\cdots+N_k$。若$N_1+N_210^r+\cdots+N_k(10^r)^{k-1}\equiv N_1+N_2+\cdots+N_k (\mod p)$，那么需要满足$10^r\equiv 1(\mod p)$。由费马小定理可知，$10^{p-1}\equiv 1(\mod p)$，故$r$为$p-1$的因子。▮

11. $a^{b^{c}}\mod p$

设$p$为素数，计算$a^{b^{c}}\mod p$。

利用费马小定理，$a^{b^{c}}\mod p=a^{b^{c}\mod (p-1)}\mod p$，然后使用快速幂。

12. “破译”RSA

(1) 假设在RSA算法中，令$N=p$，$e$为与$p-1$互质的整数，$d$为$e\mod p-1$的逆元，加密算法为$x^e\mod p$，解密算法为$(x^e)^d\mod p$。截获了$x^e\mod p$，是否有方法破译？

直接计算$d$的值即可，然后解密。

(2) 假设在RSA算法中，Alice的secret-key $d$的值泄露，Eve是否能借助$d$值求出$p,q$？

由$ed\equiv 1(\mod(p-1)(q-1))$得：$ed=1+k(p-1)(q-1)$，而$N=pq,d<(p-1)(q-1)$，通过试探$k$可以解出$p,q$。

(3) Alice使用RSA算法，给她的三位朋友（$(N_i,e_i=3),N_i=p_iq_i$）发送了相同的消息$M$，然后都被Eve截获了：$M^3\mod N_1,M^3\mod N_2,M^3\mod N_3$，该消息有被破译的风险吗？

令$x=M^3$，运用中国剩余定理可知，$x<N_1\cdot N_2\cdot N_3$存在且唯一，可以直接套用公式解出，解出$M^3$后开立方即得到$M$。

13. RSA数字签名

Alice和Bob使用RSA加密算法传递消息可以确保消息不会被Eve破译，但是Eve可以截获消息后修改消息再发送，或者Eve可以假冒Alice给Bob发送消息，如何避免这个问题呢？数字签名就派上用场了。数字签名的主要作用是解决伪造、抵赖、冒充和篡改问题。下面详细介绍RSA数字签名算法。

假设Alice的public-key为$(N_a,e_a)$，secret-key为$d_a$；假设Bob的public-key为$(N_b,e_b)$，secret-key为$d_b$。现在Alice想要给Bob发送一条消息，Bob需要确认消息确实是Alice发的而且中途未被篡改，他们可以这样做：

Alice将要发送的消息为$M$。和常规的RSA算法一样，Alice将发送加密后的消息$M^{e_b}\mod N_b$。
Alice除了发送$M^{e_2}\mod N_2$，她还要对消息$M$进行签名操作（sign）：使用哈希函数生成消息全文的摘要信息$h(M)$（不可逆，如md5），然后发送签名$[h(M)]^{d_a}\mod N_a$。总结来说，Alice发送了加密消息$M^{e_2}\mod N_2$和她的签名$[h(M)]^{d_a}\mod N_a$。
Bob将收到加密消息$M^{e_b}\mod N_b$。和常规的RSA算法一样，Bob可以使用自己的secret-key解密$M’\equiv (M^{e_b})^{d_b}(\mod N_b)$。
Bob获得消息$M’$后，还需要对消息$M’$进行验证操作（verify）：解开Alice的签名$h(M)\equiv [[h(M)]^{d_a}]^{e_a}(\mod N_a)$，使用相同的哈希函数生成对消息$M’$的摘要$h(M’)$，若$h(M’)=h(M)$，则说明消息$M’$确实是Alice发送的，且中途未被篡改；否则，该消息是不可信任的。

为什么一定要对消息的摘要签名，而不是直接对消息签名呢？假设现在直接对消息签名，Alice发送消息$M$给Bob，Eve截获了$M^{e_b}\mod N_b$；然后Eve请Bob发这段可疑的文字内容$M^{e_b}\mod N_b$给Alice。若Bob发送了，Eve便可以截获数字签名$(M^{e_b})^{d_b}\mod N_b$，从而得到$M$。就算Bob拒绝发送可疑的文字内容，Eve也可以让内容变得不可疑：挑选一个与$N_b$互质的整数$k$，然后让Bob发送$M^{e_b}\cdot k^{e_b}\mod N_b$。若Bob发送，Eve便可截获数字签名$((Mk)^{e_b})^{d_b}\mod N_b=Mk\mod N_b$，此时Eve只需要计算出$k^{-1}\mod N_b$，就可以破解出$M$。综上所述，我们需要对消息进行不可逆的摘要后，再进行签名。

RSA加密算法与数字签名看似已经非常完美了，但是仍然存在风险：在传输消息之前，Alice和Bob都需要互换对方的公钥，如果在传输公钥的过程中，Eve截获了公钥，然后伪造公钥，Eve便可以作为第三者和Alice、Bob通信，而Alice和Bob都还以为自己和对方正常通信。总结来说就是，无法确定接收到的公钥是否是对方生成的且未被篡改，这显然这可以通过数字签名来解决。目前的通用方案是：Bob先去一个被大家所信任的第三方机构（CA机构）注册他的数字证书，数字证书里面包含了Bob的公钥和CA机构对证书内容的数字签名，CA机构会把该数字证书颁发给Bob。Alice若想发消息给Bob，先要取得Bob的公钥。于是Alice向Bob请求数字证书，Alice使用CA机构的公钥验证证书的数字签名，保证该证书一定是由机构发出的且未被篡改，Alice便可以获得Bob真实的公钥。问题又来了，CA机构公钥的真实性如何保障，这个公钥是否能被第三方篡改？不可能，因为CA机构被大家所信任，它的公钥一般都直接被保存在了本地电脑中，无需网络通信传输。

Quick Link: 算法笔记整理