Два в степени сто тридцать шесть миллионов двести семьдесят девять тысяч восемьсот сорок один. Минус один Это новое самое большое простое число (и не ваша любимая группа, а просто число!)
Руководство некоммерческого проекта по поиску простых чисел GIMPS (Great Internet Mersenne Prime Search) объявило об обнаружении нового рекордно большого простого числа (то есть того, что делится только на себя и единицу). Им оказалось число 2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1, то есть два в степени 136 279 841 минус единица. Запись рекордного числа не степенной, а в обычной десятичной форме кончается на …9486871551 и требует 41 024 320 цифр — архив с ними можно скачать по ссылке на сайте проекта, он сам по себе занимает около 20 мегабайт.
8816943275038332655539391003781173589712073545090660410671563764124226306947568414417259903477232831
0883750973995977687416411861067989576855334864723995205060798449228721358061244076525539478775000439
5347501701549745762834102958481023835255352192200180198498552136822893544212337319410484368519373650
8609493602871131747101857143206470819983730614862878257124301338862520617391027430764695418172448981
5008305937259728175843471969304505016010624205115241396117063758595818539722355781328791512832801883
9057613209938389056582966505524091383431835522276577489117796697500310932940933867442316193483512025
5151308427150097668052460299803048486048403202837881227404218937078614698622508383318025612408295292
9091707884436572049502580821237700560065034341723563299580864533178881894890817148581725172201276201
7969237631825861062073285000564078764795356659196781904507581604632938788368647964197805694588255164
3497172451966966844890200336467664985643635857298544158284931783349632302774755550728620334625482940
8752819531771512548534236253532983572231189002194916586521583207586932781862770923681466147078393925
8100511697858095790246995818943348603152161928561102076514239667665213403098510766174806985820594948
2643728596113195156597488375426738642144176131987821505057297453829068899339992814613745110061647277
0615317490123443053252568975041397721388444728240993479383102138939474913207852732017423227078422701
3566971694667037080836180794813296009003535208425422441777803674447454356507470629694869791580237170
2094278733776147266120050003135077004846842717866861757111736421269721307120783435298683457230508343
1740899929332096353699971532072957065271098903819080650935808305441863784563017229089397950184268543
1649492768629217469905421196443396154736494599790079320155382033853504689532400817479031325421715124
5566168983819393872759975724676491163717912806694071829494592624092973145718801898764029752512431652
5566024837865170240623526407422821550236896304702014095938964912978795136232523669234456622467126739
1398165304599499079925897591386148911902688664792591382935344547478704595502664031697621221007000470
6121677834132204200606324211827381187223549193951581244599150674606319945604975770404524304336379988
5894076948212885567327674569886225980413232733884037412589816633520056317415512051649914439327486137
6083591442970171573888104854988312199182901014926850484818422643192545735755527775863616561968526255
2283204621600598891947556515321789886171515870867825419822967508774065858599643033020140028480657400
2203555588844662627511328369016378345591415989521940346298981936092825851255766284371056976470049162
1548073690832945058302591452885220863877781606183882380094087707379600609399859625286101373802454986
9935267086772713455632301543690202916651504413793937006907904764384101523553500627170626460509948905
4644595810927300736152995828999043944952019943955341768394229723276445057467663233726580498705079885
8992095967002042153063216515938495760914578614906876209394705477100706847552395302037080671422392047
3742226315524508738324956945039023998478646195553074921299487069491064156522752110618417514317723578
2665516740169991210894104051324172101342688812408069791763409823897119696573840413626153002666877414
3865793815668139289347131503338953243502389720455854576958034032479409708099139106369311217336939383
9382857014242361846477568187597937990553794933120875765715981100862964402259328317365131116298319720
2094673785510568033571115077434554443040151044906072043400491634222562075455396438726011593229705477
6196071490271849463581569336549919225607927260501313608595368499577843435996477273653164861197280952
7930622814851153710789009858829394829472230242830210424394590491626539044809434102144958489674491930
7683760739740514348830691270811865394548137192549075383799924261484335684899167522475802289148339295
2589290129281228737392233893368463309715954800520224775009676451000679989178002305705432094833831632
6311357488843585140396136107647072737960722563759085121585373491428557420593557089132682291724265321
3481274408476552931528731205963307144969970499453426908657434110062915892427539913857139321667534049
9135269714998523381872762016319141725691269335157407099734236572222115727736003893653342789061628337
7409768161609806765480168426578300448364499998011569067268459285770970652282410687222449366893009114
8918002074168349274856658824009498591099861296108856389582437768810638281898371009548744373223726037
8722942061760492634565872918507769481483003437973756129355950164467553402479480743560482449935807658
1302439203942842545971761068548589825900415087287508701506741956954238304989856758300246281190774970
9721089537948607229466210147399303032563539553432256389221113408113863121603268219028629707506376390
1391175286441974449728252207646268497611653182098590749720465111021873781106005761331553856649992998
5032947114537264780555942998356015486410404469477460836043532683080976891728229984131523372455915690
9539242056858770432068700746801420853475338993570261755193094524872692203566328652028905411088309934
7970568332389712504457224688572012770307636328823597992870548957387731331826024684155248418050676672
6244351069551707431714348064657583925088672657599501418680582118069885780897910385240519623146895676
2768871202742260907212688051386411963760828544709644682486143650053988012706556567540241440810142441
7012848877951857938893435551608028623006529595757344492928781000204002353025874791875166420351417173
3680906739757311219053896875669319257432471838032411237946029238307449204762036299680535654452791165
1800776782392287891924026248675691118923992503445280718243507236978214787227432694814380861368408722
3842911821642282072378552452117716968772496770287165633448782284367700447847781711228005537893777228
4703177909757910941704809576561235753602658221278618745828702186457862298348409300733206257372113293
4427509637575983410884630686177012074138955455004931867187733173251974489811339569091702040649236815
2702444419265190075821626109055384330095555657872833758443936533855843067619694768930762339542572807
8654726038570390674714600345577103195962920082635315036068832510350332897153481221339903528122451853
6305763471013161616901348398388498606119250353205319386919910663696693585081272940693527835899821947
4692298873143110340850973113197648994468470532627945700519405358214681614528291594849107233778178691
2733894680329678978593984516536612730850554268515269680027201523348670406686624516367776329654706077
9172480945920396904147707208213922988733688708784415701704020199685745954051365055383290082393482810
4601874358573990011072595583137600660561113873874081890406295729433137643671747653582708314554812236
4955134972313061905469937787515879903287278189699750573820112783112441712751739090952028165570075257
8508831120105699263815521935497694747335038184165482852493988006772593847316213260128715365551815410
1792257176336400140323470008443385369583519340568237429824834805154501463633145987789198392483264752
9598628564255962439271941537397238870632226003191158092007061143247814795791471911283411853289872619
8763970338019044587543431500517447771335001602113091428506337929317903972818876028355450609521703252
8583940060277007911468988026051019979568991721730805023670848039314844089161514835231484051963265539
5932724686680795434226160727016649510582525478101947015611208459625085749211565996138827489992195087
3590821269714042576109793633513001013497414456171404713349306420812650730435380945514220378654950392
5978751898257558498892202744310528981708735016411852344286198526809822442423752155164828653151618195
4274141277547174659066173270413110005099986670953284101030879500891205702583881452097975616848895962
6987238471513118697395142442334189209131227763805638839498851409359010305861251178269734648443542844
2845641234665180538766447893650996118572572782539535893950498447981511889051112427072710988703664972
5760960581968436453411347514368341762497298693765465776550008684480527363769009243289422541421149035
9046750855416484492645331295272640286346772564852682400932747184224863591835512635580508934228904760
1980215049035203053573026260398379196687860917979151967325865492463407612168733638271055388798276416
6310287727644922503165526357398490950733040840129721738065640644713890371111055420398099667767140246
2289254193966908128255330595555949875834296896648091883925721190930983924670317863324472614072230332
3993764487446269692721398835436687465860030206550383640571274334983490505117370252277866499254937978
2444191053369307676768536830738103942240026358318853585493006050072682536186492403699587334154882936
5672133667636421874358954020666114198320805533772987959467309938698229985276501791004008551859694049
1289895913764347714882784451611136358419034401067104786603691882363354177514508654662044315513724328
6744638986066606560701821985136475870706501145162681195173147460593251359350790385520893129204338653
5810666293351978949139024886984508518100017206070943343025651519531140415664898731366212571233778658
1021987492675512964744510439905594233994584849814904115207995114269975690157912857306313651463040181
0568028888444457341218844727373201314591892874838788425746313274975116696877938284192410410932629698
7060834873924662731612284063792340061487107288890567802221567304729621478798353331776232096750780194
7668847591477123720525077599971789998336552324685131344129013050441159394295908900290961539847693096
3618691640379258294936378152232307319301140356749727150365260569292251751352435299604905404757474726
3021089057648917216798523361502438863951056578335804354712998976012869920497909471087482393419222032
9101342129836513139278518745524341730855808270333258845880719737995481458658305740015852431902549652
2252343559082541923932926495234249473822370201798253580538538349885640535404234688203936258996253021
1261339277408531272284477466972409439825685901304448481769761230562181150989557870018151064160195285
1152…
Новое самое большое простое число было найдено исследователем и бывшим сотрудником Nvidia Люком Дюрантом. Для его поиска энтузиаст развернул собственный вычислительный кластер в облаке. При этом расчеты проводились не на процессорах, а на видеокартах.
Как сообщается на сайте GIMPS, первый результат поиска, свидетельствующий о высокой вероятности того, что новое число действительно является простым, Дюрант получил 11 октября. На следующий день исследователь убедился в результате с помощью контрольного алгоритма (теста Люка — Лемера) — тот однозначно подтвердил простоту найденного числа. Затем результат Дюранта был перепроверен несколькими экспертами с помощью разных программ, реализующих тот же алгоритм, причем вычисления проводились как на графических картах, так и на обычных процессорах. 21 октября GIMPS официально объявила об открытии нового числа.
Как и подавляющее большинство рекордно больших простых чисел, открытых за последние столетия, новое число относится к числам Мерсенна, то есть может быть представлено в форме степеней двойки за вычетом единицы. Французский математик Марен Мерсенн внес значительный вклад в исследование простых чисел в XVII веке, хотя сами числа обсуждались еще древними греками.
Самые первые числа Мерсенна — это 1, 3, 7, 15, 31 и 63, то есть 2¹−1, 2²−1, 2³−1, 2⁴−1, 2⁵−1, 2⁶−1 и так далее. Как видно, не все они являются простыми — 1, 15 и 63 к ним не относятся. Кроме того, не все простые числа являются числами Мерсенна, — например, 11, 13 и 17 в форме степени двойки представить нельзя.
Тем не менее числа Мерсенна действительно превалируют в историческом ряду рекордсменов — прежде всего потому, что их поиск существенно легче, чем поиск простых чисел другого типа. Для чисел Мерсенна существует наиболее быстрый и эффективный алгоритм проверки — тот самый тест Люка — Лемера, сформулированный Эдуардом Люка в 1878 году и доказанный Диком Лемером в 1930-м. Сложность проверки простоты числа с помощью этого теста при этом растет с квадратом длины числа в двоичном представлении, поэтому поиск все новых простых чисел требует кратного увеличения вычислительных ресурсов.
Сейчас поиск новых рекордно больших простых чисел преимущественно проводится не университетскими математиками, а волонтерами GIMPS. В результате полтора десятка рекордов за последние десятилетия принадлежат именно этому сетевому сообществу. Простые числа широко используются в некоторых важных современных алгоритмах шифрования (например, RSA), и в этом смысле они имеют конкретное практическое применение. Однако это не касается рекордно больших простых чисел с миллионами разрядов в десятичной записи, они для криптографии не нужны. Их поиск — задача прежде всего эстетическая, хотя в прошлом она и дала несколько важных результатов в теории алгоритмов и компьютерных науках.
«Медуза»