什么是质因数(质因数和密码)
我们需要先谈谈密码学。要把明文转换成密文，需要两个要素:转换规则和转换参数。前者是一种编码算法，比如“在英文字母表中前进x步”。后者是关键，比如上面算法中的数x。如果x = 1，明文“立刻飞”就会变成密文“gmz bu podf”。
(资料图片仅供参考)
可以想到的最简单的安全框架是双方都知道相同的密钥集。a用它把明文转换成密文，B用它把密文转换回原文。秘钥是《红灯记》、《潜伏》等谍战电影中情报人员舍生忘死，竭力保护和争夺的密码本。因为双方知道同一组密钥，所以这种方法称为“对称密码系统”。对称密码体制到底安全不安全？答:密码本身可以是安全的，但是密钥的分发是不安全的。
“因式分解”是典型的易守难攻的数学问题。目前世界上最常用的密码体制之一是基于因式分解的RSA(三个发明家的首字母缩写)公钥密码体制。
两个质数相乘很容易。但是，另一方面，要把一个相当大的数分解成质因数的乘积，就没那么简单了。比如29和31的乘积不难算，答案是899。另一方面，把899分解成质因数也不是那么容易。至于分解更大的数字，就更难了。以下是分解几个大数的质因数所需的时间:
从表中可以看出，用笔算和试除法分解一个50位的大数，大约需要100亿年，这其实是洪都博客做不到的。有了电子计算机，只需要15秒钟。但也要注意，对于较大的数字，即使用电子计算机也是很费时间的。比如分解大量的1000比特，就需要一个星期。至于更大的数字，难度就更大了。由于大数分解比较困难，国家安全机关把这个“难”的原则运用到了暗码中，为国家安全工作做出了巨大贡献，被银行和工矿企业广泛使用。
原来，在具体编码中，01、02、03、04、...09, 10, 11, ...26分别用于表示26个英文字母。消息中的单词按照字母顺序被“翻译”成数字，然后按照一定的方法进行编码。因为人们只知道大数(即质因数的乘积)而不知道这些质因数，所以不知道代码的秘密。唯一能破译这个密码的人是知道质因数“奥秘”的人。
目前世界上最常用的密码体制之一是基于因式分解的RSA(三个发明家的首字母缩写)公钥密码体制。
解释因式分解是指将一个合数分解成两个质因数的乘积，例如21 = 3 ^ 7。当然，分解21很容易。你可以不管它分解。但是，分解成2 67–1 = 147，573，952，589，676，412，927怎么样？这是一个18位数字。1644年(李自成入京那年)，人们认为是质数。直到1903年(清朝灭亡时)人们才发现它是一个合数，等于193707721761838257287。分解这个数字几乎花了一个朝代！
为什么这么难？用计算机科学的语言来说，随着位数的增加，因式分解的计算量是&红豆博客quot指数增长”，而指数增长是一种非常快的增长，比“多项式增长”快得多。
具体来说，如果计算机每秒做1012次运算，分解一个300位的数需要15万年，分解一个5000位的数需要50亿年。——地球年龄只有46亿年！
公钥密码系统的安全性取决于数学问题的难度。但是计算量和算法有关。比如你要计算17乘以28，笨的办法是把17的28一个一个加起来，聪明的办法是按照多位数乘法列出公式。后者显然比前者快得多。
对于因式分解这样的难题，人们在不断寻找更好的算法。我们可以肯定的是，在最好的公开算法下，因式分解的计算量是指数级增长的。未来有没有可能找到更好的算法，把计算量降低到可以破解的程度？当然有可能。这只是就公共信息而言。更何况能解密的算法可能已经被一些国家和组织掌握了，只是没有公开而已！
当然，随着电子计算机的不断发展，人们在质因数分解方面也会逐渐有新的突破。今天不能分解的大数，明天可能会分解。届时，分解质因数的奥秘将被一一揭开，这一密码的安全性将成为问题。所以密码学处于无休止的军备竞赛中，一方提出更强的攻击算法，另一方提出更强的加密算法，循环无限下去。量子密码改变了密码攻防的基本模式。目前，量子密码是唯一可以在原理上证明其安全性的密码系统。
