（2）需要调用大数库（如：WinNTL 等）进行运算。
8．判定问题（decision problem）是仅有两个可能的解（“是”或“否”）的问题。判定
问题 ∏ 的全部实例之集 D∏ 存在划分 D∏ = Y∏ + N∏ ，即解为“是”（“否”）的实例均在 Y∏（N∏）。中。比如“正整数 n 是素数吗？”就是一个判定问题。依赖概率图灵机 PTM
令 a=1.
如果 n0 =1 则计算 a0 ≡ a ⋅ x(mod n) 否则计算 a0 ≡ a ⋅ xn0 (mod n)
如果 n1 =1 则计算 a1 ≡ a0 ⋅ x1(mod n) 否则计算 a1 ≡ a0 ⋅ x1n (mod n)
且 x2 ≡ x12 (mod n)
最后得到 ak−1 就是 xe (mod n)
7．假设 x,e,n 均为正整数 ( x, e < n) ，（1）如果 n2 x 不超过计算机语言某基本变量类型 允许记录的最大整数，研究计算 y = xe mod n 的快速算法；（2）如果 n 达到计算机语言某 基本变量类型允许记录的最大整数的 32 倍，研究计算 y = xe mod n 的快速算法；
解：（1）首先将 e 表示成二进制：
e = en ⋅ 2n + en−1 ⋅ 2n−1 + ... + e0
xe = xen ⋅2n +en−1⋅2n−1+...+e0 = ((((...( x2en × xen−1 )2 × xen−2 )2...)2 × xe1 )2 × xe0
用模重复平方方法计算：令 e = nk−1 ⋅ 2k−1 + nk−2 ⋅ 2k−2 + ... + n0
第 1 章 概论
第 1 章 概论
习题及参考答案
3．在国标 GB2312 的 6763 个汉字“字符”集上（即取 q=6763）密变换为： Ek (i) : i → j ，按 j = Ek (i) ≡ k1i + k0 (mod q), k0 , k1 ∈ Zq 计算密文，其中密钥 k=( k0 , k1 )，并且要求 gcd( k1 , q)=1，以保证加密变换是可逆的。 因为 6763 是素数，所以 k1 的选择自由。此处要求 k1 = 1, k0 = 0 (恒等变换)的情况舍去。
-2-
第 1 章 概论
pr{ PTM output = "是" | I ∈ N∏} ≤ 1/ 2 则称 R 是一个（解判定问题 ∏ 的）概率算法。在网络上查找到实际使用的产生（不少于 512
比特）大素数的计算机源程序，通过调整其内部（素性概率测试）循环次数的方法，使得对
某个大整数 n 在调整前后有不相同的输出判决，证实该程序实现的算法是一个概率算法。
将 a^m(mod n)赋值给 b, if b=1(mod n) then return(“n is prime”) for （i=0:1:k-1） do { if b=-1(mod n) then return ("n is prime") else 将 b^2(mod n)赋值给 b } return(“n is composite”) n 通过一次测试，则 n 不是素数的概率为 25%。
这样，通过 t 次迭代后，n 是奇合数输出“素数”的概率小于 (1/ 4)t 。 经过以上分析，该程序的实现算法是一个概率算法，它的错误概率比 (1/ 4)t 小。
-3-
h=0
h=0
其中 l = (ki − k j ) mod 26 在表中 g 分别取 12，14，2 所以通过编程计算重合互指数 MIc (Yi ,Yjg ) 的值为：
MIc (Y0 ,Y112 ) =0.0658
MIc (Y0 ,Y214 ) =0.0672
MIc (Y1,Y22 ) =0.0642
故，计算其密钥量为：6763 *φ(6763)-1 = 45731405。
4．按照定义 1.2 完成表 1.7 中用“√”标记栏（或更多栏）数值的计算，并证实（或否 定）例 1.7 的有关结论。
25
25
∑ ∑ 解：由公式： MIc (Yi ,Yj ) ≈ p p = h−ki h−k j p ph h+ki −k j
5．在中途岛战争前，美军通过散布“中途岛淡水设备发生故障”的消息，在日军密报 中确认了中途岛的代号，从而破译了日军的密报。此例密码分析属于哪种破译类型？
解：由于美军通过散布其选择的消息而获悉了一些对攻击有利的明文-密文对，从而破 译了日军的密报。所以此例密码分析属于选择明文攻击。
6．编制欧几里德算法程序求 gcd(u,v) ，假设初值满足 0 < u,v ≤ N = 21024 - 1 。
（ Probabilistic Turing machine, 即 带 有 随 机 数 发 生 器 的 DTM ） 可 以 定 义 概 率 算 法
（probabilistic algorithm）如下：在 PTM 上使用算法 R 求解判定问题 ∏ 。用 l[I ] 记实例 I 的 规模。如果存在时间复杂度函数 T，使得（1） ∀I ∈ D∏ ，PTM 均在 T（l[I ]）步内停机，并 输出“是”或“否”；（2） ∀I ∈Y∏ ，PTM 输出“是”；（3）在 N∏ 上的出错概率
解：米勒-拉宾算法是一个判断素性的多项式时间概率算法 。网络上可以查到它的 主要循环过程如下（给出循环一次的运行情况）：
使用 Miller-Rabin 算法测试正整数 n 是不是一个素数。 把 n −1写成 n −1= 2k *m ，其中 m 是一个奇数 选取随机整数 a ，使得 1≤ a ≤ n −1
解：由于 N 为 1024bit，属于大数，所以需要调用大数库（如：WinNTL）进行运算。 #include<stdio.h>
-1-
第 1 章 概论
#include"stdlib.h" int main() {long int a,b,m,n,u,v,t; printf("please input a and b:\n"); scanf("%ld %ld",&a,&b); u=a; v=b; if(a<b){t=a; a=b; b=t;} m=a/b; n=a-b*m; while(n!=0) { a=b; b=n; m=a/b; n=a-b*m; } printf("gcd(%ld,%ld)=%d\n",u, v, b); return 0; }