信息论与数学基础课件

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