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