互动科普

像“轻便背囊问题”“三色问题”，虽然题目本身并没有什么深意，但是却与现实社会中的种种事物息息相关。比如“巡回销售员问题”，除了与快递选择最佳配送路线的问题有关系之外，与电路板的设计也有很深的联系。

事实上，在现实社会中，有很多问题就像这里介绍的“无解题”一样，“除了一一调查外，别无他法”。如果这样的问题可以简单解决的话，也许会给我们的生活带来巨大的影响。

质因数分解是“无解题”

不过，也有一些无解题在生活中发挥着作用。比如中学数学中学到的“质因数分解”。

质因数分解，是指某正整数以因数乘积的形式表现出来。所谓质数（也称素数），是指除了1和数字本身以外无法整除的数字。比如正整数35如果质因素分解的话，就为5×7。

将35进行质因数分解时，如何来考虑呢？虽然很多人会用直觉去解，但是如果我们“老老实实”去解的话，35先除以2，然后35除以3，这样一一去试。当除以5时，可以整除，所以35的质因数为5和7。

那么，数字更大的情况下怎么办呢？实际上我们还没有找到将质因数更有效分解（也就是在多项式时间内）的算法，也就是说我们只能“老老实实”一个一个尝试可整除数。

这样，大家就明白为什么大数字的质因数分解是“无解题”了吧。

因为质因数分解无解所以才能进行网上购物

那么什么样的质因数分解在什么样的场合下会有用呢？这就是不能让人随意解开的东西，也就是“密码”。

让我们想象一下网上购物的场景。在互联网上订购某商品，为了支付货款，就需要将银行卡信息通过互联网发送给店家。当然，这些信息需要以“密码”形式发送。质因数分解对于该密码来说是不可缺少的。

先说明一下暗号的构成与质因数的关系。首先，小A向店方发送银行卡信息，为了防止信息泄露给第三方，需要将信息“密码化”。为了将信息密码化，就需要“钥匙”。虽然说是“钥匙”，但不是现实生活中的钥匙，而是密码的规则。这把钥匙，由店方先做好，然后公开（公钥）。

这把“公钥”，是由两个质数相乘的结果。一般两个150位的质数相乘的话，结果为300位左右的正整数。虽然位数很多，但是制作公钥只是简单的“乘法”。

一方面，为了将密码化的信息复原，需要“私钥”。私钥是店方在制作公钥时使用的两个质数。这些私钥是不公开的。而且，这里最重要的是，要想从公钥算出私钥，几乎是不可能的。为什么呢？因为公钥是300位的正整数，要从这里将私钥算出来的话，必须对该数进行质因数分解。因为这个数本来就是两个质数相乘的结果，所以除了这两个质数外没有其他约数。这样被造出来的300位正整数的质因数分解，目前在现实时间中是不可能的。

因此，可以将密码化信息复原的，事实上只有原本就有私钥的店方。当然实际情况要更加复杂一些，但是基本上是按照这样一个结构来保护银行卡信息的秘密的。也就是说保证秘密不外漏的正是“质因数分解的难解性”。

图1. 质因数分解与密码的关系？

上图表现了质因数分解与密码的关系。制作两个质数（例如7591和9941）相乘的公钥是很简单的，但是从公钥分解出私钥（进行质因数分解）是很难的。

解开“无解题”的可能性

那么，将来质因数分解问题仍然会这样难吗？实际上，为了实现简化质因数分解问题的可能性，我们需要考虑两件事情。

第一，开发简化质因数分解，实用算法的可能性。到目前为止尽管进行了很多研究，但是这样的算法依然没有开发出来的事实，在一定程度上保证了质因数分解的难解性。但是也不能否定突然出现某种意想不到的使问题简化的方法。

第二，将计算机性能飞跃性提高的可能性。如果只考虑在目前计算机基础上进行改良，是不可能实现的。

如果开发出原理完全不同的“量子计算机”并推广使用，质因数分解问题将不再是难题，密码的方式也必须改变了。

下面我们梳理一下“问题的难解性”与计算机计算能力之间的关系。

从计算量的角度来看，数字排序问题很简单。在现在的计算机中也有进行数字的排序实际操作。我们在计算软件中，发出“排序”命令后，一瞬间排序即可完成数字的排序。即使是处理入学考试结果这样较为庞杂的数据，计算机也可以顺利完成任务。

不过，从计算量的角度来看，背囊问题、三色问题、巡回销售员问题等都是最难的问题。这些问题，即使使用未来开发出的量子计算机，在现实时间内也是不可能解决的。

那么，质因数分解问题能够解决吗？质因数分解问题的计算量会根据进行质因数分解的正整数的位数，呈指数函数式增长。这意味着它也是一个无解问题。但是这个问题计算量的增加速度与巡回销售员等问题相比是和缓的。用量子计算机做分解质因数的话，在现实时间内是可行的，这一点也已经从数学角度得到证明。虽然质因数分解目前还是无解题，但是一旦量子计算机得到应用，就会变成“可解题”了。

当然，不管是巡回销售员问题还是质因数分解题，如果找到了可行的减少计算量的算法的话，用现在的计算机也是可能解决的。

图2. 目前最难的问题，将来会不会也无解？

虽然现在的计算机无法解决质因数分解问题，但是数学上已经证明，用量子计算机是可以解决的。不过，很多研究者认为，即使使用量子计算机也无法解决像“背囊问题”这样的难题。当然，如果开发出可行算法的话，即使是现在的计算机也可以解决这些问题。当然，很多研究者认为这样的算法根本不存在。

深奥的人脑也值得研究

无解问题与现实社会有着千丝万缕的联系。在很多时候，我们都在不知不觉中挑战着各种无解问题。巡回销售员问题就是一个很好的例子。但是，我们似乎从不因为此类问题过于苦恼。因为我们一般会在某种程度上找出“相对近似”的答案（很接近正确答案的答案），但是这仅适用于问题“规模”较小的情况。我们人脑的复杂性，深奥性，也许也可以称为一道“无解题”吧。

（本文发表于《科学世界》2011年第8期）