质因数和密电码质因数是什么 _小知识

质因数是什么（质因数和密电码）
数学起源于生涯。我们所学的数学知识，都是直接或间接地为实际服务的。大家都知道，小学学分解质因数是为了学习分数的须要。因为分数的加减法要用到通分，乘除法要用到约分，而通分、约分须要用到分解质因数。除此而外，分解质因数还有什么用，大家可能就不知道了。前几年，美国数学家把分解质因数问题运用于密电码，为国度安全保密工作找到了一条新的门路。

文章插图

我们须要先讲一点密码学。把明文变换成密文，须要两个元素：变换的规矩和变换的参数。前者是编码的算法，例如"在英文字母表上前进x步" 。后者是密钥，例如上述算法中的x这个数。如果取x = 1，明文的"fly at once"（立即腾飞）就会变成密文的"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 = 37 。分解21当然轻而易举，你不管三七二十一就能分解它。不过，来分解2^67 – 1 = 147,573,952,589,676,412,927看看？这是个18位数。1644年（李自成进北京那一年），人们认为它是一个质数。直到1903年（清朝都快亡了），人们才发明它是一个合数，等于193,707,721761,838,257,287 。分解这个数，几乎花了一个朝代的时光！
为什么会这么艰苦呢？用盘算机科学的语言说，随着位数的增长，因数分解的盘算量是"指数增加"的，而指数增加是一种非常快的增加，比"多项式增加"要快得多。