当前位置：文档之家 › 现代密码学 (彭代渊 著) 西南交通大学 课后答案-第1章概论习题与解答

现代密码学 (彭代渊 著) 西南交通大学 课后答案-第1章概论习题与解答

  • 格式：pdf
  • 大小：175.09 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

现代密码学(谷利泽)课后题规范标准答案

现代密码学(谷利泽)课后题规范标准答案

《现代密码学习题》答案第一章判断题×√√√√×√√选择题1、1949年，（A ）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。

A、ShannonB、DiffieC、HellmanD、Shamir2、一个密码系统至少由明文、密文、加密算法、解密算法和密钥5部分组成，而其安全性是由（D）决定的。

A、加密算法B、解密算法C、加解密算法D、密钥3、计算和估计出破译密码系统的计算量下限，利用已有的最好方法破译它的所需要的代价超出了破译者的破译能力（如时间、空间、资金等资源），那么该密码系统的安全性是（B ）。

A无条件安全B计算安全C可证明安全D实际安全4、根据密码分析者所掌握的分析资料的不通，密码分析一般可分为4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其中破译难度最大的是（D ）。

A、唯密文攻击B、已知明文攻击C、选择明文攻击D、选择密文攻击填空题：5、1976年，W.Diffie和M.Hellman在密码学的新方向一文中提出了公开密钥密码的思想，从而开创了现代密码学的新领域。

6、密码学的发展过程中，两个质的飞跃分别指1949年香农发表的保密系统的通信理论和公钥密码思想。

7、密码学是研究信息寄信息系统安全的科学，密码学又分为密码编码学和密码分析学。

8、一个保密系统一般是明文、密文、密钥、加密算法、解密算法5部分组成的。

9、密码体制是指实现加密和解密功能的密码方案，从使用密钥策略上，可分为对称和非对称。

10、对称密码体制又称为秘密密钥密码体制，它包括分组密码和序列密码。

第二章判断题：×√√√选择题：1、字母频率分析法对（B ）算法最有效。

A、置换密码B、单表代换密码C、多表代换密码D、序列密码2、（D）算法抵抗频率分析攻击能力最强，而对已知明文攻击最弱。

A仿射密码B维吉利亚密码C轮转密码D希尔密码3、重合指数法对（C）算法的破解最有效。

(完整版)北邮版《现代密码学》习题答案

(完整版)北邮版《现代密码学》习题答案

《现代密码学习题》答案第一章1、1949年，（ A ）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。

A、ShannonB、DiffieC、HellmanD、Shamir2、一个密码系统至少由明文、密文、加密算法、解密算法和密钥5部分组成，而其安全性是由（ D）决定的。

A、加密算法B、解密算法C、加解密算法D、密钥3、计算和估计出破译密码系统的计算量下限，利用已有的最好方法破译它的所需要的代价超出了破译者的破译能力（如时间、空间、资金等资源），那么该密码系统的安全性是（ B ）。

A无条件安全B计算安全C可证明安全D实际安全4、根据密码分析者所掌握的分析资料的不通，密码分析一般可分为4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其中破译难度最大的是（ D ）。

A、唯密文攻击B、已知明文攻击C、选择明文攻击D、选择密文攻击5、1976年，和在密码学的新方向一文中提出了公开密钥密码的思想，从而开创了现代密码学的新领域。

6、密码学的发展过程中，两个质的飞跃分别指 1949年香农发表的保密系统的通信理论和公钥密码思想。

7、密码学是研究信息寄信息系统安全的科学，密码学又分为密码编码学和密码分析学。

8、一个保密系统一般是明文、密文、密钥、加密算法、解密算法 5部分组成的。

9、密码体制是指实现加密和解密功能的密码方案，从使用密钥策略上，可分为对称和非对称。

10、对称密码体制又称为秘密密钥密码体制，它包括分组密码和序列密码。

第二章1、字母频率分析法对（B ）算法最有效。

A、置换密码B、单表代换密码C、多表代换密码D、序列密码2、（D）算法抵抗频率分析攻击能力最强，而对已知明文攻击最弱。

A仿射密码B维吉利亚密码C轮转密码D希尔密码3、重合指数法对（C）算法的破解最有效。

A置换密码B单表代换密码C多表代换密码D序列密码4、维吉利亚密码是古典密码体制比较有代表性的一种密码，其密码体制采用的是（C ）。

现代密码学课后题答案

现代密码学课后题答案

《现代密码学习题》答案第一章判断题×√√√√×√√选择题1、1949年，（ A ）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。

A、ShannonB、DiffieC、HellmanD、Shamir2、一个密码系统至少由明文、密文、加密算法、解密算法和密钥5部分组成，而其安全性是由（ D）决定的。

A、加密算法B、解密算法C、加解密算法D、密钥3、计算和估计出破译密码系统的计算量下限，利用已有的最好方法破译它的所需要的代价超出了破译者的破译能力（如时间、空间、资金等资源），那么该密码系统的安全性是（ B ）。

A无条件安全B计算安全C可证明安全D实际安全4、根据密码分析者所掌握的分析资料的不通，密码分析一般可分为4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其中破译难度最大的是（ D ）。

A、唯密文攻击B、已知明文攻击C、选择明文攻击D、选择密文攻击填空题：5、1976年，和在密码学的新方向一文中提出了公开密钥密码的思想，从而开创了现代密码学的新领域。

6、密码学的发展过程中，两个质的飞跃分别指 1949年香农发表的保密系统的通信理论和公钥密码思想。

7、密码学是研究信息寄信息系统安全的科学，密码学又分为密码编码学和密码分析学。

8、一个保密系统一般是明文、密文、密钥、加密算法、解密算法 5部分组成的。

9、密码体制是指实现加密和解密功能的密码方案，从使用密钥策略上，可分为对称和非对称。

10、对称密码体制又称为秘密密钥密码体制，它包括分组密码和序列密码。

第二章判断题：×√√√选择题：1、字母频率分析法对（B ）算法最有效。

A、置换密码B、单表代换密码C、多表代换密码D、序列密码2、（D）算法抵抗频率分析攻击能力最强，而对已知明文攻击最弱。

A仿射密码B维吉利亚密码C轮转密码D希尔密码3、重合指数法对（C）算法的破解最有效。

A置换密码B单表代换密码C多表代换密码D序列密码4、维吉利亚密码是古典密码体制比较有代表性的一种密码，其密码体制采用的是（C ）。

现代密码学原理与协议课后答案

现代密码学原理与协议课后答案

现代密码学原理与协议课后答案
1.密码学原理：僵尸攻击
答案：僵尸攻击是一种攻击技术，它通过向大量受感染计算机之间传
播恶意软件，将其控制在一个网络中，从而实现攻击者的恶意目的。

2.密码学原理：哈希算法
答案：哈希算法是一种用于验证数据完整性的数学算法，它能够快速
地生成一个固定长度的散列值，这个值反映了输入数据的内容和长度，所
以不同的输入会生成不同的散列值。

3.密码学原理：公钥基础设施
答案：公钥基础设施（PKI）是管理公钥密码学系统中的证书等信息
的独立机构，它保证了数字证书的安全性，同时还保护使用公钥密钥将信
息加密和解密的用户的隐私。

4.密码学原理：数字签名
5.密码学原理：RSA算法
答案：RSA算法是一种非对称密码加密算法，它使用一对相关的密钥
来加密和解密信息，其中一个密钥用于加密信息，另一个则用于解密信息。

6.密码学原理：对称加密
答案：对称加密是一种加密算法，它只使用一个密钥来加密和解密信息。

现代密码学

现代密码学

恶意程序
需主程序
不需主程序
陷门
逻辑 炸弹
特洛伊 木马
病毒
细菌
蠕虫
图1.2 恶意程序分类
对恶意软件也可根据其能否自我复制来进行分 不能自我复制的一般是程序段， 类。不能自我复制的一般是程序段，这种程序段在 主程序被调用执行时就可激活。 主程序被调用执行时就可激活。能够自我复制的或 者是程序段（病毒）或者是独立的程序（蠕虫、 者是程序段（病毒）或者是独立的程序（蠕虫、细 菌等），当这种程序段或独立的程序被执行时， ），当这种程序段或独立的程序被执行时 菌等），当这种程序段或独立的程序被执行时，可 能复制一个或多个自己的副本， 能复制一个或多个自己的副本，以后这些副本可在 这一系统或其他系统中被激活。以上仅是大致分类， 这一系统或其他系统中被激活。以上仅是大致分类， 因为逻辑炸弹或特洛伊木马可能是病毒或蠕虫的一 部分。 部分。
信息的安全威胁
自然威胁：自然灾害、恶劣的场地环境、电磁辐 射和电磁干扰、网络设备自然老化。 人为威胁（恶意的或无恶意的用户） 入侵网络的用户也称为黑客，黑客可能是某个无 恶意的人，或者是某个心怀不满的雇员，也可 能是一个犯罪分子。 恶意软件（病毒、蠕虫等恶意程序） 需要主程序，是某个程序中的一段，不能独立于 实际的应用程序或系统程序； 不需要主程序,能被操作系统调度和运行的独立程 序。
高等院校信息安全专业系列教材
杨波 主编
现代密码学
总 目 录
第1章 章 第2章 章 第3章 章 第4章 章 第5章 章 第6章 章 第7章 章 第8章 章 引言 流密码 分组密码体制 公钥密码 密钥分配与密钥管理 消息认证和杂凑算法 数字签字和密码协议 网络加密与认证
第1章 引言 章
1.1 信息安全面临的威胁 安全威胁 入侵者和病毒 安全业务 1.2 信息安全的模型 1.3 密码学基本概念 保密通信系统 密码体制分类 密码攻击概述 1.4 几种古典密码 单表代换密码 多表代换密码

现代密码学概论

现代密码学概论
主要技术：分组密码与流密码 定义 4(分组密码) 将明文消息在编码集按照固定长度t 进行分组，再一组一组地加\解密明\密文消息。 #著名的DES、AES都是这类密码。
2.1.4 现代密码学主要技术(续)
定义5 K 是加密变换集的密钥空间，序列 e1e2… eiK称为密钥流。 定义6 (流密码) 消息m以串的形式(m1m2…mi)给出， 密钥e1e2…ei是K上的密钥流。流密码通过ci=Eei(mi) 给出密文消息(c1c2…ci)；如果di为ei的逆，解密则通 过mi=Ddi(ci)完成。
秘密密钥 d6 A6
A5, e5, ST(A5 || e5)=s5 A6, e6, ST(A6 || e6)=s6
图2.4 证书认证过程
# 证书权威负荷小(离线、非交互、存储证书)，权限低
2.1.4 现代密码学主要技术(续)
公钥证书的产生
情况1 可信方产生密钥对。可信方为实体产生公 钥算法的密钥对，并将公开密钥和绑定身份的公 钥证书通过公共信道发给该实体。实体在证明了 自己的身份(例如，出示身份证或个人可信照片) 后，将通过安全信道得到对应的秘密密钥。
2.1.4 现代密码学主要技术(续)
签名和认证函数必须满足的性质 1) 当且仅当Vk’ (m, s)=True时，s是消息m的合 法签名。
2) 对于任何签名者以外的实体在计算上不可 能得到任意的一组mf和sf满足Vk’ (mf , sf)=True。 数字签名的争议解决(不可否认)
如果签名者和验证者对签名发生争议，可由 验证者带着签名(m, s)提交给可信任第三方 (TTP)，由TTP验证该签名，最后进行仲裁。
# 特点：时实性。
2.1.4 现代密码学主要技术(续)
直观安全目标： a 在宣称者A和验证者B都诚实地执行认证时，A能向B成 功地证明自己，也就是B将完成执行并接受A所宣称的身 份。 b (不可转移性)验证者B不能从与宣称者A交互中获得的信 息，成功地向第三方C来冒充A 。 c (不可冒充性)任何一个非宣称者A的C想通过扮演A的身 份，通过验证者B的认证，让B接受A的身份的可能性可以 忽略。这里，可以忽略的含义是概率小到没有具体的实际 意义，准确的度量需要根据实际应用而定。 d 即使如下情况存在，以上三个条件仍然成立。 d.1宣称者A和验证者B之间以前进行的多项式次认证会话 且被窃听; d.2 冒充者C以前参与了同宣称者A或（和）验证者B的认 证执行; d.3 冒充者C可能发起多个认证会话并行运行。

现代密码学-流密码


7
2.1 流密码一般模型
流密码的分类 同步流密码(SSC: synchronous stream cipher)
产生密钥序列的算法与明文、密文无关.
i F ( i 1 , k ), zi f ( i , k ),
ci E ( zi , mi ).
k
密钥流生成器
i : 密钥流生成器的内部状态 0 : 密钥流生成器的初始状态
满足上述三个条件的序列称 sequence), 简记为: PN序列. PN序列在CDMA,通信同步, 导航, 雷达测距等领域 有重要应用.
18
Solomon W. Golomb: Shimonoseki, Japan, October 10-14, 2005
(G1)：在一个周期内，0与1出现的个数至多相差1。也即， 如果N为偶数，则在一个周期内0与1的数目各占N/2； 如果N为奇数，则在一个周期内0的数目为(N+1)/2或者 (N-1)/2，相应地1的数目为(N-1)/2或者(N+1)/2。 (G2)：在一个周期内，长度为i 的游程个数占游程总数的 1/2i，i=1,2, …。且在长度为i的游程中，0的游程与1的 游程数目相等或至多相差一个。 (G3)：序列的异相自相关函数是一个常数。
20
伪随机序列
反馈移位寄存器(FSR: Feedback Shift Register)
n个寄存器: 从右至左依次称为第1,2,…,n 级 反馈函数 f(x0, x1,…,xn-1): GF(2)nGF(2). 工作原理: 当一个时钟脉冲来到时, 第i 级寄存器的内容传送给第 i-1级寄存器(i=2,3,…,n),第1 级寄存器的内容为反馈移位寄存器 的输出. 反馈函数 f(x0, x1,…,xn-1)的值传送给第n级寄存器. FSR的输出序列: a0, a1,a2,…,an,… 称为反馈移位寄存器序列(FSR 序列).

现代密码学教程


（）
(7) 差分分析是一种攻击迭代密码体制的选择明文攻击方法，所以，对于 和 都有一
定的攻击效果。
（）
(8) 线性分析实际上是一种已知明文攻击方法。
（）
(9) 通过 类似， 也存在弱密钥，但其弱密钥数量少于 的弱密钥数。 （ ）
(10) 算法是可逆的，即可以用相同的算法进行加密和解密。
（）
(11) 因为 密码算法采用 结构，所以具有加解密相似的特征。 （ ）
，并且
，
，
，求 。
（8） 请给出一个 完全类问题的例子。
第四章 分组密码
1.
(1)
判在分断组题密码中，分组或密钥越长意味着安全性越高，因此，在实际应用中应选用分组和
密钥都长的分组密钥算法。
（）
(2) 分组密码一般采用简单的、安全性弱的加密算法进行多轮迭代运算，使得安全性增强。
一般来说，分组密码迭代轮数越多，密码分析越可困难。
计算机网络的普及和发展。
（）
（5） 年后，美国数据加密标准（ ）的公布使密码学的研究公开，从而开创了现
代密码学的新纪元，是密码学发展史上的一次质的飞跃。
（）
（6） 现代密码系统的安全性不应取决于不易改变的算法，而应取决于可随机改变的密钥。
（）
（7） 能经受住选择明文攻击的密码体制就能经受住已知明文攻击。 （ ）
第五章 序列密码
1（. 1）判断序题列密码（又称流密码）是属于对称密码体制。
（）
（2） 序列密码的加解密钥是由种子密钥生成的，而种子密钥的长度是由需加密的明文长
度决定。
（）
（3） 利用反馈移位寄存器来生成序列密码的密钥的过程中，反馈移位寄存器的初始值是
由种子密钥决定的。

现代密码学谷利泽课后题答案word文档良心出品

现代密码学谷利泽课后题答案word文档良心出品《现代密码学习题》答案第一章判斷题选择题1. 1949年，（A ）发衣题为《保密系统的通信理论》的文章.为密码系统建立了理论基础，从此密码学成了一门科学? A. Shannon B 、Diffie C 、Hellman D. Shamir2. 一个密码系统至少由明文、密文、加密算法、解密算法和密钥5部分组成?而其安全性是由（D ）决定的。

A.加密算法B.解密算法C.加解密算法D 、密钥3、计算和估计出破译密码系统的计算量下限，利用己冇的Ai 好方法破译它的所需要的代价超出了破译者?的破译能力（如时间.空仙.资金等资源人那么该密码系统的安全性是（B ）oA 无条件安全B 讣算安全C 可证明安全D 实际安全4. 根据密码分析者所掌握的分析资料的不通，密码分析一般可分为4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其中破译难度最人的是（D ）oA 、唯密文攻击B 、己知明文攻击C 、选择明文攻击D 、选择密文攻击填空题：开创了现代密码学的新领域。

6.密码学的发展过程中，两个质的飞跃分别指 1949年香农发表的保密系统的通信理论和公钥密码思想?密码学足研究信息寄信息系统安全的科学，密码学又分为_密码编码学和密码分析学。

密码体制是指实现加密和解密功能的密码方案?从使用密钥策略上，可分为对称和非对称第二章判断题:选择题:1. 字母频率分析法对（B ）算yiAi/f 效。

A.置换密码B.单表代换密码C.多表代换密码D.序列密码 2、（D ）算法抵抗频率分析攻击能力址强?而对己知明文攻击最弱。

5. 1976 年? W, Diffie 和乩 Hellman 在密码学的新方向一文中捉出了公开密钥密码的思想，从而7、 8、一个保密系统一般是明文密文、密钥.加密算法■解密算法 5部分组成的。

9. 10.对称密码体制又称为」密码体制，它包括一分组密码和序列密码。

现代密码学第1章概论1010


M m
c Ek1 (m)
C
c
c Ek1 (m)
Dk2 (c) m
Dk2 (c) m
20
1.2 密码系统模型和密码体制
密码体制系统的分类 对称密码体制(symmetric cryptosystem) k=k1=k2 或 k1 k2 单钥、私钥 (one-key, private key)密码体制
我国
党的十五届五中全会明确指出，大力推进国民经济 和社会信息化是覆盖现代化建设全局的战略举措。 要以信息化带动工业化。
在《科技教育发展“十五”重点专项规划（高技术产 业发展规划）》中明确提出攻克信息保护、隐患发 现、安全反应等关键技术，为国家信息基础建设提 供技术支撑。
1999年国务院颁布商用密码管理条例，对密码的管 理使用进行了具体规定。
3
1.1 信息系统安全与密码技术
信息时代 农业革命工业革命信息革命 20世纪80年代美国Toffler A. 著《第三次浪潮》， 预言： 计算机网络的建立与普及将彻底改变人类的生存和 生活模式
信息、资源、能源是人类生存的三大支柱
4
1.1 信息系统安全与密码技术
民用 Internet普及 电子政务 电子商务 电子金融
11
侵害对象 机密性 完整性
可用性
认证性 公平性 可控性
威胁或攻击手段 入侵系统取得高级授权 破译密码
插入、删除、篡改 信道干扰 摧毁系统硬件
扰乱以至摧毁系统软件 用户恶意占用 业务拒绝 发送方身份假冒，接收抵赖 破坏收发审计记录 非对等的密钥协商 利用非公平交易协议获取利益 破坏“密钥托管”，阻止“匿名撤消” 抗内容检测过滤的“穿透” 阻止司法取证
现代密码学
Modern Cryptography
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

（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; }