质数是什么意思详解（质数竟然有这么有用？）

鬼魅的质数

什么是质数？小学数学就开始学习的一个概念。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。质数对于普通人而言是非常不解，因为不解，所以学生学习时会想数学家怎么那么无聊，发明这些概念，让他们痛苦不堪，但是对于数学家而言有着太过强烈的吸引力，因为，她实在太过鬼魅。

一百多年前，数学家哈代也没觉得质数有用，那么质数到底有没有用呢？在回答这个问题之前，我们先看一下质数到底鬼魅在什么地方，这得从找通项式开始说起。比如：1，3，5，7......,问这个数列第n项数是什么？很简单，可以用2n-1表示，那么任意一项是什么数可以迅速算出来。再比如：1、1、2、3、5、8、13、21、34……这个数列仔细看看，也能看出其中的端倪，即第三个数是前两个数字之和，这就是大名鼎鼎的斐波那契数列，它的通项式，我们也可以通过这个通项式迅速找到第n项的数字。

但是，如果有人问2，3，5，7，11......这个数列第n项是什么数字，就算集有史以来所有数学家的才智对这个问题的答案也无能为力，这就是质数为什么如此吸引数学家的原因，要找到第n个质数，只有暴力求解一条路了。暴力求解？比如，验证5是否为质数，从1开始寻找，5除以1能整除，5除以2不行，一直计算到5除以5，需要计算5次。看起来计算机似乎非常擅长干这件事。比如，我们通过这么一段程序验证一个数是否为质数，这一段只是为了演示，不懂程序的可以跳过，直接往下面看，不影响我们的阅读。数字比较小的时候似乎是可以，但是，如果是一个有着100位数字的数字需要验证呢？估算一下需要多久，100位数字，开方后大概需要循环次，最快的计算机，那也得要几年时间。

boolean isPrime = number > 0;
// 计算number的平方根为k，可以减少一半的计算量
int k = (int) Math.sqrt(number);
for (int i = 2; i <= k; i++) {
    if (number % i == 0) {
        isPrime = false;
        break;
    }
}
return isPrime;

质数应用——加密算法

这跟质数有没有用有什么关系呢？这就得从我们每天都打交道的网络说起了。比如，你要把银行卡密码发送给朋友，你会选择加密发送（这个加密的过程是由程序处理的，我们做一个简化的过程描述），111111*2=222222，这里的2就是密钥，朋友拿到你的信息，除以2就可以得到你的密码，下次，你发送其他的信息，诸如，银行卡卡号等等信息，密钥很容易泄露，非常容易就能发现你加密的规律，自然很容易就能破解你原来的信息。这个时候，就得想办法升级加密系统。这里涉及到专业的RSA算法，我尽量用最简单的语言描述一下它跟质数应用的关系。如图所示，是加密和解密的过程。m是你要发送的内容，经过加密之后得到c,你把加密后的信息发送给你的朋友，你的朋友就可以拿到原来的信息m。

加密用的e和N是公开的，解密用的私钥d的求解依赖p和q，p和q是不会公开的。为什么用质数很难破解呢？假如e=6,很容易就找到2和3这两个质因数的乘积，但是如果要对这个整数进行质因数分解就会显得非常困难。12301866845301177551304949583849627207728535695953347921973224521517264005657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413。

它的两个质因数分别是

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489和36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917。这就意味着黑客很难根据公开的信息反接触私钥d。如果不是用质数，用合数的话，就不需要暴力求解，可以通过寻找通项式找到求解d依赖的p和q两个数。

再简单一点理解，就是加密时用一个数，这个数由两个质数生成，解密时必须要知道这两个质数才能解密，比如，13*7=91，黑客在网络通信中获取到了这个91，他需要反解出13和7才能去解密，这个数比较小，黑客能够迅速解出来，但是当这个数非常大的时候，黑客只能通过暴力求解的方法，就像上面我们给出的那个大的整数，要花很长时间才能计算出来，再大一点数呢，几无可能被破解。

RSA的神奇之处在于，尽管构建密码依赖于费马300多年前关于质数的发现，但是要想破译密码却依赖于一个我们尚未解决的问题——素数（也叫质数）的通项式是什么？