斯坦福大学密码学-数论简介 10

感觉明天就可以结束了。。。。加油！！！！！！！学校什么时候解封，要疯了。。。。。。。

ppt链接：

Notation

背景。

一些符号。

模运算。

最大公因数。

模逆。

模逆存在的条件。

解线性同余方程。

费马和欧拉

回顾。

最后 n=log \ N 。

费马定理。求逆算法与欧几里得相比，只限于质数模，而且更低效。

费马定理应用。迭代几百次就够了。

生成元。循环群。

生成群。

拉格朗日定理。

欧拉定理。

计算模e次方根

计算-简单情况。 e与p-1互质。

当e与p-1不互质时，e为2时。平方根。

二次剩余。

欧拉定理。勒让德符号。判断x是否为 Z_p 的二次剩余？

解 Z_p 中的二次方程。仅当 Z_p 中有平方根。

计算合数模的e次方根。

需要因子分解合数N，再分别计算。

计算大整数的模

大整数的表示。

加减乘除时间复杂度。karatsuba的算法经常被使用。最好的乘法是n·logn，不实用，大数据才有效。

指数。

重复平方算法。

运行时间。

模运算中的难题

简单的问题。

离散对数问题。质数模的难题。

不只是 (Z_p)^* , 在有限循环群 G 中即可。

注意：椭圆曲线上的离散对数问题比群 (Z_p)^* 上的离散对数问题要困难。

计算离散对数有一个亚指数算法，一个n位的质数，运行时间的指数是n的立方根。

对于椭圆曲线群，运行时间的 2^{(n/2)} ，一个合适的指数时间算法。

椭圆曲线大小（质数模的大小）是对称密钥大小两倍的原因是，指数里的因子2 ，必须将椭圆曲线群的大小扩大一倍以获得 2^n 的运行时间。

离散对数的应用：抗碰撞

y1-y0的模q的逆，然后把结果与x0-x1相乘。

为什么q是质数？因为 y1-y0始终可逆。y1不可能等于y0。

不太用，相对慢。

合数模的难题。

大数分解问题现状。

目前最好的算法叫做数域筛法NFS,但是运行时间的指数级的，指数是立方根次的，所以这就是为什么合数要非常大才难分解。

这章本科学过了信安数学基础，相对较容易一些。。。。。。。