数学理论和计算技术难题之一：超大复合数的分解

simon21 · 发表于 2005-7-26 10:26

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

设想在周六晚上，你去参加一个大型晚会，你可能会很想知道那里是否有你的熟人。如果晚会主人提示你，你可能认识角落里的露丝女士，你向那边看一眼就能很快确认主人说得是对的。但是，如果没有主人的提示，你就不得不在整个房间转一遍，逐个人辨认，才能最后确定房间里是否有你的熟人。这个例子可以用来说明这么一类现象：寻找问题的答案通常比验证这个答案的正确性更困难、更费时。 类似地，如果有人告诉你整数13717421能够分解为两个更小整数的乘积，你可能不知道是否应该相信他。但是，如果他对你说，这个整数能够分解为3607和3803的乘积，你只需按一下计算器，很快就能验证他说得对。复合数的分解就属于上述一类问题。迄今为止，数学家们还没有找到快速分解复合数的通用方法。 举一个更简单的例子。你能够不用计算器，在五分钟之内把整数8051分解为两个整数之积吗？你当然可以从整数2到90逐个试除，看余数是否为零，可是时间就不止五分钟了。告诉你一个诀窍，利用8051=8100-49=902-72=(90-7)*(90+7)=83*97，你很快就得到答案了。这一诀窍不是万能的，如果需要分解的整数不是很接近一个整数的平方，这种方法就不一定能加快速度。 在70年代，分解一个一般的20位整数就是一项很艰难的工作。到了80年代，由于电子计算机的运用，分解一个一般的50位整数已经是一件很平常的事。 超大复合数的分解是目前的一个计算难题，计算机信息加密方法RSA就是利用了这一特点。公共钥匙对(PQ, E)是对外公开的，你的私人钥匙D是机密的。选择一个很大的复合数PQ，要解密你的信息就需要能够在合理的时间内把这个数分解为两个素数之积：PQ=P*Q。 随着数学理论、计算机硬件和并行计算技术的发展，人们能够分解的超大复合数的位数越来越多。有人从理论上证明，如果发明了量子计算机，超大复合数的分解难题就会迎刃而解。到那时，RSA加密方法就不可靠了。 为了反映超大复合数分解技术的进展，以便及时评估RSA加密方法的可靠性。<a href="http://www.rsasecurity.com/" target="_blank" >RSA数字安全公司</A>开展了RSA复合数分解竞赛。这些竞赛题都是经过反复筛选的。 1991年，100位的RSA-100复合数分解竞赛题得到了解答： 152260502792253336053561837813263742971806811 496138068865790849458012296325895289765400035 0692006139= 400946909509208810306837352927614683892148997 24061* 379752279369436739228088727554456278545655366 38199 1992年，110位的RSA-110复合数分解竞赛题得到了解答： 357942341797258687749918078325684554030037780 242282261935329081904846702523646774115135161 11204504060317568667= 612242109049354757693703731756141884122575855 4253106999* 584641821440615467883655318297916238419861050 5601062333 1993年，120位的RSA-120复合数分解竞赛题得到了解答： 227010481295437363334259960947493668895875336 466084780038173258247009162675779735389791151 574049166747880487470296548479= 327414555693498015751146303749141488063642403 240171463406883* 693342667110830181197325401899700641361965863 127336680673013 1995年，129位的RSA-129复合数分解竞赛题得到了解答： 114381625757888867669235779976146612010218296 721242362562561842935706935245733897830597123 563958705058989075147599290026879543541= 349052951084765094914784961990389813341776463 8493387843990820577* 327691329932667095499619881908344614131776429 67992942539798288533 1996年，130位的RSA-130复合数分解竞赛题得到了解答： 1807082088687404805951656164405905566278102516 7694013491701270214500566625402440483873411275 90812303371781887966563182013214880557= 3968599945959745429016112616288378606757644911 2810064832555157243* 4553449864673597218840368689727440886435630126 3205069600999044599 1999年，140位的RSA-140复合数分解竞赛题得到了解答： 2129024631825875754749788201627151749780670396 3277216278233383215381949984056495911366573853 0219183167831073879953172308895692308734419364 71= 3398717423028438554530123627613875835633986495 969597423490929302771479* 6264200187401285096151654948264442219302037178 623509019111660653946049 1999年，155位的RSA-155复合数分解竞赛题得到了解答： 10941738641570527421809707322040357612003732945 44920599091384213147634998428893478471799725789 12673324976257528997818337970765372440271467435 31593354333897= 10263959282974110577205419657399167590071656780 8038066803341933521790711307779* 10660348838016845482092722036001287867920795857 5989291522270608237193062808643 如果你能将以下174位的复合数 18819881292060796383869723946165043980716356337 94173827007633564229888597152346654853190606065 04743045317388011303396716199692321205734031879 550656996221305168759307650257059 分解为两个素数之积，你就能获得一万美元奖金。更多的奖金等着你去拿，最高奖金二十万美元。

多情清秋 · 发表于 2005-7-26 18:51

数太大了，头晕

账号		自动登录	找回密码
密码			我要加入

[其他相关] 数学理论和计算技术难题之一：超大复合数的分解

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。