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

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

数学来源于生活。我们所学的所有数学知识都直接或间接地服务于现实。众所周知，小学质因数的分解是为了学习分数。因为分数的加减使用一般分，乘除使用近似分，一般分和近似分需要分解质因数。另外，分解质因数有什么用，你可能不知道。几年前，美国数学家将素因子分解应用于密码，为国家安全和保密找到了新的途径。

我们需要先谈谈密码学。将明文转换为密文需要两个要素:转换规则和转换参数。前者是一种编码算法，比如“英语字母表上的Advance x best steps”。后者是一个键，比如上面算法中的数字x。如果x = 1，明文“立刻飞行”(立即起飞)将变成密文“gmz bu podf & quot。

最容易想到的安全框架是双方都知道同一套密钥，A用它把明文转换成密文，B用它把密文转换回原来的样子。秘钥是《红灯记》《潜伏》等谍战片中情报人员舍命守护争夺的密码本。由于双方知道同一组密钥，这种方法被称为“对称密码系统”。对称密码安全吗？答案是:密码本身可以是安全的，但密钥的分发是不安全的。

在易守难攻的数学问题中，“因式分解”就是一个典型的例子。目前，世界上最常用的密码系统之一是基于因式分解的RSA(三个发明者的首字母缩写)公钥密码系统。

两个质数相乘很容易。然而，反过来说，把相当多的数分解成质因数的乘积就不是那么简单了。例如，计算29和31的乘积并不难。答案是899。另一方面，把899分解成质因数也不是那么容易的。至于分解更大的数字，就更难了。以下是分解几个大数的质因数所需的时间:

从表中可以看出，用试除法分解一个50位数的大数大约需要100亿年，实际上是不可能的。有了电脑，15秒就能完成。然而，还应该注意的是，对于较大的数量，即使用电子计算机也非常耗时。例如，如果分解大量的1000位，则需要连续一周的时间。至于人数多，难度就更大了。大数很难分解，所以国家安全机关把这个“难”用了BST的原理应用到密码上，为国家安全工作做出了巨大贡献，百特网络被银行和工矿企业广泛使用。

原来，在具体的编码中，英语中的26个字母用01、02、03、04、… 09、10、11、… 26来表示，而消息中的单词则是(原创www.isoyu.com版权)按字母顺序“翻译”成数字，然后按照一定的编码方法。因为人们只知道大数(即质因数的乘积)，却不知道这些质因数，他们不知道代码的秘密。破译这个密码的唯一方法是掌握主要因素答案“人。

目前，世界上最常用的密码系统之一是基于因式分解的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加起来，聪明的做法是按照多位数乘法列出公式，显然比前者快很多。

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

当然，随着电子计算机的不断发展，人们会逐渐在素因子的分解上取得新的突破。今天不能分解的大数，2021-09-29 可能会分解。届时，分解质因数的奥秘将被一一揭开，这一密码的安全性也将受到质疑。因此，密码学在军备竞赛中处于无休止的对抗之中。一方提出更强的攻击算法，另一方提出更强的秘密算法，无限期进行。量子密码改变了攻击和防御的基本模式。量子密码是唯一能从原理上证明安全性的密码系统。