返回首页

数论算法

数论主要研究的是整数的性质,数论算法也是一块非常有意思的内容.数论的算法一般并不深奥,但是很精妙(当然,有些算法的背后有着很深刻的问题,比如Miller-Rabin测试背后的Generalized Riemann Hypothesis).

数论的相当多算法都已经被研究了很长时间了,比如质因数分解(而它到现在为止都没有给出对于大数据有效的算法.)数论的问题,是非常深刻的,而且影响着数学的方方面面.

有一点要特别注意,那就是这里所说的数论算法,事实上包括了一些更大的领域的内容,如组合学之类的.

数论历史[主页面]

警告:此页面尚未添加,本子标题的存在仅为了维持文章结构.

最大公约数[主页面]

最大公约数是数论中一个非常简单的问题.在古希腊,欧几里得时代就给出了一个有效算法(那个时候当然还没有复杂度理论),即辗转相除法,这个算法时间复杂度$\mathtt{O}(n^2\log{n})$.

素性测试[主页面]

素性测试是一个非常重要的问题,不管是在应用上或者是在理论上.素性测试中的一个重要的里程碑就是AKS算法,一个被证明是多项式时间的确定性算法.虽然实际使用中有一些更好的方法(比如确定性Miller-Rabin(GRH),亚指数的APR-CL).这些算法需要讲很长一段时间.显然这不是问题.

质因数分解[主页面]

质因数分解的困难性可以从一些地方看出来,如现在还没有多项式的质因数分解算法.已知的最好的算法是广数域筛法(General Field Sieve).随着对于质因数分解的算法的研究的不断深入,由于一种广泛运用着的不对称加密方式:RSA加密,这个以质因数分解的困难性作为它安全的保障的算法,安全性已经岌岌可危了.人类的进步总是要伴随着某些损失,不是么?