密码学的数学基础.ppt

本章授课提纲 （1）素数判定概述 （2）米勒－拉宾素数判定 （3）因数分解概述 素数判定概述 素数在公钥密码体制中的重要性 公开密钥密码体制中需要大的素数，如基于因数分解困难性的RSA体制的密钥就是两个非常大的素数的乘积，如果素数选择过小，则分解它们是容易的，因而整个RSA密码体制系统就不安全。ElGamal是基于离散对数求解困难的公钥密码体制，同样需要产生非常大的素数，以保证密码体制的安全。 这种非常大的素数通常也叫强素数 素数判定概述 在长度为512位或略短一些的数中，有超过10151个素数。宇宙中仅有1077个原子，如果宇宙中从诞生到现在为止，每一微秒都需要10亿个新的素数，那么总共需要10109个素数，现在仍然剩下约10151个512位的素数。 素数有多少个呢？ 素数判定概述 素数定理给出一种估计素数个数的方法： 设π(x)是小于x的素数的个数，则 π(x)≈x/lnx 应用举例： 64位二进制表示的素数的个数为 264/ln264-263/ln263≈2.05×1017个 素数定理 素数判定概述 （1）素数分布极不规则 （2）素数越大，其分布越稀疏。因为整数越大，比它小的素数也越多，从而被比它小的素数整除的概率也越大。 平均而言，在64，128，256位中任选约23，46，92次奇数，即可获得一素数。 素数的分布特点 素数判定概述 欧拉定理是素数判定的必要非充分条件 欧拉定理：对于任何互素的两个整数a和n，有 aφ(n)≡1(mod n) 如果n=p是素数，则有ap-1≡1(mod p) 但是，反过来如果ap-1≡1(mod p)，并不能推出p是素数 素数判定概述 二次探测定理是素数判定的必要非充分条件 二次探测定理：如果p是一个素数，且0xp，则方程x2?1(mod p)的解为x=1，p-1。 如果(p-1)2?1(mod p)，那么p很有可能是素数，但仍然不能肯定p就是素数。 像这样，满足欧拉定理和二次探测定理，但不是素数的合数，常被称为“伪素数” 素数判定概述 Wilson定理是素数判定的充要条件 Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!? -1(mod n)。 虽然是充要条件，且Wilson 定理有很高的理论价值。但实际用于素数测试所需要计算量太大（计算量比试除法还多）,无法实现对较大素数的测试。 素数判定概述 （1）原始的确定性算法，如试除法和筛法 （2）概率算法，如Lehmann素性判定算法和Miller-Rabin素性判定算法 （3）印度学者的多项式确定算法 素数判定算法概述 素数判定概述 试除法：对于待检测的整数n依次用从1到sqrt(n)的整数来试除，看是否被整除。 素数判定算法概述——试除法和筛法 筛法：依次去除2、3、5、7等的倍数，看n是否被剩下来。 这两个方法是寻找素数的确定性算法，由于复杂度较高，对于较大的整数（如256位和512位），为了判定它是否为素数，所需时间为天文数字。 素数判定概述 素数判定算法概述——概率算法 Lehmann测试 对于给定的数p，随机选取ap， 计算a(p－1)/2 mod p， 如果它不等于1或－1，则p不是素数 否则，它不是素数的可能性最多是50% 于是 a就是p可能是素数的一个证据 多找几个证据 比如t个，则p不是素数的可能性至多0.5t t=10时，p是素数的概率0.99999 素数判定概述 素数判定算法概述——概率算法 Lehmann判定算法和Miller-Rabin素性判定算法都是概率算法，即以一定概率保证判定的对象为素数，但不能百分百保证。但这两个算法都是具有多项式时间的算法，在实际中得到广泛使用。 素数判定概述 2002年，也就是Miller-Rabin方法提出的10多年后，三个印度人终于提出了复杂度为P的确定性的素性测试算法。这个算法，也就是所谓的AKS算法，可以在多项式时间里确定的判断一个数是否是素数。 素数判定算法概述——印度的多项式确定算法 素数判定概述 素数判定算法概述——印度的AKS算法 素数判定概述 （1）产生一个k位随机正整数n（用二进制表示），最高位和最低位均为1，中间位随机选择0或1。 （2）检查以确保n不被任何小的素数整除。一般用小于2000的素数去试除n，如果能够整除，需要重新产生n；否则执行“素数判定”程序。事实上，只要验证3，5，7，就能排除54%的奇数。 （3）对n执行“素数判定”，即选用某种素数判定算法，对n做进一步的判定，确定n是否为素数。 产生大素数的一般流程 素数判定概述 历史上找到的最大的素数 本讲授课提纲 （1）素数判定概述 （2）米勒－拉宾素数判定 （3）因