第三章-数论算法-2.pptVIP

III数论算法-2 ρ方法 RSA例 例：取p=23,q=43，则 注意，取 ，则有 ，求得其逆 求得 以e为明钥，d为密钥 假定欲发送的明文为 将明文分段 RSA例续 加密 解密 连分数法实例 再多取一次 可得到分解 直接用浮点数得到的结果 整环 令R是一个含幺元的交换环。R中的元素c称为不可约(irreducible)的 （1）c非零元非单位元； （2）如果c=ab,则a或b为单位元 . R中的元素c称为素(prime)的 （1）c非零元非单位元； （2）如果p|ab,则p|a或p|b. 定义 均不可约 但 离散对数 给定数 ，其中p为素数g而为 的生成子，找到x满足 ， 称x为y关于g为基modp的离散对数。 Diffe-Hellman密钥交换算法 Diffe-Hellman密钥交换算法 Alice选取一个大的随机数x，发送给Bob Bob选取一个大的随机数y，发送给Alice Alice计算 s=Yx mod p Bob计算 t=Xy mod p s=t= gxy mod p 理论基础：离散对数计算的复杂性。 已知gx mod p，求x。 Baby Step/Giant Step Shanks提出 算法： Step1： Step2：计算序列 Step3：计算序列 Step4：寻找数使得在两个序列中均出现。此时 例 例：求解指数方程 应用GAUSS消去法找到线性不独立的行 最后六行的基系数全部为零，扩展部分则说明是由哪几个行相加得到：比如00010001000001（最后一行）：由行4，8，14相加得到。 1）1)10000001100000 即行1，8，9的积： 将各部分除以2得到：1320001 111002 代换后得到 无法将N分解 1）? 01110100000000 即行2，3，4，6的积： 将各部分除以2得到：1220101 020111 代换后得到 例如：p=13和g=2，则 总的时间 * Fermat的方法 连分数法 组合方程 数域筛法 RSA RSA: Rivest，Shamir，Adelman（1978年）基于大数分解的困难性 RSA算法的步骤如下： 随机选择两个大的秘密素数p与q 计算公开的模数r=p*q 计算秘密的欧拉函数φ(r)=(p-1)(q-1) 能选择一个与φ(r)互素的K，K可以定义为秘密密钥SK或公开密钥PK ， 计算模φ(r)即的K的乘法逆元素，这个量规定为秘密密钥SK或公开密钥PK， 它取决于第4步的选择。 将明文X自乘PK次幂后按r取模进行加密运算，从而产生密文Y： 将密文Y自乘SK次幂后按r取模进行解密运算，从而产生明文X 原理：若N为合数，则N至少有一个因子 自然算法 复杂度： Pollard的ρ方法 若d1，则d为非平凡的解，停止； 令 定义序列： 满足 对i做 Pollard的ρ方法实例 例：N=1387=19*73 X[ 10 9 8 7 6 5 4 3 2 1 i X[i] 1 2 5 26 677 620 202 582 297 829 X[2i] 2 26 620 582 829 ? ? ? ? ? y[i] 1 24 615 556 152 ? ? ? ? ? gcd 1 1 1 1 19 ? ? ? ? ? i 1 2 3 4 5 6 7 8 9 10 复杂度 命题：如果映射 被映射 代换，其中f为随机函数， 因子p可在 步 分解，即 Fermat的方法 求解 ，其中 由于每项均非 ，从而得到非平凡的解 比较小 Fermat的方法：找到q使 小的数是平方的可能性较大 Fermat的方法（续） 小的数a和b使 ，则 对固定的a和b，运行时间为 没有已知的一般方法！ Fermat的方法实例 例： N=561， ? 连分数法 对 继续上述过程： 对应的分数逼近（最优的），并且是交错的： 性质： 连分数法 的第i次逼近 寻找 得到： 例： 从而： 连分数法实例 组合方程 从而有分解式： 4633=41*133 ? 观察：N=4633 及 各自单独不能将N分解，但结合起来即可 如果满足上述要求，则记录它并再寻找新的Q，得到方程组： 组合方程--方法 对于数B