数论中的伪随机二进制数列
2008-5
科学出版社
刘华宁
170
无
随着通信与计算机网络的发展，伪随机二进制数列得到了广泛的应用，并已成为密码学的一个基本工具，在构造密码系统中起着重要的作用。本书介绍了如何基于数论中的Legendre符号、Liouville函数、最大素因子、丢番图逼近、指标、最小非负剩余、Lehmer问题与Gallagher问题等来生成伪随机二进制数列，使用的方法涉及多项式特征和的估计、多项式指数和的估计、Dirichlet L函数均值、有限域上多项式理论等。该书是对这一新兴领域十余年来研究工作的一个阶段性总结，其中包含了作者近几年来的研究成果。 本书可供高等院校数学系、计算机系研究生或高年级本科生学习，也可供数论、信息安全与密码学相关专业人员参考。
第1章 伪随机二进制数列的测度 §1.1 伪随机测度 §1.2 测度之间的关系 §1.3 线性复杂度与相关性 §1.4 测度的取值范围（I） §1.5 测度的取值范围（II） §1.6 进制数列上的Gowers范数第2章 数论基础 §2.1 整除与同余 §2.2 剩余系与整数逆 §2.3 指标与原根 §2.4 Legendre符号，特征与特征和 §2.5 指数和的估计第3章 Legendre符号与特征 §3.1 Legendre符号的伪随机性 §3.2 可容许的三元组 §3.3 多项式Legendre符号的伪随机性 §3.4 特征的伪随机性 §3.5 多项式Legendre符号的碰撞与雪崩效应第4章 Liouville函数 §4.1 一致分布测度——指数和 §4.2 一致分布测度——Perron公式 §4.3 Liouville函数的相关性——初等方法 §4.4 整数环的伪随机子集（I） §4.5 整数环的伪随机子集（II） §4.6 Liouville函数的相关性——伪随机子集 §4.7 Liouville函数的相关性——圆法第5章 Erdos的猜想 §5.1 P（n）与P（n+1）的伪随机性 5.1.1 一致分布——初等方法 5.1.2 一致分布——小筛法 5.1.3 相关性——小筛法 §5.2 最大素因子的伪随机性 §5.3 （nα）数列与（n2α）数列的伪随机性 5.3.1 一致分布测度的下界估计 5.3.2 一致分布测度的上界估计 5.3.3 相关性的反例 §5.4 （nkα）数列的伪随机性 5.4.1 一致分布测度 5.4.2 相关测度第6章 指标与最小非负剩余 §6.1 多项式的指标 6.1.1 一致分布测度 6.1.2 相关测度 §6.2 多项式的最小非负剩余 §6.3 多项式的乘法逆 6.3.1 一致分布测度 6.3.2 相关测度第7章 Lehmer问题与Gallagher问题 §7.1 Gallagher问题中的伪随机数列 §7.2 Lehmer问题中的伪随机数列与Legendre符号 §7.3 Gallagher问题中的大族伪随机数列 §7.4 Lehmer问题中的大族伪随机数列与最小非负剩余第8章 密码学中的初步应用 §8.1 统计测试 §8.2 伪随机测度与统计测试 §8.3 素数模的选择参考文献
第1章 伪随机二进制数列的测度 当前人类已经进入了一个崭新的时代，传统的商务活动、事务处理以及政府服务等越来越多地通过开放的计算机和通信网络来实施和提供。只有在开放网络能提供安全通信的情况下，上述活动才能顺利实现，而各种形式的密码则是解决这一问题的基本理论和方法。 一个密码系统的安全性可以通过破译该系统的最好算法的计算复杂性来度量，因而计算复杂性理论已成为现代密码学的基础。与此同时，伪随机二进制数列得到了广泛的应用，并已成为密码学的一个基本工具，在构造密码系统中起着重要的作用。具体来说，基于计算复杂性理论构造的伪随机二进制数列与真随机数列是多项式时问不可区分的，也是多项式时间不可预测的。这种类型的伪随机二进制数列具有重要的意义，用它构造的密码体制具有与用相同长度的真随机数列构造的密码体制同样的安全性。 目前已有的基于计算复杂性理论构造的伪随机二进制数列都是基于大数分解或离散对数等数学难题的，由于生成速度慢等缺点，不能完全满足实际的需要。在实际应用中，当需要伪随机二进制数列时，人们通常利用硬件设备或数学方法来获得所需数列。然而对于得到的数列，人们往往事先不知道其伪随机性如何，因此必须进行某些统计测试，使得伪随机数列满足真随机数列所应具有的某些统计性质或能通过某些统计测试。 ……
无
这是我想要的东西。