什么是质因数(质因数和密码)

数学来源于生活。我们所学的数学知识，Best Net，直接或间接服务于实际情况。众所周知，小学分解质因数是为了满足学习成绩的需要。因为分数的加减需要一般分数，乘除法需要近似分数，一般分数和近似分数需要分解最佳净质量因子。另外，分解质因数有什么用？你可能不知道。几年前，美国数学家将因子分解素因子问题应用于密码，为国家安全和保密找到了新的途径。

我们需要先谈谈密码学。将明文转换为密文需要两个要素:转换规则和转换参数。前者是一种编码算法，比如“英文字母表中的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很容易。不管3721你都可以分解。然而，让我们分解2 67–1 = 147，573，952，589，676，412，927。看到了吗？这是一个18位数的数字。1644年(李自成进京的那一年)，人们以为是质数。直到1903年(清朝濒临灭亡)人们才发现这是一个复合数，等于193，707，721，761，838，257，287。分解这个数字几乎用了一个朝代！

为什么这么难？在计算机科学的语言中，随着位数的增加，因式分解的计算量是“指数增长”，而指数增长是一种非常快的增长，比“多项式增长”快得多。

具体来说，如果计算机每秒做1012次运算，分解一个300位数需要15万年，分解一个5000位数需要50亿年——地球的年龄只有46亿年！

公钥密码系统的安全性取决于数学问题的难度。然而，计算量与算法有关。比如要算17乘28，愚蠢的做法是把17乘28一个一个加起来，聪明的做法是按照多位数乘法列出公式，显然比前者快很多。

人们一直在寻找更好的算法来解决像因式分解这样的难题。我们可以肯定的是，在目前公开的最佳算法下，因子分解的计算量呈指数增长。未来有没有可能找到更好的算法，把计算量降低到可以破解的水平？当然有可能。这只是在公共信息方面。更令人不安的是，可以解密的算法可能已经被一些国家和组织掌握，但却没有公布！

当然，随着计算机的不断发展，人们会逐渐在素因子的分解上取得新的突破。今天不能分解的大数，明天可能会分解。到那时，分解质因数的奥秘将一个接一个地暴露出来，这个密码的安全性将成为问题。因此，密码学处于无休止的军备竞赛对抗中，一方提出更强的攻击算法，另一方提出更强的安全算法，循环无限地进行下去。然而，量子密码改变了密码攻击和防御的基本模式。量子密码是目前唯一能从原理上证明安全性的密码系统。