Откриването на най-голямото просто число на Мерсен: Технологичен пробив в математическите изследвания
Най-голямото известно просто число —
\(2^{136\,279\,841}-1\) с над 41 милиона цифри
На 12 октомври 2024 г. Люк Дюрант открива ново просто число на Мерсен: \(M_{136279841}=2^{136\,279\,841}-1\). То има 41 024 320 десетични цифри и става най-голямото известно просто число, като надминава предишния рекорд с повече от 16 милиона цифри. Така приключва 28-годишната поредица от рекордни прости числа, открити с помощта на обикновени персонални компютри. Този път изчисленията са извършени чрез облачна мрежа от хиляди графични процесори, разположени в 24 облачни региона в 17 държави.
Откритието
На 12 октомври 2024 г. Люк Дюрант, изследовател от Сан Хосе, Калифорния, открива, че числото \(2^{136\,279\,841}-1\), обозначавано с \(M_{136279841}\), е просто. То е най-голямото известно просто число и същевременно 52-рото известно просто число на Мерсен. С 41 024 320 цифри то надминава предишния рекорд — \(2^{82\,589\,933}-1\), открит от GIMPS през декември 2018 г. — с над 16 милиона цифри. В официалния списък на GIMPS \(M_{136279841}\) заема условно 52-ро място и е означено с \(52^\ast\). Макар всички показатели в съответния интервал вече да са проверени поне веднъж, не всички резултати са преминали окончателна повторна проверка. Поради това все още не е изключено да бъде открито друго, по-малко просто число на Мерсен, което да промени поредното място на \(M_{136279841}\) в списъка.
Ако цифрите му се произнасят една по една със скорост две цифри в секунда, прочитането би отнело приблизително 5700 часа, или около 237 денонощия без прекъсване. При около 2700 цифри на страница отпечатването на цялото число би изисквало над 15 000 страници — обем, съпоставим с десетки големи печатни томове.
Думата „известно“ тук е особено важна. Най-голямо просто число не съществува, защото още Евклид доказва, че простите числа са безкрайно много. Рекордът показва само кое е най-голямото просто число, открито и проверено до този момент.
Кой е Люк Дюрант и как откри числото
Люк Дюрант е изследовател и бивш служител на NVIDIA, добре запознат с архитектурата и възможностите на графичните процесори. За разлика от предишните открития на GIMPS, направени с помощта на персоналните компютри на доброволци, Дюрант изгражда своеобразен облачен суперкомпютър. Той включва хиляди сървърни графични процесори, разположени в 24 облачни региона в 17 държави.
Благодарение на тази инфраструктура Дюрант може едновременно да проверява голям брой числа на Мерсен за простота. Такъв обем от изчисления би бил непостижим за отделен доброволец, разполагащ само с един персонален компютър. Първият положителен резултат е получен на 11 октомври 2024 г. чрез тест за вероятно просто число (PRP), извършен с графичен процесор NVIDIA A100 в Дъблин. На следващия ден простотата на числото е доказана чрез теста на Люка–Лемър, извършен с графичен процесор NVIDIA H100 в Сан Антонио. След това резултатът е потвърден независимо с различни програми и на различни хардуерни платформи. Последната проверка приключва на 19 октомври.
Числата на Мерсен: кратка история
Число на Мерсен се нарича всяко число от вида \(M_n = 2^n - 1\), където \(n\) е положително цяло число. Когато \(M_n\) е просто, то се нарича просто число на Мерсен; в такъв случай показателят \(n\) задължително също е просто число и обикновено се означава с \(p\). Тези числа носят името на френския монах, философ и математик Марен Мерсен (1588–1648), който през XVII век подробно изследва числата от вида \(2^p - 1\) и формулира известна хипотеза за стойностите на \(p\), при които те са прости.
Наистина, ако \(p = ab\), където \(a, b > 1\), тогава \[2^{ab}-1=(2^a-1)\bigl(1+2^a+2^{2a}+\cdots+2^{(b-1)a}\bigr).\] Следователно \(2^p - 1\) е съставно число. Обратното твърдение обаче не е вярно: ако \(p\) е просто число, от това не следва непременно, че \(2^p - 1\) също е просто.
Рекордите за най-голямо известно просто число често принадлежат на числа на Мерсен. Причината е специалната им форма \(2^p - 1\), която позволява използването на теста на Люка–Лемър и на бързи алгоритми за работа с огромни цели числа.
Нови прости числа на Мерсен се откриват рядко и през неравномерни интервали — понякога между две открития изминават няколко години. Все още не е известно дали съществуват безкрайно много прости числа на Мерсен.
На новото просто число на Мерсен съответства съвършеното число \[2^{136\,279\,840}\bigl(2^{136\,279\,841}-1\bigr),\] което има точно 82 048 640 десетични цифри — два пъти толкова цифри, колкото има \(M_{136279841}\).
Тестът на Люка–Лемър
Как се проверява дали число с десетки милиони цифри е просто? Проверката чрез пробно деление, тоест чрез последователно изпробване на възможни делители, е практически неприложима за число с такъв размер. Вместо това се прилага тестът на Люка–Лемър, предложен от френския математик Едуар Люка и по-късно усъвършенстван от американския математик Дерик Хенри Лемър. Тестът е предназначен специално за числата на Мерсен и използва особената им форма, което значително улеснява проверката за простота. Първоначалният PRP тест показва, че числото е вероятно просто, а окончателното доказателство е получено чрез теста на Люка–Лемър.
Графични процесори и специализиран софтуер
До появата на специализираните програми за графични процесори търсенето в GIMPS разчита основно на централните процесори (CPU) в компютрите на доброволците. С увеличаването на показателя \(p\) и на размера на проверяваните числа всяка отделна проверка изисква все повече време и изчислителни ресурси. Навлизането на графичните процесори (GPU) съществено променя начина, по който се организира търсенето.
Дюрант използва GpuOwl — специализиран софтуер, създаден от Михай Преда за извършване на тестове за простота на числа на Мерсен върху графични процесори. Всяка итерация зависи от резултата на предходната, затова отделните итерации не могат да се изпълняват паралелно. Графичните процесори ускоряват аритметичните операции във всяка стъпка, особено умножението и повдигането на квадрат на числа с милиони цифри. Облачната мрежа му осигурява изчислителна мощ, недостижима за един обикновен персонален компютър.
Проектът GIMPS
GIMPS (Great Internet Mersenne Prime Search) е основан през 1996 г. от Джордж Уолтман с идеята да обедини изчислителните ресурси на хиляди доброволци по целия свят. Участниците използват различни безплатни програми за централни и графични процесори, сред които Prime95, MPrime, GpuOwl, PRPLL и Mlucas. Сървърната система PrimeNet разпределя задачите, приема резултатите и координира повторните проверки.
От основаването си през 1996 г. GIMPS е открил последните 18 известни прости числа на Мерсен. Основната заслуга за откритието е на Люк Дюрант, но то става възможно и благодарение на създателите на използвания софтуер, администраторите на PrimeNet и хилядите доброволци в проекта. Поради това в официалното съобщение на GIMPS наред с Люк Дюрант са посочени Михай Преда, Джордж Уолтман, Арън Блосър и останалите участници. Дюрант обявява, че възнамерява да дари наградата от 3000 долара на математическия отдел на Училището по математика и природни науки на щата Алабама (Alabama School of Math and Science).
Американската организация Electronic Frontier Foundation (EFF) предлага награда от 150 000 долара за първото открито просто число с поне 100 милиона десетични цифри. Сегашният рекорд от малко над 41 милиона цифри все още не достига тази граница.
Приложения и значение
Простите числа имат фундаментална роля в теорията на числата и в редица криптографски алгоритми. Самото число \(M_{136279841}\) обаче няма непосредствено приложение в широко използваните криптографски системи: за практическите алгоритми обикновено се избират прости числа с конкретен размер и подходящи свойства, а не най-големите известни прости числа. Значението на откритието е преди всичко научно и изчислително.
С числата на Мерсен е свързан и известният генератор на псевдослучайни числа Mersenne Twister, чийто период е равен на простото число на Мерсен \(2^{19937}-1\). Генераторът се използва широко при симулации и числени експерименти, но стандартната му версия не е криптографски сигурна и не е подходяща за създаване на пароли или криптографски ключове.
Изчисленията с огромни цели числа натоварват силно процесора и оперативната памет, а възникналите аритметични грешки могат да бъдат открити. Поради това Prime95 се използва широко и за стрес тестове на компютърни системи — например за установяване на проблеми с охлаждането, грешки в паметта или нестабилни настройки при овърклок.
Откритието на \(M_{136279841}\) показва, че графични процесори, разположени в центрове за данни в различни държави, могат да бъдат обединени в една ефективна изчислителна система. Подобна инфраструктура вероятно ще играе все по-голяма роля при бъдещото търсене на рекордни прости числа.
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7. клас
- ›НВО по математика след 10. клас
- ›Кандидатстудентски изпити по математика
- ›Подготовка по математика за ISEE, SAT и A Level
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: математически анализ, линейна алгебра, аналитична геометрия, диференциални уравнения, теория на вероятностите, статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар