chp2-信息论与数学基础课件

第2章信息论与数学基础

统计机器学习与数据挖掘技术与方法研讨班讲义信息论Shannon与20世纪40年代提出信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化问题。信息量与不确定性

一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。从这个角度可认为，信息量的度量就等于不确定性的多少。例子：冠军队预测熵（Entropy）的定义：设随机变量X，取值空间Ω，Ω为有限集合。X的分布密度为p(x)，p(x)=P(X=x)x∈X，则该随机变量的取值不确定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。熵率（语言信息率）

：：

r=H(M)/N语言绝对信息率：R=log2L语言多余度：D=R-r密码体制的安全性唯一解距离唯一解距离是指，当进行强力攻击时，可能接触唯一有意义的明文所需要的最少密文量。一般而言，唯一解距越长，密码体制越好。混乱和散布混乱用于掩盖明文和密文之间的关系，如凯撒移位密码。散布是通过将明文多余度分散到密文中使之分散开来的方法，如置换密码。复杂性理论1、算法的复杂性一个密码体制的强度是通过破译它所需的计算能力来确定的，所需的计算能力越大，表明密码体制的安全强度越大。一个算法的计算复杂性由两个角度来度量：T（时间复杂性）、S（空间复杂性）。通常，一个算法的计算复杂性的数量级用“O”表示表2.1当n=106不同算法族运行时间与n的关系复杂度所需运算所需时间（106运算/s）常数线性二次方三次方指数O(1)O(n)O(n2)O(n3)O(2n)110610121018103010301us1s11.6d32000年宇宙年龄的10301006倍2、问题的复杂性复杂性理论也将各种问题，按照解决问题时所需最少的时间及最小的空间将之归纳为不同类别的复杂度。

能够用多项式时间算法解决（输入与n成多项式关系）的问题称之为易处理的。

不能在多项式时间内解决的问题称之为难处理的，难处理的问题有时也称之为难解问题。复杂度与输入值成指数关系的问题属于难解问题。

依照求解问题所需的时间，复杂性理论也将各种问题区分成下面各类：（1）P问题：代表那些能够在多项式时间内可解的问题

易处理的，在确定性图灵机上多项式时间内可计算（2）NP问题：多项式时间内可验证的问题

在不确定性Turingmachine上多项式时间内可计算,不确定性Turingmachine能进行猜测,即不确定性Turingmachine如能猜出一个解的话,则确定性Turingmachine在多项式时间内可校验解的正确性.（3）NP－完全问题：是NP问题中的一些特殊问题，NP中的所有问题都可以转换成NP完全问题。换句话说，只要NP完全问题解决了，其他问题都可以解决。NP完全问题是NP问题中最困难的问题。3、NP－完全问题

（一）旅行商问题：一名旅行商必须旅行到n个不同的城市，而他只有一箱汽油（即有一个他能旅行的最远距离）。有方法使他仅用一箱汽油而旅行到每个城市恰好一次吗？（这是一般的汉密尔顿问题）

（二）三方匹配问题：有一屋子的人，包括n个男人，n个女人和n个牧师（祖父，犹太教士等等）。正常的婚礼将包括一个男人、一个女人和一个愿主持仪式的牧师。有了这样一张可能的三人一组的表，是否可能安排n个婚礼，使每一个人要么和一个人结婚，要么主持一个婚礼？（三）整数分解问题（四）背包问题（五）离散对数问题数论数论是研究数性质的一个数学分支，他同时也是密码学的基础学科之一。全体整数所组成的集合通常用Z表示，即：Z={…,-3,-2,-1,0,1,2,3,…}欧几里德（Euclid）算法

欧几里德（Euclid）算法

首先我们介绍整数的带余除法，它是整个数论的基础性定理之一。

对于两个整数a和b，可以对其进行分解来计算它们的最大公因数，但对于大整数而言，目前还没有足够有效的办法进行。实际中常用的用来计算两个数的最大公因数的算法称为欧几里德算法。它的理论依据正是前面所述的带余除法。

例1求(726,393),并求整数p和q使得(726,393)=726p+393q

自反性对称性传递性除了上述结论外，以下性质也是经常用到的习题求51mod13,和111mod13.求51mod17.例子：

例求21mod11.九、中国剩余定理

例利用中国剩余定理求解下列联立的线性同余式

习题1.

求(937,576),并求整数p和q使得(937,576)=937p+576q2.求51mod17.3.

利用中国剩余定理求解联立的线性同余式:例子

设有下列同余式:

x21,x22,x23,x24mod5求解?因子分解（NPC:整数分解问题）

在数论中，因子分解是一个古老而又困难的问题。现代的算法并不能测试出一个数所有可能的素因子。尽管如此，人们在这方面还是取得了不少的进展。

目前，比较好的因子分解算法有：二次筛选法数域筛法椭圆曲线法连式分解法试除法

（一）因子分解法（二）模N的平方根如果n是两个素数的乘积，那么计算模n的平方根的能力在计算上等价于对n进行因子分解的能力。换句话说，某人知道n的素因子，那么就能容易计算出一个数模n的平方根；这个计算已被证明与计算n的素因子一样困难。素数生成元

两个大的素数相乘，据推测它是一个单向函数，因为这两个数数相乘得到一个数是容易的，但分解这个大数且恢复原来的两个大素数却是困难的。这样，就有办法利用这个单向函数设计一个陷门单向函数。

单向函数是求逆困难的函数，而Diffie和Hellman引入的概念陷门单向函数(TrapdoorOne-wayFunction)，是在不知道陷门信息下求逆困难的函数，当陷门信息知道后，求逆是易于实现的。但如何给陷门单向函数下定义则难以解决，因为：

(1)陷门函数其实就不是单向函数，因为单向函数在任何条件下求逆都是困难的；

(2)陷门可能不止一个，通过实验，一个个陷门就可容易地找到逆。如果陷门信息的保密性不强，则求逆不难。测试一个整数是否素数也是一个经常遇到的事，但它与因子分解相比要容易得多。公钥密码体制需要素数，而产生这些素数由多种方法。

首先，我们将解决一些显尔易见的问题：（1）如果每个人都需要一个不同的素数，是否可以用光素数？（2）是否会有两个人偶然地选择了同样素数的情况呢？

（一）Solovage-Strassen方法（不讲）

（二）Rabin－Miller方法

这个算法是由Rabin发明的。事实上，这也是在NIST（国家标准和技术研究所）的DSS建议中推荐算法的一个简化版。

首先选择一个待测试的随机数p。计算b，b是2整除p-1的次数（即2b是能整除p-1的2的最大幂）。然后计算m，使得n=1+2bm。

(1)

选择一个随机数a，使得a小于p。

(2)

设j=0且z=ammodp。

(3)

如果z=0或z=p-1，那么p通过测试，可能是素数。

(4)

如果j>0且z=1，那么p不是素数。

(5)

设j=j+1。如果j<b且z=p-1，设z=z2modp，然后回到步骤（4）。

(6)

如果j=b且z=p-1，那么p不是素数。

（三）Lehmann方法另一种更简单的测试是由Lehmann独自研究出的。下面是迭代次数设置为100的这个算法：(1)

选择一个待测的随机数n。(2)

确信n不能被任何小素数整除。测试2、3、5、7和11将显著地提高这个算法的速度。(3)

选择100个1到n-1之间的随机数a1,a2,…,a100。(4)

对所有的ai=

a1,,a2,…,a100，计算ai(n-1)/2：如果对所有的i，ai(n-1)/2=1(modn)，那n可能是合数。如果对任一个i，ai(n-1)/2=1或-1(modn)，那么n是合数。如果对所有i，ai(n-1)/2=1或-1(modn)，(但并非所有i均等于1)，那么n是素数。（四）强素数

p-1和q-1的最大公因子应该较小。

p-1和q-1都应有大的素因子，分别记为p和q。

p-1和q-1都应有大的素因子，分别记为p和q。

(p-1)/2和(q-1)/2都应该是素数。

有限域上的离散对数（一）离散对数基本定义（二）计算有限群中的离散对数

习题

1、一条表示性别的消息的熵是

比特；一条表示一周的天数的消息的熵是

比特。

2、简述P问题、NP问题和NP－完全问题之间的关系。