Thursday, November 27, 2008

Hundred-digit RSA moduli

Here are 100 100-digit RSA numbers: composites which factor into two equal-sized primes p and q. These numbers have the additional property that p+1, p-1, q+1, and q-1 also factor into two equal-sized primes (about 24 digits) and a few small factors (of course, including 2). Supposedly, these numbers are less vulnerable to special-number form factoring techniques.

getprime(q1,q2)=while(1,gg=q1+random(q2-q1);if(isprime(gg),break));gg
getrsa(q1,q2)=while(1,a=getprime(q1,q2);b=getprime(q1,q2);c=2*a*b+1;if(isprime(c),break));c
sz(p)=k=factorint(p+1);t=matsize(k);k[t[1]-1,1]
f1=3976353643835253325869338
f2=7071067811865475244008443
while(1,n=getrsa(f1,f2);print(n," ",sz(n)))

(Also the version which substitutes -1 for +1 in the appropriate places)

About 24 hours of search found 36000 candidates, of which the top 200 were selected and multiplied in pairs.

Of course, you should never use 100-digit RSA moduli; such numbers are almost trivial to factor these days.

1606428709899644729874675979292345859654261912647353093530637240089303053475053483933871758658410219
1704014108375258232737556170089148629948631896518967829879823541975881140640737874146502172074720287
1781303871889377223414878066041046394989792128486958233489182544753788481820611087134561070907497173
1862237772373996905689295251458388912728129050046313202782606882823454460745331091160983437356835271
1863317161108440491784402169090723710328502758082436318999831475935478843114144639261236051995685229
1928186552880330378657548107358842775976081107486737809658287620191327077197836105307352011237748301
1971657626674264204865458242316555816541138382753209294935787227304564152259974057831527487103166407
2028049839351881459899909862326608427784064033926606997582218719057211695841608494095970669094226173
2052129505036174353773730742162145457926784364221422012948102112673397423603447131330887211534074779
2089380960944832852716732137816387179950714557613898107752545827218102104231909068695806721006463341
2238146047776751329237282406300280723312108210627221616403472491269905403902480619844803342962175879
2252538625538704083309972363187504222543758486053793308473796507040808159187723618530016903811982993
2294314770434088879896648129879522862399735253256066308189801083115545474012861193891721089672893239
2323270575724253209186988716872865510807032805830056848715924486914924134600890115589480130665334411
2340254553108776924011125627381261339445389397114169080478284013493485210904286804316087215113459061
2346001386853602671211488705804568717925421375853437909727471388811164647389494301887008402196318631
2367544112365820345900961281062642258234942394443158330248804849176766550140198720330668796048781193
2420752706808924291072117874364349749755162091948721183545654812632490986483168192081530407225663921
2468766347735017772498998955290809747612377851380639323684169970301869749564513583330333464156422029
2502723145108906755656479273164618329956090686604673606063520571902575267773401392164793460633560531
2505466024287737444575216343678719806113221284101210556211381272309131582105038072202248755280181053
2514819408020339284762792563494866333400359198337490607288714701219066433909273008391279171408813909
2527070226401987187553918134898646038208041262679245433517287265153695604282864930761615170318299969
2540006700253043438302266678754859367981950533831737339343095788860764404208272622207473848591257853
2559602838320872424063839428049351141187394194969844966839972904073119853633551041094042192844596623
2623226576138861804707078029794032379793347795252756894680066223422728200102481679595705532226921801
2656546631363865286061546433080659939051141076140368745110956525896356982212769452133426782895706041
2672856585396187104631717381973028466310217523948072541704370135521290338811009221873650428067475137
2688318140234922481333122344836356763753220764122293336352722027470844031628052090912309291336938943
2759342509671618107340999944607264715474935857124362293792122016288931611236406102105747366190861569
2781769177702512671801569869962989208899399438756551577799592732169792217879872698916047917931681023
2815581847128494489899327887766685641376214823135649001116319904019384215684581183417091443118320121
2832427209912011643998408435789427498041586383561657807137281108681095870314371454323666746207185907
2845407732379697878681523334158764800840617750182117533868015227154956738880828447097298720234466393
2933578246279942472905959058552670698685457299366671355661766502296264039035282957746781846260344343
3020324503955108891023734327960331076750789722432890614898138580906827276655007213810650458844980997
3022437167285430526788613748366688899847026835117048228709385357222563460560194574651479261561373969
3044221224943319376085788968740676321823230069427609973761897582455882269139200231188981745661099039
3067356733432768441722833695795890642250999999212551526314317461672510673400216070069543355000378321
3104892984247299440400490905970668142655174877497724946313845872959040684940174832205731874619109771
3127153750038505863221407005484368161932229229374971829124297672751269265278543058243102996233395521
3138157352441741746915878674601574236118154960689259153929497969198155960143138779290480526648147337
3172669852191950198900850940738879551536991562963084637192364041513427165679798094548084131953079433
3222605460279557745165261878407998313390213960462554542476082123783721999392039488989859238622835643
3249180651995477004052348718696285774308609755015381897565655454936092764455218570778263725807266529
3264071864402627680644279058535539778896128551805042430623967642951237093724433977084393916722337731
3281923057304381024478654741215917726775160906509928984127132872958049218389565364951783098971515041
3316347985545278949148842962909688054700468084441281317962118498475265773076100016316164207339462287
3377801256714914369037381417575555077754785937493204959059364587957290949188609875675624560657411429
3377804852584007053329606486965993139285758158046823789252587442043267826059569337541596906160764141
3382614110520418856649486657541298114497291413771436042569010213428654191029959383004428589173711761
3425566082292472765785966410970564242016526964524142627572601600608895349156487611582646858700322781
3432593773258855780026935367837828098093522030747847114481033192026782716423803708875854105419552851
3449834606703586935768163097997460660810660672500108382660718955631563381526065256790265360908457323
3555084821948618983805640142935224233837633142222920194445237243791835243026051037013121242921587333
3574646437350503859361213693195328430462082341283354865866581094384690686095699543644433003913076571
3581108680106505887376502020883713477945953510763402345263494160148629534474631068842936794746748059
3632193157339998240932055524340818664435201283668694133980824106168616294089853645566965892016190707
3660984718942436040061828717597535767299661792298244678108128507341798808086740040342617323420625193
3694730049440206433517860273503267990779539690648197325084376578237026864361845894530652965634182719
3698748863697349364220828050863699461647006020001946237521591439590073305661357719421521605334278367
3740342228497990126337036972150539236712775408339845080675758157462578195023071803412406224147041797
3760386712873008018055233809234881765214954524005722082385233612101334861580512896575422129976604999
3767677096130786941657778333261372076113562370557367620595346554915074298921006318460649684815267099
3795023711379423299783064857375120869896072374252578421709750333830505806327716109059214567825133431
3799313939844983981000281632123870193575121072007543595251174467838773372094417526472590203209738621
3818194893276794667794753004689695267576378659090289470945470869585642313481157785048295037254029431
3874810275455576530281824470154469628261424410612406958135430049882587050731553541437487028612357701
3900454505476552361238424165543354565914202955353943948051418443519449100251895832664972028769154629
3905341385660724823193417033287651315122167893382830678649475883221742265778380762932205104394299333
3943111087943883109511339404868985408811254225397641961685465096178749640748411249820539444176754873
3944610641742138358460460575593233270514173116700633999964348827489387944593615430941947382538500489
3948650576194654668403044630495960385902128564702751223852502018656848090218777280005390176186830781
4029939222885065928076025523884984978382193895925989062184415443436671797365092254657645199154680737
4071167656639439354509739437261277274036493179680366718803335652522373089871838354459162560297616439
4126032416469826340211683734291505070779216465336697318408551471805921064468976443370643281189788201
4192876971876078441668792599802789644383032501530745059626629341152859068528182850991717666321686121
4195079625975933145709050784678711594871210778262909592906983169942438864975719807979098081788146409
4204602693001598658906245028238540549036761438088876115846366877890116466948492839962121083712912979
4372333094635444411404161699136339965599973060347379346779270139251189734297128428275138570975754219
4390240481760304098497816473597383527293732492932531090531192893488177102504849562909714619103642921
4411885605137661379932684231165551148457776975073400165085423075316520416744207983984125827711433699
4536255981065388269463781807246369361368486703084950967874979915733032966466736438902723804366067109
4616001349352079571132689963661844312241282729063121403411497199021977141930876336430831724471619943
4719681597334134304867170103057066130307898945139038600636339045903622581613921660556363691040022803
4746063361550105570699647738423983407551144991697248833824237588343392890308963978423101130872876551
4826948064208647142259931668996899330815850154136782810008953449218549983348314039069784382413548857
4831870377807201563223533271698875622456079721031312891278799444113782680890073855645179449956046899
4835937311773458816746523449714776859486220074958122150329976048049943095503000785610919784084612009
4998911338819591528184578091279141938809778087943457933605305150671037946483775726827743063554020327
5209088823969632804859212804747861066535659452150144864490963356438368941799349329545566810516011157
5478114759049141052504652826554630032413669904251036294616158721816323754865718160763366847607600809
5816255086039065593822318338282112418463727602219891827563207282582426320308504390732473216253915167
5846112823892760213723927356664281463847091564214073509950235987714188563476697540009734390145419793
5853215074287720382025823189503080595986472048459799918166737862968671105664724455619189156382073467
6029669892554445009749222158834204895410314886381788933780537144624468333428607399120604344928354609
6190084975945507543072414355969653287399527511265226494946581136594995886693792721186444801198819551
6403544569031008763054654773021400705543445146362286250629708514339353817758169087777504652234269589
7507602920570761337713972258731432878488987240251459558778594444861549373115673133962887949623141253
8418059742469774751246918389821786647059804771789656108322744613592280124246009891390922294272758861

No comments :