高速乘方计算

比如[tex]x^{256}=(((((((x^2)^2)^2)^2)^2)^2)^2)^2[/tex]，因此只要做8次乘法就可以完成了。再比如[tex]x^{290}=x^{256}\cdot x^{32}\cdot x^2[/tex]，所以我们只需要在计算[tex]x^{256}[/tex]的过程中保留下[tex]x^{32}[/tex]和[tex]x^2[/tex]的值，最后把它们乘起来就可以了。一般来说，计算[tex]x^k[/tex]只需要做[tex]\log_2k[/tex]次左右的乘法。

“工业水准素数”

费马小定理说，如果p是素数，a和p互素，则[tex]a^{p-1}\equiv 1[/tex](mod p)。如上所述乘方计算是非常快的，所以这给大致判定一个数的素性提供了一个非常方便的方法。如果一个数n满足[tex]a^{n-1}\equiv 1[/tex](mod n)，则称n为“以a为底的拟素数”。

是拟素数而不是素数的数虽然不是很多，但也不算少。特别是，还有一种数叫做卡迈克尔数，这种数不是素数，但是以任意和它互素的一个数为底它都是拟素数。最小的一个卡迈克尔数是561=3*11*17。

但是事情还有改进的余地。如果p是奇素数，设[tex]p-1=2^st[/tex]，则[tex]a^{p-1}\equiv 1[/tex](mod p)也就是说[tex]a^{2^st}-1=(a^t-1)(a^t+1)(a^{2t}+1)\cdots(a^{2^{s-1}t}+1)[/tex]是p的倍数。如果p真的是素数，那它当然整除这乘积的某一项；但如果p只是拟素数而非素数，则有很大的可能p的因子分散在这个乘积的几项里。因此注目于这个特征可以让我们筛选掉大部分不是素数却是拟素数的数。对于一个奇数[tex]n=2^st+1[/tex]，如果n整除乘积[tex]a^{2^st}-1=(a^t-1)(a^t+1)(a^{2t}+1)\cdots(a^{2^{s-1}t}+1)[/tex]的某一项，则称n为“以a为底的强拟素数”。强拟素数判定可以在与拟素数判定相当的时间内完成：我们先计算[tex]a^t[/tex]，如果[tex]a^t\equiv \pm 1[/tex](mod n)那当然通过；否则就接着依次计算[tex]a^{2t},a^{4t},\ldots[/tex]直到对于某个i有[tex]a^{2^it}\equiv -1[/tex](mod n)为止；如果一直算到i=s-1了这个[tex]a^{2^it}[/tex]模n都不等于-1，那就是不通过。

“强卡迈克尔数”是不存在的。如果一个数不是素数，那对于一个随机选择的底有大于一半的可能性它通不过强拟素数判定。[tex]25\times 10^9[/tex]以内以2,3,5,7为底的强拟素数而不是素数的只有一个：3215031751=151*751*28351。因此这是一个非常高信赖的判别方法，以2,3,5,7为底的强拟素数有时被称为“工业水准素数”。通常在因数分解一个数之前都要用强拟素数判定来确认它确实是一个合数，在判定素性以前也都要用强拟素数判定来推测它大概确实是一个素数。

费马数和梅森数

形如[tex]2^n+1[/tex]的数如果是素数，那么n一定是2的幂（如果n有奇数的因数，那么[tex]x^n+1[/tex]就可以因式分解了）。而形如[tex]2^n-1[/tex]的数如果是素数，那n一定是素数（[tex]x^{ab}-1[/tex]有[tex]x^{a}-1[/tex]作为因子）。我们把形如[tex]2^{2^k}+1[/tex]的数称为费马数，把形如[tex]2^p-1[/tex]（p是素数）的数称为梅森数。费马数和梅森数都有非常简单的素性判定法。

(Pepin’s test)[tex]F(k)=2^{2^k}+1[/tex]是素数，当且仅当[tex]3^{\frac{F(k)-1}{2}}\equiv -1[/tex](mod F(k))。

首先如果F(k)是素数，那么只要3不是F(k)的二次剩余，就有[tex]3^{\frac{F(k)-1}{2}}\equiv -1[/tex](mod F(k))（欧拉准则）。而我们确实知道3不是F(k)的二次剩余，是因为有二次互反律。
反之，设F(k)有素因子q。设a是满足[tex]3^a\equiv 1[/tex](mod q)的最小的自然数，则由费马小定理知a<=q-1。另一方面，由[tex]3^{\frac{F(k)-1}{2}}\equiv -1[/tex](mod F(k))当然有[tex]3^{F(k)-1}\equiv 1[/tex](mod F(k))，而q是F(k)的因子，所以[tex]3^{F(k)-1}\equiv 1[/tex](mod q)。这样一来a必然是F(k)-1的约数。F(k)-1=[tex]2^{2^k}[/tex]只含有素因子2，而由[tex]3^{\frac{F(k)-1}{2}}\equiv -1[/tex](mod F(k))知道[tex]3^{(F(k)-1)/2}[/tex]模q一定不等于1，所以a只能等于F(k)-1。所以F(k)-1=a<=q-1，于是F(k)=q。 容易看出在这里3并没有什么特别，只要不是F(k)的二次剩余，选择其他的底也是可以的。如果你不喜欢3，也可以用（比如）5来代替。 梅森数的素性判定与费马数完全类似，只不过需要稍微高深一点的知识。首先是一个类似费马小定理的定理： 设p是奇素数，D不是p的二次剩余。令[tex](V_1+U_1\sqrt{D})^i\equiv V_i+U_i\sqrt{D}[/tex](mod p)，则[tex]U_{p+1}\equiv 0[/tex](mod p)。 这是因为[tex](V_1+U_1\sqrt{D})^p\equiv V_1^p+U_1^pD^{\frac{p-1}{2}}\sqrt{D}\equiv V_1-U_1\sqrt{D}[/tex](mod p)。（用二项展开就得到第一个等式，而由费马小定理[tex]V_1^p\equiv V_1,U_1^p\equiv U_1[/tex](mod p)，由欧拉准则[tex]D^{\frac{p-1}{2}}\equiv -1[/tex]。）所以[tex](V_1+U_1\sqrt{D})^{p+1}\equiv V_1^2-U_1^2D[/tex](mod p)。 接着是一个类似欧拉准则的东西： 在前一个定理的前提下，再假定[tex]V_1^2-U_1^2D[/tex]也不是p的二次剩余，则有[tex]V_{\frac{p+1}{2}}\equiv 0[/tex](mod p)。 这是因为[tex](V_{\frac{p+1}{2}}+U_{\frac{p+1}{2}}\sqrt{D})^2\equiv V_{p+1}+U_{p+1}\sqrt{D}[/tex](mod p)，所以[tex]0\equiv U_{p+1}\equiv 2U_{\frac{p+1}{2}}V_{\frac{p+1}{2}}[/tex](mod p)，所以要么[tex]U_{\frac{p+1}{2}}\equiv 0[/tex](mod p)，要么[tex]V_{\frac{p+1}{2}}\equiv 0[/tex](mod p)。现在[tex]V_{p+1}\equiv V_1^2-U_1^2D[/tex](mod p)不是p的二次剩余，所以[tex]U_{\frac{p+1}{2}}[/tex]模p不能为0（否则[tex]V_{p+1}[/tex]模p就是[tex]V_{\frac{p+1}{2}}[/tex]的平方了），于是[tex]V_{\frac{p+1}{2}}\equiv 0[/tex](mod p)。 (Lucas-Lehmer test)令[tex]M(k)=2^k-1[/tex]，[tex](1+\sqrt{3})^i\equiv x_i+y_i\sqrt{3}[/tex](mod M(k))，则M(k)是素数当且仅当[tex]x_{\frac{M(k)+1}{2}}\equiv 0[/tex](mod M(k))。 首先如果M(k)是素数，借助二次互反律就可以知道3和-2都不是M(k)的二次剩余。所以这时确实有[tex]x_{\frac{M(k)+1}{2}}\equiv 0[/tex](mod M(k))。 反之，设M(k)有素因子q。设a是满足[tex]y_a\equiv 0[/tex](mod q)的最小的自然数，我们已经知道a<=q+1。另一方面，由[tex]x_{\frac{M(k)+1}{2}}\equiv 0[/tex](mod M(k))当然有[tex]y_{M(k)+1}\equiv 0[/tex](mod M(k))，而q是M(k)的因子，所以[tex]y_{M(k)+1}\equiv 0[/tex](mod q)。这样一来a必然是M(k)+1的约数。M(k)+1=[tex]2^{k}[/tex]只含有素因子2，而由[tex]x_{\frac{M(k)+1}{2}}\equiv 0[/tex](mod M(k))知道[tex]y_{\frac{M(k)+1}{2}}[/tex]模q一定不等于0（否则的话就有[tex](1+\sqrt{3})^{\frac{M(k)+1}{2}}\equiv x_{\frac{M(k)+1}{2}}+y_{\frac{M(k)+1}{2}}\sqrt{3}\equiv 0[/tex](mod q)，于是[tex]1+\sqrt{3}\equiv 0[/tex](mod q)，这当然是不可能的），所以a只能等于M(k)+1。所以M(k)+1=a<=q+1，于是M(k)=q。 关于[tex](1+\sqrt{3})^i[/tex]的计算，还可以稍微简化一点。注意[tex](1+\sqrt{3})^2=2(2+\sqrt{3})[/tex]，而[tex]2+\sqrt{3}[/tex]的幂计算起来相对比较容易一些。这是因为[tex](2+\sqrt{3})(2-\sqrt{3})=1[/tex]，所以如果设[tex](2+\sqrt{3})^i= s_i+t_i\sqrt{3}[/tex]，我们有[tex]s_i^2-3t_i^2=(2+\sqrt{3})^i(2-\sqrt{3})^i=1[/tex]。所以[tex]s_{2i}=s_i^2+3t_i^2=2s_i^2-1[/tex]。 很奇怪我们目前所知的最大素数是梅森数而不是费马数。而且网上有发动人寻找梅森素数的，倒是没有听说有找费马素数的。大概因为费马数比梅森数要少（[tex]2^{2^k}+1[/tex]实在是变大得太快了），而且大部分都是合数吧。我们仍然不知道费马素数或者梅森素数是否有无穷多个，但似乎有人猜前者是“没有”，后者是“有”的。 离散对数问题

如前所述我们可以很快算出x的k次方=y，但是给定x和y，想要知道x的几次方是y，在很多时候并不容易。比如我们怎么才能知道7模17等于3的11次方呢？这称为离散对数问题，所谓离散是指我们通常考虑的是有限群。

事实上在某种意义上来说RSA加密算法的安全性也依赖于离散对数问题的困难性。如果我们有一种一般的解决离散对数问题的方法，那只要随机选一个数字x，用RSA公开的加密密匙a加密x得到[tex]x^a[/tex](mod n)，然后（不依赖n的因数分解）算出一个r使得[tex](x^a)^r\equiv x[/tex](mod n)，那么这个r有很大的可能性就是解密密匙。即使不是，也和解密密匙密切相关。

所以有直接利用离散对数问题的困难性进行保密通信的方法也就不奇怪了。假如A和B要进行通信，他们约定好一个群和这个群里的一个元x。A在心里想一个数a，这个a不要告诉任何人。同样的B也在心里想一个数b，也不要告诉任何人。A把[tex]x^a[/tex]告诉B，B把[tex]x^b[/tex]告诉A。A收到[tex]x^b[/tex]以后计算[tex](x^b)^a[/tex]，B收到[tex]x^a[/tex]以后计算[tex](x^a)^b[/tex]。这样A和B手里都有了同一个数[tex](x^b)^a=(x^a)^b[/tex]，把这个做为密匙（利用任何一种不公开密匙的加密算法）加密他们想要传递的信息就可以了。如果有黑客窃听A和B之间的通信，他可以知道A和B约定的群，群里的那个元x，[tex]x^a[/tex]还有[tex]x^b[/tex]。但是如果这个群的离散对数问题是很困难的，黑客就很难从[tex]x^a[/tex]和[tex]x^b[/tex]中还原a和b，也就很难知道密匙[tex]x^{ab}[/tex]。

至于这个约定的群，似乎现在大家都在谈论椭圆曲线群。椭圆曲线是由方程[tex]y^2=x^3+ax+b[/tex]定义的曲线（要求[tex]4a^3+27b^2\neq 0[/tex]，这个条件保证三次方程[tex]x^3+ax+b=z[/tex]有不同的根），这个曲线有个很特别的性质就是曲线上任意两点的连线都通过曲线上的第三个点。设曲线上的两点为[tex](x_1,y_1)[/tex]和[tex](x_2,y_2)[/tex]，通过这两点的直线（如果这两个点相同，则理解为过那个点的切线）交椭圆曲线于第三点[tex](x_3,y_3)[/tex]，则定义[tex](x_1,y_1)\cdot (x_2,y_2)=(x_3,-y_3)[/tex]。具体写出来，
[tex]x_3 = \lambda^2 – x_1 – x_2[/tex]
[tex]y_3 = \lambda (x_3 – x_1) + y_1[/tex]
其中[tex]\lambda[/tex]是直线的斜率，当[tex](x_1,y_1)[/tex]和[tex](x_2,y_2)[/tex]不同的时候[tex]\lambda =\frac{y_1-y_2}{x_1-x_2}[/tex]；当[tex](x_1,y_1)[/tex]和[tex](x_2,y_2)[/tex]相同的时候[tex]\lambda =\frac{3x_1^2+a}{2y_1}[/tex]。如果[tex]\lambda[/tex]的分母为0，则[tex](x_3,y_3)[/tex]理解为无穷远点。椭圆曲线上的点关于这个乘法做成可换群，其单位元是无穷远点，(x,y)的逆元是(x,-y)。

（据说），Microsoft  Digital  Rights  Management  (MS-DRM)  V.2  里用的椭圆曲线是在一个模
89abcdef012345672718281831415926141424f7
的域上定义的
a=37a5abccd277bce87632ff3d4780c009ebe41497
b=0dd8dabf725e2f3228e85f1ad78fdedf9328239e
的椭圆曲线。约定的点的x坐标为
8723947fd6a3a1e53510c07dba38daf0109fa120
y坐标为
445744911075522d8c3c5856d4ed7acda379936f
这个点生成的子群的阶是
89abcdef012345672716b26eec14904428c2a675
（都是十六进制数。呵呵，当个稀罕看吧）

题外话

本来想系统地写一写因数分解和素数判定的，维基百科在数论方面的内容实在不怎么样。但是尝试了一下决定放弃了，就算写出来大概也没人愿意看。代数就是结论漂亮过程繁杂（好吧，其实整个数学都是这样），只好写点可以速成的。唉。