1、统计机器学习与数据挖掘技术与方法研讨班讲义第2章 信息论与数学基础信息论信息论nShannon 与20世纪40年代提出n信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到 1948 年，香农提出了“信息熵”的概念，才解决了对信息的量化问题。n信息量与不确定性信息量与不确定性 一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。从这个角度可认为，信息量的度量就等于
2、不确定性的多少。n例子：冠军队预测n熵（熵（Entropy）的定义：的定义：设随机变量设随机变量X X，取值空间，取值空间，为有限集合。为有限集合。X X的分的分布密度为布密度为p p(x x)，p p(x x)=P=P(X=xX=x)x xX X，则该随机变量，则该随机变量的取值不确定程度，即其熵为：的取值不确定程度，即其熵为：当使用当使用log2log2时，熵的单位为比特时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。反映一个信源发出不同信号，具有的平均信息量。2()()()log()0log0 0,loglogxH XH pp xp xall possible values
3、Definen熵率（语言信息率）熵率（语言信息率）：r=H(M)/N 语言绝对信息率：语言绝对信息率：R=logR=log2 2L L 语言多余度：语言多余度：D=R-rD=R-r密码体制的安全性唯一解距离n唯一解距离是指，当进行强力攻击时，可能接触唯一有意义的明文所需要的最少密文量。一般而言，唯一解距越长，密码体制越好。混乱和散布n混乱用于掩盖明文和密文之间的关系，如凯撒移位密码。n散布是通过将明文多余度分散到密文中使之分散开来的方法，如置换密码。复杂性理论1、算法的复杂性、算法的复杂性 一个密码体制的强度是通过破译它所需的计算能力来确定的，所需的计算能力越大，表明密码体制的安全强度越大。一
4、个算法的计算复杂性由两个角度来度量：T（时间复杂性）、（时间复杂性）、S（空间复杂性）（空间复杂性）。通常，一个算法的计算复杂性的数量级用“O”表示表表2.1 当当n=106不同算法族运行时间不同算法族运行时间与与n的关系的关系复杂度复杂度所需运算所需运算所需时间（所需时间（106运算运算/s）常数线性二次方三次方指数O(1)O(n)O(n2)O(n3)O(2n)110610121018103010301us1s11.6d32000年宇宙年龄的10301006倍2、问题的复杂性、问题的复杂性 复杂性理论也将各种问题，按照解决问题时所需最少的时间及最小的空间将之归纳为不同类别的复杂度。能够用多项
5、式时间算法解决（输入与n成多项式关系）的问题称之为易处理的。不能在多项式时间内解决的问题称之为难处理的，难处理的问题有时也称之为难解问题。复杂度与输入值成指数关系的问题属于难解问题。复杂度与输入值成指数关系的问题属于难解问题。依照求解问题所需的时间，复杂性理论也将各种依照求解问题所需的时间，复杂性理论也将各种问题区分成下面各类：问题区分成下面各类：（1）P问题：代表那些能够在多项式时间内可解的代表那些能够在多项式时间内可解的问题问题 易处理的，在确定性图灵机上多项式时间内可易处理的，在确定性图灵机上多项式时间内可计算计算（2）NP问题：多项式时间内可验证的问题多项式时间内可验证的问题 在不确定
6、性在不确定性Turing machineTuring machine上多项式时间内上多项式时间内可计算可计算,不确定性不确定性Turing machineTuring machine能进行猜测能进行猜测,即不确定性即不确定性Turing machineTuring machine如能猜出一个解的话如能猜出一个解的话,则确定性则确定性Turing machineTuring machine在多项式时间内可校验在多项式时间内可校验解的正确性解的正确性.（3）NP完全问题完全问题：是是NPNP问题中的一些问题中的一些特殊问题，特殊问题，NPNP中的所有问题都可以转换成中的所有问题都可以转换成NPNP
7、完全问题。换句话说，只要完全问题。换句话说，只要NPNP完全问题完全问题解决了，其他问题都可以解决。解决了，其他问题都可以解决。NPNP完全问完全问题是题是NPNP问题中最困难的问题。问题中最困难的问题。3、NP完全问题完全问题 （一）旅行商问题：旅行商问题：一名旅行商必须旅行到一名旅行商必须旅行到n n个不同个不同的城市，而他只有一箱汽油（即有一个他能旅行的最的城市，而他只有一箱汽油（即有一个他能旅行的最远距离）。有方法使他仅用一箱汽油而旅行到每个城远距离）。有方法使他仅用一箱汽油而旅行到每个城市恰好一次吗？（这是一般的汉密尔顿问题）市恰好一次吗？（这是一般的汉密尔顿问题）（二）三方匹配问题
8、：三方匹配问题：有一屋子的人，包括有一屋子的人，包括n n个男人，个男人，n n个女人和个女人和n n个牧师（祖父，犹太教士等等）。正常的个牧师（祖父，犹太教士等等）。正常的婚礼将包括一个男人、一个女人和一个愿主持仪式的婚礼将包括一个男人、一个女人和一个愿主持仪式的牧师。有了这样一张可能的三人一组的表，是否可能牧师。有了这样一张可能的三人一组的表，是否可能安排安排n n个婚礼，使每一个人要么和一个人结婚，要么个婚礼，使每一个人要么和一个人结婚，要么主持一个婚礼？主持一个婚礼？（三）整数分解问题（三）整数分解问题（四）背包问题（四）背包问题（五）离散对数问题（五）离散对数问题数论n数论是研究数性
9、质的一个数学分支，他同时也是密码学的基础学科之一。n全体整数所组成的集合通常用Z表示，即：Z=,-3,-2,-1,0,1,2,3,欧几里德（欧几里德（Euclid）算法）算法 欧几里德（欧几里德（Euclid）算法）算法 首先我们介绍整数的带余除法，它是整首先我们介绍整数的带余除法，它是整个数论的基础性定理之一。个数论的基础性定理之一。定理定理 1（带余除法）（带余除法）设Zba,且0b，那么存在一对整数 q 和 r，使得 rbqa且|0br (1)满足以上条件的整数 q 和 r 是唯一确定的。由(1)式显然有(a,b)=(b,r)对于两个整数对于两个整数a a和和b b，可以对其进，可以对其
10、进行分解来计算它们的最大公因数，但行分解来计算它们的最大公因数，但对于大整数而言，目前还没有足够有对于大整数而言，目前还没有足够有效的办法进行。实际中常用的用来计效的办法进行。实际中常用的用来计算两个数的最大公因数的算法称为欧算两个数的最大公因数的算法称为欧几里德算法。它的理论依据正是前面几里德算法。它的理论依据正是前面所述的带余除法。所述的带余除法。欧几里德算法的数学表述如下：欧几里德算法的数学表述如下：Zba,且0b，重复应用带余除法，我们有：nnnnnnnnnnnnrrrrqrrrrrqrrrrrqrrrrrqbbrrbqa1111112233231122121110,0,0,0,|0,
11、这时，0|21rrb，由于小于|b|的正整数只有有限个以及 1整除任一整数，所以这过程不能无限制地做下去，必定会出现某个 n，要么1,|1nnnrrr，要么1nr，此时余数 01nr。我们容易得到：我们容易得到：定理定理 2),(barn 这是因为nnnnnrrrrrrrrbba),(),(),(),(),(112211 另外，由(1)式我们可得：112232313121221110,0,0,|0,nnnnnnrrrqrrrrrqrrrrrqbrbrbqar 把前面的式子依次代入到后面的除式中，相应地消去1321,nrrrr，最后，nr可以表示为 a 和 b 的整系数线性组合，这时的系数即为使
12、 ax+by=(a,b)的系数。求(726,393),并求整数p和q使得 (726,393)=726p+393q n自反性n对称性n传递性除了上述结论外，以下性质也是经常用到的除了上述结论外，以下性质也是经常用到的习题习题 求求 51 mod 13,和 111 mod 13.求求 51 mod 17.例子：例子：例例 求21 mod 11.5mod33mod22mod1xxx 例例 利用中国剩余定理求解下列利用中国剩余定理求解下列 习题习题1.求(937,576),并求整数p和q使得 (937,576)=937p+576q2.求求 51 mod 17.3.求解:例子例子 设有下列同余式:x21
13、,x22,x23,x24 mod 5求解?因子分解因子分解（NPC:整数分解问题整数分解问题）在数论中，因子分解是一个古老而又困难的问题。现代的算法并不能测试出一个数所有可能的素因子。尽管如此，人们在这方面还是取得了不少的进展。目前，比较好的因子分解算法有：二次筛选法 数域筛法 椭圆曲线法 连式分解法 试除法 （一）因子分解法（一）因子分解法（二）模（二）模N的平方根的平方根 如果n是两个素数的乘积，那么计算模n的平方根的能力在计算上等价于对n进行因子分解的能力。换句话说，某人知道n的素因子，那么就能容易计算出一个数模n的平方根；这个计算已被证明与计算n的素因子一样困难。素数生成元素数生成元
14、两个大的素数相乘，据推测它是一个单向函数单向函数，因为这两个数数相乘得到一个数是容易的，但分解这个大数且恢复原来的两个大素数却是困难的。这样，就有办法利用这个单向函数设计一个陷门单向函陷门单向函数数。单向函数是求逆困难的函数，而Diffie和Hellman引入的概念陷门单向函数(Trapdoor One-way Function)，是在不知道陷门信息下求逆困难的函数，当陷门信息知道后，求逆是易于实现的。但如何给陷门单向函数下定义则难以解决，因为：(1)(1)陷门函数其实就不是单向函数，因为单向函数在任何条件下求逆都是困难的；(2)(2)陷门可能不止一个，通过实验，一个个陷门就可容易地找到逆。如
15、果陷门信息的保密性不强，则求逆不难。测试一个整数是否素数也是一个经常遇到的事，但它与因子分解相比要容易得多。公钥密码体制需要素数，而产生这些素数由多种方法。首先，我们将解决一些显尔易见的问题：（1 1）如果每个人都需要一个不同的素数，是否可以用光素数？（2 2）是否会有两个人偶然地选择了同样素数的情况呢？（一）Solovage-Strassen方法（不讲）（二）RabinMiller方法 这个算法是由Rabin发明的。事实上，这也是在NIST（国家标准和技术研究所）的DSS建议中推荐算法的一个简化版。首先选择一个待测试的随机数p。计算b，b是2整除p-1的次数（即2b是能整除p-1的2的最大幂
16、）。然后计算m，使得n=1+2bm。(1)选择一个随机数a，使得a小于p。(2)设j=0且z=ammodp。(3)如果z=0或z=p-1，那么p通过测试，可能是素数。(4)如果j0且z=1，那么p不是素数。(5)设j=j+1。如果jb且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之间的随
17、机数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完全问题之间的关系。*3、(1).已知一个所给的算法的复杂性是 ax7+3x3+sin(x)，则其计算复杂性T (2).已知一个所给的算法的复杂性是 en+an10，则其计算复杂性T (3).已知一个所给的算法的复杂性是 n!+n50，则其计算复杂性T*4、对于整数15和18，问：(1)它们是否互素？(2)试用欧几里德算法求它们的最大公因子并将其线性表示。
