数论总结

最近在教室里闲得蛋疼于是翻算法导论学了点数论

那么来总结一下:

1.中国余数定理

这个似乎没什么卵用啊 不过还是学了一下

就是说有一个数x模n个数(两两互质)

$$a_1,a_2,a_3…a_n$$

得到的结果分别为

$$b_1,b_2,b_3…b_n$$

已知所有a和所有b 求x

这个还是比较简单的

先令

$$n=\begin{matrix} \prod_{i=1}^n a_i \end{matrix}$$

然后

$$ c_i = \frac{n}{a_i} \left[ \left(\frac{n}{a_i} \right)^{-1}\bmod\ a_i \right]$$

最后

$$x \equiv \begin{matrix} \sum_{i=1}^n b_i c_i \end{matrix} \pmod n$$

貌似很简单对吧

举个孙子的例子:

找出所有整数,被3、5、7整除时余数分别为2、3、2

那么先算出n=105

然后算出

$$c_1=35 \times 2=70$$

$$c_1=21 \times 1=21$$

$$c_1=15 \times 1=15$$

那么

$$x=(70 \times 2 + 21 \times 3 + 15 \times 2) \bmod 105 =23$$

解释:(不记得了 自己看去233)

看到后面那个%105 所以在23上可以任意加105 都可以满足

【看不懂多脑补一下就懂了】

2.RSA公钥加密系统

这个似乎更没有什么卵用了

就是弄一个公钥一个密钥 两个互为反函数,公钥任何人都可以看到,给对方发信息就是用对方公钥加密了丢给他,然后他再用密钥解密,或者用自己的密钥加密做数字签名防止伪造,这样就可以防截取/防伪造。

生成公钥+密钥的算法:

1.首先选两个大素数p,q,那么n=pq

2.选取一个与Φ(n)互质的小奇数e

3.计算

$$d=e^{-1} \bmod \Phi(n)$$

那么公钥为(e,n) 密钥为(d,n)

那么将M用公钥加密:

$$P(M)=M^e \bmod n$$

解密:

$$M=S(P(M))=M^{ed} \bmod n$$

可以证明是对的(所以我就不证了XD)

3.Miller_Rabin素数测试

首先我们要知道费马小定理:

当n为质数时,

$$ a^{n-1} \equiv 1 \pmod n $$

其中

$$ a \in Z_n^+$$

那么命题:当n满足上式时 n为素数

也【几乎】成立

所以最简单的方法就是a取2把n带进去试试

不过有几个很鬼的数叫Carmichael数,虽然是合数,不过满足费马小定理那个式子

所以就有了Miller_Rabin判素算法:

1.随机选x个数

$$a_1,a_2,a_3…a_n$$

2.将n-1表示为

$$u2^t$$

(位运算很简单)

3.对于选出的每个a

(1)算出

$${a_i}^u \bmod n$$

然后模n平方t次,如果平方时发现了1的非平凡平方根则返回合数

(2)最后结果如果不为1返回合数

4.返回素数

 

【名词解释】1的非平凡平方根:1的平凡平方根为1和-1,在模n下可能会出现另外的数k使得

$$k^2 \equiv 1 \pmod n$$

则k为模n下1的非平凡平方根

 

这个就几乎不可能会萎了

复杂度很小 貌似是O(β)

代码:

4.Pollard_rho因子分解

这个算法和上一个一样 也不能保证正确。。还不能保证时间

不过复杂度O(√√n)还是很诱人的

【其实我也不懂 背背代码好了】

说点什么

您将是第一位评论人!

提醒
wpDiscuz