小学学的素数既有趣又有用还很南( 二 ) _小知识

我们知道，任何一个自然数都可以分解为素数的乘积，如果不计因数的次序，分解形式是唯一的。这叫做算术基本定理。但是将一个大整数分解却没有一个简单易用的好方法，只能用较小的素数一个一个去试除，耗时极大。如果用计算机来分解一个100位的数字，所花的时间要以万年计。可是将两个100位的数字相乘，对计算机却十分容易。美国数学家就利用了这一点发明了编制容易而破译难的密码体系，这种编码方式以三位发明者姓氏的首字母命名为RSA码。下面我们就来简单说明这种密码是怎么巧妙利用素数来构建的。
RSA密码的加密解密算法
下面讲解RSA密码的算法原理，我们可以通过如下8步来进行加密和解密，具体如下：
（1）选择一对不同的、足够大的素数p、q (p, q严加保密，不让任何人知道，p、q越大，也越难破解)；
（2）计算n=p*q；
（3）计算f(n)=(p-1)*(q-1) ；
（4）找一个与f(n)互质的数e，满足 1
（5）计算d，使得d*e ≡ 1 mod f(n)；
这里 ≡ 是数论中表示同余的符号。公式中 ≡ 符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管f(n)取什么值，符号右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积取模运算后的结果也必须等于1 。这就需要计算出d的值，让这个同余等式能够成立，一般可以通过逐个尝试的方法找到可行的d；
（6）公钥KU=(e, n)(公钥就是可以公开的，大家都可以知道)，私钥KR=(d,n)(私钥需要自己保密，用于破解密码用)；
（7）对于0至n-1之间的任意一个整数M，可以这样加密：C≡M^e(mod n)(这里M^e是指M的e次方，下面类似)，C就是需要传输的信息，将C给到你想传递信息的人；
（8）接收人收到信息C后，通过计算D=C^d(mod n)，就获得了原来的信息M，即D=M；
如果传输的信息很多，可以利用0、1、2、......、n-1 对信息进行编码(比如需要传输的是英文单词，可以对每一个字母编码，可以根据字母顺序编码，a->1、b->2、c->3、以此类推) 。下面我们讲个例子让大家更好地理解上面的原理的正确性。对这个感兴趣的读者也可以自己尝试证明一下为什么这个密码体系是对的。
RSA密码的简单例子
令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3(3与20互质)，则e×d≡1 mod f(n)，即3×d≡1 mod 20，这时可以取d=7，满足e×d≡1 mod f(n) 。这时公钥为：KU =(e,n)=(3,33)，私钥为：KR =(d, n)=(7,33) 。
我们可以用这套密码体系来传输英文字母，用字母的顺序对应的数字来代表该字母。比如如果我们要传输字母y，可以这样进行：字母y在字母表中的序号是25，就用25来代替y，通过加密计算C≡M^e(mod n)≡25^3(mod 33) = 15625(mod 33)=16 。你可以将16传给收信息的人，收信息的人收到16后，用D=C^d(mod n)来解密，具体计算是D=C^d(mod n) = 16 ^7(mod 33) = 268435456(mod 33) = 25，这就是y对应的序号，因此解密过程成功。
作者曾经设计的一个账号体系也用到了素数的知识，原理跟上面的RSA比较类似，大致意识是先确定账号的容量m ，即这个账号系统一共支持多少个账号，找一个素数p与m互质，找另个一个素数q，满足 p*q mod m =1(我的这个方法不要求p是素数，只要跟m互质就可以了，当然如果p是素数，只要不是m的因子，是一定满足跟m互质的条件的) 。
我的这个方法设计非常精巧，也比较简单，它最大的价值是竞争对手通过注册几个账号是无法猜测出账号的生成规律的，从而无法知道你的产品有多少用户。下面我们来讲讲这个方法的具体实现原理。
每个用户根据他注册的次序给他赋予一个整数值k，即这个用户是第k个注册的，采用下面图2的算法获得该用户的账号(即后面的u1、u2、u3等等) 。同时我们可以采用图3的算法根据用户的账号获得用户是第几个注册的用户。下面a的目的是为了让所有用户账号位数一样，比如如果a取9999999(9百99万9999)，m取90000000(9千万)，那么用户的账号范围就是10000000(1千万)到99999999(9999万9999) 。大家可以看到这里面生成账号的过程类似RSA的加密过程，从账号获得用户注册顺序的过程类似RSA的解密过程。

文章插图
图2：用户账号生成算法(类似于RSA的加密过程)

文章插图
图3：从用户账号获得用户的序号(类似于RSA的解密过程)

素数在人类生活和自然界中的应用应该还非常多，等待聪明的人类来挖掘和探索。有兴趣的读者也可以结合素数的性质多思考，看是否能够找到素数的巧妙应用。