6. 密码学
虽然我们在解决NP问题方面取得了很大的进展，但是很多密码学的领域仍旧毫无进展。包括单向函数、安全散列和公钥密码等多种形式的加密。一种有效的NP算法，其实是能够破解所有密码系统的，除了那些信息理论上安全的密码系统（比如一次性密码和一些量子物理学的安全系统）。我们已经看到过很多成功的网络安全攻击，但是它们通常源于服务器糟糕的设置、很差的随机数生成器，或者人为的一些错误，几乎都不是由于密码学本身的问题所导致的。
现在的大多数CPU芯片都内置AEC，因此一旦我们使用公钥密码技术来设置私钥，我们就可以像发送纯文本一样轻松的发送加密数据了。加密为区块链和加密货币提供了底层的技术支持，这意味着人们对加密技术的信任十分高，足以将现金和比特币进行交换。Michael Kearns和Lesilie Valiant在1994年的研究表明，学习最小的电路，甚至学习最小的有界层神经网络，都可以用来分解质因数和破解公钥密码系统。但是到目前为止，机器学习尚未成功用于破解密码协议。
可能有人会问，我们既然已经在许多其他NP问题上取得了很多的进展，为什么单单是密码学上失灵了呢？在密码学中，我们可以选择问题，专门设计为这个场景单独设计的方法来加密，从而达到不错的效果。而其他的NP问题通常使用通用的、通过程序自己形成的方法来执行。这些自动匹配的方法可能不是量体裁衣的，就并不是最合适和最困难的方法。
量子计算是目前我们知道的唯一一个能够威胁到互联网公钥协议安全的存在。Shor的算法可以用于对大数进行质因数分解和其他相关的数论计算。这种担忧可以通过几种方法来加以解决。虽然目前来看量子计算取得了一些令人惊叹的进步，但是它距离能够破解当今的密码系统相去甚远，毕竟还不能够处理足够多的纠缠位。有人估计，可能还得需要几十年甚至几个世纪才能真正使用Shor算法+量子计算机对目前的公钥产生威胁。另外，研究人员在开发对量子攻击具有抵抗力的公钥密码系统方面取得了良好的进展。我们将在本文后面的部分详细介绍量子计算。
因式分解问题，目前来说并不是NP完全的，即使我们没有大规模的量子计算机，数学上的突破也肯定有可能推导出很高效有用的解决方案。不论我们如何看待量子计算的未来，一些拥有了多种公钥系统的计算机都可能解决因式分解问题。
（未完待续）
No post found!
- 《纽约客》丨纪念9·11二十五周年 - 09/12/26
- 数学500年：新的黄金时代？（1） - 06/05/26
- 没有美洲，我们吃啥？ - 05/17/26