论文部分内容阅读
在小学，同学们曾学习到正整数的一种分类，按这种分类，所有正整数可分为：质数(或称素数)、合数和1，在做了这种分类后，同学们会进一步了解到：每个合数都可以由几个质数相乘得到，由此引入了一个非常自然的问题：如果知道了一个数是合数，如何把这个合数分解质因数呢?一种常用的方法称为试除法，具体地说，为了分解一个合数，我们可以试着从最小的质数2开始，用质数2，3，5，……一个一个地去试除给定的合数，看这些质数能否整除所给的合数，如果能整除，就记下除数和商，如果商仍然是合数，就重复上面的试除过程，如此炮制，一直到最后的商是质数为止，由此，就把给定的合数分解质因数了。
到此为止，一切都很简单、很好理解，难道整数分解这个小问题真的是这样浅显无趣吗?如果你这样认为，那你可以试试下面的一个“小题目”：分解4189，你会发现，如果用上面的办法分解30只需要几秒钟，那么用同样的办法分解4189，或许就要花费你好几分钟了，很不幸，4189这个数才仅有4位而已，如果要分解一个10位或20位的数，又会怎样呢?一个有趣的故事会告诉我们答案。
1903年10月，美国数学家科尔(1861－1926)登上讲台，以一个并不醒目的标题“论大数的因数分解”开始做学术报告，只见一向沉默寡言的科尔走上讲台，一言不发地在黑板上计算起267(这个式子表示67个2连乘在一起)来，然后他小心地将该数减去1，得到21位的庞大数字147573952589676412927，他仍一言不发地移到黑板上的空白处，一步步地做起了乘法运算：193707721×761838257287，两个计算结果完全相同，台下的听众马上意识到，科尔已经在这次无声的学术报告中成功地分解了一个21位的合数267－1，会场上顿时响起了经久不息的掌声，会后，当有人询问科尔寻找这两个质数因子用了多长时间时，科尔回答说：“三年中的全部星期天!”
由此我们可以明白。为了更好地处理大数分解的问题，人们需要寻找更好的方法，300多年前，法国数学家费马(他以提出费马大定理而闻名)最先找到了整数分解的新方法，下面，我们就用他的方法来分解一下上面刚刚提到的4189。
先找一个数，这个数的平方稍大于4189，我们可以取65.65的平方是4225，用这个数减去4189，得到36.36正好是6的平方，于是，我们有4189＝652－62而(65＋6)(65－6)＝65×65＋6×65－6×65－62，恰好等于652－62(事实上，一般总有：两数的平方差等于这两个数的和乘以这两个数的差)，于是，我们得到4189＝652－62＝(65＋6)(65－6)＝71×59，对71、59这两个比较小的数，容易验证它们都是质数，因此，我们就成功地把4189分解质因数了。
如果你勤于思考，你可能会问：这里找到的65的平方与4189的差正好是一个数(即6)的平方，如果这个差不是一个数的平方，该怎么办呢?办法是，你可以继续试试66的平方与4189的差，67的平方与4189的差……简单地说，费马给出的方法是：为了分解一个数，去找另一个数，使后一个数的平方减去给定的数，差正好是一个平方数，下一步，利用上面提到的，两数的平方差等于这两个数的和乘以这两个数的差，使问题得到解决，你明白费马的方法了吗?试试分解5251吧，你会发现，在这类例子中，费马的方法比毫无效率的试除法确实是简捷多了，不过，多试几个例子你就会发现，这种方法也是有局限性的，并不是对任何一个数的分解它的工作量都如此小。
谈到这儿，有同学可能会问：以前没有计算机，大数分解是困难的，现在有了速度非常快的计算机，把事情交给计算机完成，不就行了吗?这样的疑问是有道理的，但问题是，在有了计算机后，分解20位数可能由困难变得简单了，可如果分解一个40位或50位的数呢?计算机比我们手算的速度可能快多少亿倍，但这在整数分解问题上所能做到的，最多不过是把可分解的整数位数提高一二十位而已，因此，要想成功地对大数进行分解，只靠计算机的高速是不大管用的。
唉呀，停一下!我们为什么要对这么高的位数的大数进行分解呢?毕竟，这种大数分解似乎是没有任何实用价值的，放在几十年前，对这个问题的回答可能是：做这种事，多多少少就是一些对此充满好奇的人没事儿找事，另一种回答也许是：正是因为这种“纯正洁白”的研究没有实际用处，所以才更具有迷人的魅力，然而，当20世纪70年代人们把大数分解与极具应用价值的密码技术联系在一起时，事情发生了转折。
密码的应用，已有悠久的历史，最初，它应用在一些非常重要的场合，如战争中，交战中，将领想把信息传递给自己的下属，但又担心在传递过程中，信息被截获导致机密泄漏，如何做才能避免这种可怕的后果呢?一种有效的方式就是对信息进行加密，从而隐藏信息的意思，对原来的信息，我们称之为明文：加密后的信息我们称之为密文，信息的发送一方把明文转化为密文。信息的接收方再把收到的密文转化为明文，在此过程中，关键是传送信息的一方与接收信息的一方事先要协商好某种要保密的“钥匙”(可称为密钥)，用来加密和解密，在谍战片中，经常出现的密码本就是这种密钥，在传统密码方案中，加密者和解密者必须知道同样的密钥，并用同一个密钥进行加密和解密，而且只要有密钥，加密与解密都很容易进行，但是在没有密钥的情况下，破译信息是不可能的或者是非常困难的，这正是谍战片中人们为什么要如此费心费力去得到密码本的原因。
20世纪，特别是进入信息化时代后，这种传统密码方案的局限性越来越明显，越来越无法适应人们的要求，1976年，一种非常美妙的新思想被引入了，有人想到可以设计陷阱门密码，像任何人都很容易掉进陷阱，但是出来却要难得多一样，陷阱门密码具有一种类似的进去容易出来难的“单向性”，我们可以通过一个类比来理解一下这种密码。
我们都知道，把锁关上是非常容易的，但只有有钥匙的人才能把锁打开，于是：一个人比如说甲为了得到别人的信息，可以设计一种挂锁和钥匙，然后自己保存好钥匙，而把成千上万的挂锁分发出去(公开分发的挂锁相当于甲的“公开密钥”)，如果别人想发一个信息给甲，只需要把信息用甲提供的锁锁在箱子中寄给甲就行了，挂上锁和锁上的过程相当于加密，因为每个人都可以得到挂锁，所以每个人都可以挂上锁锁上箱子以发送信息，因此，加密一个信息是很容易的，但因为只有甲有钥匙(只有甲才有的钥匙相当于甲的“私人密钥”)，因此只有他可以打开锁，看到箱子中的信息，其他人即使得到了挂上锁的箱 子，也知道有关锁的知识，但这些都无助于开锁。
可是，如何才能将这一美妙思想变成现实呢?1977年4月。三位研究者获得了成功，于是，一种新的、在现代密码学中最有影响的加密系统问世了，它以三位发现者(Rivest，Shamir，Adleman)名字的首字母命名。称为RSA密码，下面，我们用非常简略的方式说明一下这种密码的操作过程。
我们假设一个人比如说甲要得到别人的信息，他可以这样做：选取两个质数p与q，保存好这两个数，然后算出两者的乘积N，并把这个值公开，这个被公开的Ⅳ就是甲的公开密钥(相当于上面类比中公开发送出去的挂锁)，而保存好的不公开的p与q实际上就是甲的私人密钥，如果有人比如说乙打算发信息给甲。他只需要先查到甲的公开密钥N，然后以Ⅳ为基础加密信息后传给甲就行了，甲在收到乙寄来的加密信息后，可以利用自己的私人密钥p与q解密密文，假设丙截获了信息，他破译密文的关键是要通过公开的数Ⅳ得出未公开的p与q，而这个过程是一个分解质因数的过程，我们已经知道，对于一个大数来说要分解质因数是极其困难的，因此，只要甲选定的Ⅳ的数量级达到了一定的程度，那么要想分解它。即便最先进的电子计算机也是无能为力的。
仔细体会会觉察到，这种RSA密码系统的最优美之处在于利用了这样一个事实：给定两个大质数进行乘法运算得到其积是容易的，但已知乘积把它分解成原来的两个质数却是非常难以做到的!
为了证明这种密码的可靠性，《科学美国人》杂志1977年8月号上发表了一篇名为《一种新的密码，要几百万年才能破解》的文章，文章举例说。为了解密某个信息，关键要做的是把一个129位的大数分解!按照当时通用的方法分解这个被称为RSA-129(129指位数)的大数，人们估计至少要用几百万年，因为当时即便是50位数，看起来也超出了最方便的因数分解方法和电子计算机“能够驾驭”的范围。
然而。正是RSA密码的提出，极大地刺激了大数分解的研究，从而在这方面出现了远远超出人们预料的进展，在短短的20多年里，几种精巧绝伦的有效分解方法先后被提出，从而使人们在大数分解方面迈出了一大步。
先是在20世纪80年代初，一种与上面提到的费马方法有关系，但却远为精巧、复杂的二次筛法(或称平方筛法)出现了。它把能被分解的数的位数一下子翻了一番，以前人们一般只能分解50位左右的大数，而它一下子把原来很难分解的正整数推进到了100位的水平，随后在1987年，有数学家提出椭圆曲线法，1980年代后期，又有数学家提出了数域筛法，数域筛法在1990年代被改进，威力大增，已成为目前世界上最快、最先进的整数分解方法，使用这种方法，现在人们已经能够分解200位的大数了。
那么，RSA－129的命运又如何了呢?1994年，有人组织了一项以互联网为基础的分解RSA－129的工程，来自24个国家的600位志愿者，每人操作一至数台个人计算机，他们合作8个多月后，最终找到了这个大数的两个质数因子，成功地分解了这个大数，在挑战提出17年后，RSA－129被攻克了!人们取得这一成功，除了有赖于计算机变得越来越快外、最重要的原因在于：分解中使用了当时先进的“二次筛法”。
虽然RSA－129有些短命，然而从某种意义上讲，分解129位数所需要的大量工作恰恰表明了RSA保密系统的威力，这同时也表明，为了增加亓丁靠性，做到真正的保密，使用RSA密码系统时，必须使用更高数量级的数，现在人们建议，RSA加密应当至少有240位，以保安全，在一些更重要的场合，如银行转帐等，可以让N取300位的大数，这样，恐怕1亿台电脑加起来分解它也要花费成千上万年的时间。
我们看到，要破泽目前被广泛使用的RSA密码系统，就意味着需要找到更好更快的方法来进行大数分解，大数质因数的分解这个最古老的纯粹数学问题与最新的学科——密码学意外地结合了起来，由此，大数分解问题一跃而成为数学研究中的热点问题。
一个看似简单的小问题竟然蕴含着如此深的大学问，而一个貌似毫无实际用途的最纯粹的数学课题，居然成为现代安全体系的基础，被广泛应用于现代社会各种各样的场合，这一切是多么有趣，多么出人意料，又多么具有启发意义啊!
到此为止，一切都很简单、很好理解，难道整数分解这个小问题真的是这样浅显无趣吗?如果你这样认为，那你可以试试下面的一个“小题目”：分解4189，你会发现，如果用上面的办法分解30只需要几秒钟，那么用同样的办法分解4189，或许就要花费你好几分钟了，很不幸，4189这个数才仅有4位而已，如果要分解一个10位或20位的数，又会怎样呢?一个有趣的故事会告诉我们答案。
1903年10月，美国数学家科尔(1861－1926)登上讲台，以一个并不醒目的标题“论大数的因数分解”开始做学术报告，只见一向沉默寡言的科尔走上讲台，一言不发地在黑板上计算起267(这个式子表示67个2连乘在一起)来，然后他小心地将该数减去1，得到21位的庞大数字147573952589676412927，他仍一言不发地移到黑板上的空白处，一步步地做起了乘法运算：193707721×761838257287，两个计算结果完全相同，台下的听众马上意识到，科尔已经在这次无声的学术报告中成功地分解了一个21位的合数267－1，会场上顿时响起了经久不息的掌声，会后，当有人询问科尔寻找这两个质数因子用了多长时间时，科尔回答说：“三年中的全部星期天!”
由此我们可以明白。为了更好地处理大数分解的问题，人们需要寻找更好的方法，300多年前，法国数学家费马(他以提出费马大定理而闻名)最先找到了整数分解的新方法，下面，我们就用他的方法来分解一下上面刚刚提到的4189。
先找一个数，这个数的平方稍大于4189，我们可以取65.65的平方是4225，用这个数减去4189，得到36.36正好是6的平方，于是，我们有4189＝652－62而(65＋6)(65－6)＝65×65＋6×65－6×65－62，恰好等于652－62(事实上，一般总有：两数的平方差等于这两个数的和乘以这两个数的差)，于是，我们得到4189＝652－62＝(65＋6)(65－6)＝71×59，对71、59这两个比较小的数，容易验证它们都是质数，因此，我们就成功地把4189分解质因数了。
如果你勤于思考，你可能会问：这里找到的65的平方与4189的差正好是一个数(即6)的平方，如果这个差不是一个数的平方，该怎么办呢?办法是，你可以继续试试66的平方与4189的差，67的平方与4189的差……简单地说，费马给出的方法是：为了分解一个数，去找另一个数，使后一个数的平方减去给定的数，差正好是一个平方数，下一步，利用上面提到的，两数的平方差等于这两个数的和乘以这两个数的差，使问题得到解决，你明白费马的方法了吗?试试分解5251吧，你会发现，在这类例子中，费马的方法比毫无效率的试除法确实是简捷多了，不过，多试几个例子你就会发现，这种方法也是有局限性的，并不是对任何一个数的分解它的工作量都如此小。
谈到这儿，有同学可能会问：以前没有计算机，大数分解是困难的，现在有了速度非常快的计算机，把事情交给计算机完成，不就行了吗?这样的疑问是有道理的，但问题是，在有了计算机后，分解20位数可能由困难变得简单了，可如果分解一个40位或50位的数呢?计算机比我们手算的速度可能快多少亿倍，但这在整数分解问题上所能做到的，最多不过是把可分解的整数位数提高一二十位而已，因此，要想成功地对大数进行分解，只靠计算机的高速是不大管用的。
唉呀，停一下!我们为什么要对这么高的位数的大数进行分解呢?毕竟，这种大数分解似乎是没有任何实用价值的，放在几十年前，对这个问题的回答可能是：做这种事，多多少少就是一些对此充满好奇的人没事儿找事，另一种回答也许是：正是因为这种“纯正洁白”的研究没有实际用处，所以才更具有迷人的魅力，然而，当20世纪70年代人们把大数分解与极具应用价值的密码技术联系在一起时，事情发生了转折。
密码的应用，已有悠久的历史，最初，它应用在一些非常重要的场合，如战争中，交战中，将领想把信息传递给自己的下属，但又担心在传递过程中，信息被截获导致机密泄漏，如何做才能避免这种可怕的后果呢?一种有效的方式就是对信息进行加密，从而隐藏信息的意思，对原来的信息，我们称之为明文：加密后的信息我们称之为密文，信息的发送一方把明文转化为密文。信息的接收方再把收到的密文转化为明文，在此过程中，关键是传送信息的一方与接收信息的一方事先要协商好某种要保密的“钥匙”(可称为密钥)，用来加密和解密，在谍战片中，经常出现的密码本就是这种密钥，在传统密码方案中，加密者和解密者必须知道同样的密钥，并用同一个密钥进行加密和解密，而且只要有密钥，加密与解密都很容易进行，但是在没有密钥的情况下，破译信息是不可能的或者是非常困难的，这正是谍战片中人们为什么要如此费心费力去得到密码本的原因。
20世纪，特别是进入信息化时代后，这种传统密码方案的局限性越来越明显，越来越无法适应人们的要求，1976年，一种非常美妙的新思想被引入了，有人想到可以设计陷阱门密码，像任何人都很容易掉进陷阱，但是出来却要难得多一样，陷阱门密码具有一种类似的进去容易出来难的“单向性”，我们可以通过一个类比来理解一下这种密码。
我们都知道，把锁关上是非常容易的，但只有有钥匙的人才能把锁打开，于是：一个人比如说甲为了得到别人的信息，可以设计一种挂锁和钥匙，然后自己保存好钥匙，而把成千上万的挂锁分发出去(公开分发的挂锁相当于甲的“公开密钥”)，如果别人想发一个信息给甲，只需要把信息用甲提供的锁锁在箱子中寄给甲就行了，挂上锁和锁上的过程相当于加密，因为每个人都可以得到挂锁，所以每个人都可以挂上锁锁上箱子以发送信息，因此，加密一个信息是很容易的，但因为只有甲有钥匙(只有甲才有的钥匙相当于甲的“私人密钥”)，因此只有他可以打开锁，看到箱子中的信息，其他人即使得到了挂上锁的箱 子，也知道有关锁的知识，但这些都无助于开锁。
可是，如何才能将这一美妙思想变成现实呢?1977年4月。三位研究者获得了成功，于是，一种新的、在现代密码学中最有影响的加密系统问世了，它以三位发现者(Rivest，Shamir，Adleman)名字的首字母命名。称为RSA密码，下面，我们用非常简略的方式说明一下这种密码的操作过程。
我们假设一个人比如说甲要得到别人的信息，他可以这样做：选取两个质数p与q，保存好这两个数，然后算出两者的乘积N，并把这个值公开，这个被公开的Ⅳ就是甲的公开密钥(相当于上面类比中公开发送出去的挂锁)，而保存好的不公开的p与q实际上就是甲的私人密钥，如果有人比如说乙打算发信息给甲。他只需要先查到甲的公开密钥N，然后以Ⅳ为基础加密信息后传给甲就行了，甲在收到乙寄来的加密信息后，可以利用自己的私人密钥p与q解密密文，假设丙截获了信息，他破译密文的关键是要通过公开的数Ⅳ得出未公开的p与q，而这个过程是一个分解质因数的过程，我们已经知道，对于一个大数来说要分解质因数是极其困难的，因此，只要甲选定的Ⅳ的数量级达到了一定的程度，那么要想分解它。即便最先进的电子计算机也是无能为力的。
仔细体会会觉察到，这种RSA密码系统的最优美之处在于利用了这样一个事实：给定两个大质数进行乘法运算得到其积是容易的，但已知乘积把它分解成原来的两个质数却是非常难以做到的!
为了证明这种密码的可靠性，《科学美国人》杂志1977年8月号上发表了一篇名为《一种新的密码，要几百万年才能破解》的文章，文章举例说。为了解密某个信息，关键要做的是把一个129位的大数分解!按照当时通用的方法分解这个被称为RSA-129(129指位数)的大数，人们估计至少要用几百万年，因为当时即便是50位数，看起来也超出了最方便的因数分解方法和电子计算机“能够驾驭”的范围。
然而。正是RSA密码的提出，极大地刺激了大数分解的研究，从而在这方面出现了远远超出人们预料的进展，在短短的20多年里，几种精巧绝伦的有效分解方法先后被提出，从而使人们在大数分解方面迈出了一大步。
先是在20世纪80年代初，一种与上面提到的费马方法有关系，但却远为精巧、复杂的二次筛法(或称平方筛法)出现了。它把能被分解的数的位数一下子翻了一番，以前人们一般只能分解50位左右的大数，而它一下子把原来很难分解的正整数推进到了100位的水平，随后在1987年，有数学家提出椭圆曲线法，1980年代后期，又有数学家提出了数域筛法，数域筛法在1990年代被改进，威力大增，已成为目前世界上最快、最先进的整数分解方法，使用这种方法，现在人们已经能够分解200位的大数了。
那么，RSA－129的命运又如何了呢?1994年，有人组织了一项以互联网为基础的分解RSA－129的工程，来自24个国家的600位志愿者，每人操作一至数台个人计算机，他们合作8个多月后，最终找到了这个大数的两个质数因子，成功地分解了这个大数，在挑战提出17年后，RSA－129被攻克了!人们取得这一成功，除了有赖于计算机变得越来越快外、最重要的原因在于：分解中使用了当时先进的“二次筛法”。
虽然RSA－129有些短命，然而从某种意义上讲，分解129位数所需要的大量工作恰恰表明了RSA保密系统的威力，这同时也表明，为了增加亓丁靠性，做到真正的保密，使用RSA密码系统时，必须使用更高数量级的数，现在人们建议，RSA加密应当至少有240位，以保安全，在一些更重要的场合，如银行转帐等，可以让N取300位的大数，这样，恐怕1亿台电脑加起来分解它也要花费成千上万年的时间。
我们看到，要破泽目前被广泛使用的RSA密码系统，就意味着需要找到更好更快的方法来进行大数分解，大数质因数的分解这个最古老的纯粹数学问题与最新的学科——密码学意外地结合了起来，由此，大数分解问题一跃而成为数学研究中的热点问题。
一个看似简单的小问题竟然蕴含着如此深的大学问，而一个貌似毫无实际用途的最纯粹的数学课题，居然成为现代安全体系的基础，被广泛应用于现代社会各种各样的场合，这一切是多么有趣，多么出人意料，又多么具有启发意义啊!