第三章数论算法2.ppt

III数论算法-2ρ方法Fermat的方法连分数法组合方程数域筛法RSARSA: 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的ρ方法 若d>1，则d为非平凡的解，停止；令定义序列：满足对i做Pollard的ρ方法实例例：N=1387=19*73i12345678910X[X[I]12526677620202582297829X[2i]226620582829     y[I]124615556152     gcd111119     i12345678910复杂度命题：如果映射被映射代换，其中f为随机函数，因子P可在即 Fermat的方法 求解，其中由于每项均非，从而得到非平凡的解比较小Fermat的方法：找到q使小的数是平方的可能性较大Fermat的方法（续）小的数a和b使，则对固定的a和b，运行时间为没有已知的一般方法！ Fermat的方法实例例： N=561， 连分数法 对继续上述过程：对应的分数逼近（最优的），并且是交错的：性质：连分数法的第i次逼近 寻找得到：例：从而：连分数法实例组合方程 从而有分解式：4633=41*133 观察：N=4663及各自单独不能将N分解，但结合起来即可如果满足上述要求，则记录它并再寻找新的Q，得到方程组：组合方程--方法对于数B，所有小于B的素数及“-1”构成的基，即因子基(Factor Base)。

方法：生成数Q使得的绝对值比较小，能够在因子基上分解选择合适的集合S，将上述方程相乘，得到当为偶数时，式右亦为平方项！找一个子集满足上述性质，即MOD2代数组合方程--方法如果s比列数大，则一定有解，可以用GAUSS消去法求解但不能保证出现平凡解！组合方程—算法1）找到所有素数≤B 个这样的Q 2）寻找数形如的Q，其中a和b较小，检查的因子是否为的素数找3）通过Gauss消去法找到一个子集S使得诸式的积形如 4）如果找到非平凡的解，终止；否则，则再找一新的Q进行步骤3，直到找到非平凡的解例：N=85907，B=10组合方程—例Q形如 其中a较小在因子基{-1，2，3，5，7}上分解 找到若干Q如下 有解：行1，3，4之和为（0  0  0  0  0） 从而 数域筛法(Number field Sieve) 目前最好的方法！ 的数在代数域和整数域上同时进行分解；与前面相同，搜集有用的成功分解，再找MOD2的相关性最初该算法用于分解形如的N，其中a、b和c较小；比如令，则该算法有一个分解基，形如：，可以视作代数数（Algerabic Number）视为代数整数时对小范数为素的对于形如1999年一个151位数被成功分解 如：As of November 2002, the record-holding SNFS factorization is the 233-digit factorization of 2^773+1 and the record-holding GNFS factorization is the 158-digit factorization of a divisor of 2^953+1. Although 2^953+1 is of the special form required for SNFS, it was out of the reach of current computational resources. Various smaller factors of it had been discovered leaving the c158 co-factor which was split using GNFS. 使例：分解N=20437寻找多项式和一个数，对于加法和代数数的环（不一定为整环）。

利用可将上面两个数的积化成同样形式的另外的同构将用m代替，构成了一个代数整数和，则，的基m方法：即将N表成m的多项式：构造得到多项式的整数分别分解：构成求解将形如的整数和，其中常规整数的标准基： 代数数的基：分别分解及而对应前者对应指数，后者对应代数数每一接受的积构成一个指数的行，因子基中的每一列对应一个因子0 3 0 0 1 0 0   0 1 0 0 0 1对多组这样的数，构成如下的矩阵：另一例子 关系，建立MOD2的矩阵：求解一个应用GAUSS消去法找到线性不独立的行最后六行的基系数全部为零，扩展部分则说明是由哪几个行相加得到：比如00010001000001（最后一行）：由行4，8，14相加得到1）1)10000001100000    即行1，8，9的积：将各部分除以2得到：1320001  111002代换后得到 无法将N分解 1）  01110100000000 即行2，3，4，6的积：将各部分除以2得到：1220101  020111代换后得到 。