找回密码
 注册
Simdroid-非首页
查看: 226|回复: 2

[工程数学] 数学理论和计算技术难题之一:超大复合数的分解

[复制链接]
发表于 2002-12-7 20:10:21 | 显示全部楼层 |阅读模式 来自 Reserved
设想在周六晚上,你去参加一个大型晚会,你可能会很想知道那里是否有你的熟人。如果晚会主人提示你,你可能认识角落里的露丝女士,你向那边看一眼就能很快确认主人说得是对的。但是,如果没有主人的提示,你就不得不在整个房间转一遍,逐个人辨认,才能最后确定房间里是否有你的熟人。这个例子可以用来说明这么一类现象:寻找问题的答案通常比验证这个答案的正确性更困难、更费时。  
  
类似地,如果有人告诉你整数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加密方法的可靠性。RSA数字安全公司开展了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  
分解为两个素数之积,你就能获得一万美元奖金。更多的奖金等着你去拿,最高奖金二十万美元。  
  
如果有兴趣,你可以看到更多RSA复合数分解竞赛题目和有关FAQ。  
  
======================  
热身练习题:  
(1) 试把151467053137分解为两个素数之积。

评分

1

查看全部评分

发表于 2002-12-7 20:58:34 | 显示全部楼层 来自 天津

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

Simdroid开发平台
这个RSA我是知道的,不过这个竞赛我看就免了,不过是不是只要在规定的时间内找到一对P,Q,那么你就可以获取用户的D了吗?
Angle 该用户已被删除
发表于 2002-12-8 19:06:10 | 显示全部楼层 来自 山东青岛
提示: 作者被禁止或删除 内容自动屏蔽
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|小黑屋|联系我们|仿真互动网 ( 京ICP备15048925号-7 )

GMT+8, 2024-3-29 23:46 , Processed in 0.044025 second(s), 19 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表