Знайдено просте число довжиною в п'ять романів «Війна і мир»

Візуалізація розкладання чисел на дільники. Кожна крива, складена з півкіл, зображає натуральне число n. Вона перетинає числову пряму в точках n, 2n, 3n і так далі. Таким чином, всі криві, що входять в точку на числовій прямій, - суть все дільники даного числа 

На початку лютого 2013 математик Кертіс Купер, учасник проекту GIMPS (Great Internet Mersenne Prime Search), виявив 48-е просте число Мерсенна. Десятковий запис такого числа складається з більш ніж 17 мільйонів знаків. Для порівняння, у «Війні і мирі» Толстого всього приблизно 3,1 мільйонів символів. За своє відкриття професор Університету Центрального Міссурі цілком може отримати три тисячі доларів. Втім, він, як і інші учасники GIMPS, займається пошуком простих чисел Мерсенна зовсім не заради грошей.

Перекази давнини глибокої

Числа Мерсенна - це числа виду 2^p - 1, де p - довільне ціле число, яке називають показником. Ці числа вабили математиків з найдавніших часів, орієнтовно з Евкліда (приблизно 300 рік до нашої ери), правда, до XVI століття вчені вважали, що всі ці числа прості (тобто діляться тільки на себе і одиницю). Це, звичайно ж, невірно - досить поглянути на четверте число Мерсенна: воно дорівнює 15 і зображається у вигляді добутку 3 і 5.

Мабуть, першим, хто помітив, що не всі числа Мерсенна з простими показниками (відомо, що для складових показників число Мерсенна не може бути простим) є простими, був Худальрікус Региус в 1536 році. Він показав, що при p = 11 отримане число - це 2047 - виявляється складеним, оскільки зображається у вигляді добутку 23 і 89.

У XVII столітті пошук простих чисел Мерсенна став досить популярною серед математиків розвагою. В 1640 до вивчення цих чисел підключився знаменитий П'єр Ферма - він показав, що роботи його попередників, в яких стверджувалася простота чисел для p = 23 і p = 37, були помилкові. Але взагалі, Ферма не був унікальний у своєму інтересі до цього предмета, в історії цих чисел відзначилися багато відомих учених: Ейлер, Паскаль, Галілео, Гюйгенс.

Ім'я ж своє числа Мерсенна отримали на честь французького ченця Марена Мерсенна, філософа, теолога і математика. Він натрапив на ці числа в пошуках універсальної формули, яка дозволяла б перераховувати всі прості числа. У 1648 році він випустив працю Cogitata Physica-Mathematica, в якому висловив припущення, що числа виду 2^p - 1 повинні бути простими для показників 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 і складовими для всіх інших цілих чисел, що не перевершують 257. Звідки взялася така гіпотеза, достеменно невідомо - сучасники сумнівалися, що Мерсенн міг розібрати всі ці випадки вручну, та й він сам, кажуть, це визнавав.

Втім, ця гіпотеза стала популярною вже після смерті автора. Так часто буває з деякими математичними твердженнями - з абсолютно незрозумілої причини вони опиняються в центрі уваги безлічі математиків. Можливо, на руку їй зіграла, як і у випадку з легендарною теоремою Ферма, простота формулювання. Як би там не було, але з рядом Мерсенна вчені розібралися тільки в середині XX століття - тоді вони встановили, що список показників, що дають прості числа Мерсенна і не переважаючих 257, виглядає таким чином: 2, 3, 5, 7, 13, 17 , 19, 31, 61, 89, 107 і 127. Це і є перші 12 простих чисел Мерсенна.

Наш час

Треба сказати, що перемозі над гіпотезою Мерсенна сприяла поява так званого тесту Люка-Лемера. Суть його полягає в наступному: для фіксованого числа Мерсенна обчислюється деяка рекурентна послідовність. Рекурентна формула для членів цієї послідовності, по-перше, відносно проста, а по-друге, для перевірки потрібно взяти p - 2 члени послідовності, де p - непарний простий показник числа Мерсенна. Складність роботи алгоритму складає близько третього степеня log n, де n - саме число Мерсенна. Використання різного роду методів швидкого множення, як, наприклад, методу Шенхаге - Штрассена, дозволяє трохи прискорити роботу, проте кардинально складності не змінює.

Многочлен Джонса. Формула для генерації простих чисел: множина невід'ємних значень цього многочлена від 26 змінних, для всіляких наборів з 26 натуральних чисел дає всі прості числа.

 

 

Потрібно розуміти, що це вкрай низька обчислювальна складність, тобто алгоритм працює досить швидко. Для порівняння, найшвидший детерміністський алгоритм перевірки простоти з існуючих - тест Агравала-Каяла-Саксени c поліпшеннями Померанса-Ленстра - має складність порядку (log n)⁶. Відносну простоту програмування та низьку обчислювальну складність тесту Люка-Лемера вчені оцінили тільки з появою комп'ютерів.

У 60-ті роки минулого століття інтерес до чисел Мерсенна став спадати. Пов'язано це було з тим, що перспективи обчислювальної техніки на той момент бачилися досить туманними, а використання суперкомп'ютерів для пошуку великих простих чисел здавалося досить марнотратним. У 1968 році в Університеті Іллінойсу було відкрито 23-е просте число Мерсенна з показником 11213. На той момент це було настільки великим досягненням, що Пол Бейтман, який керував кафедрою теорії чисел в цьому університеті, замовив спеціальну печатку для кореспонденції, на якій, крім дати, красувався напис «2¹¹²¹³ - 1 - просте число».

У 1970-х роках інтерес до чисел Мерсенна знову активізувався. Причиною тому стала історія двох тоді ще американських школярів - Лаури Нікел і Лендона Нолла. Не особливо розбираючись в математичних тонкощах питання, вони написали програму для перевірки чисел Мерсенна на простоту за допомогою тесту Люка-Лемера і прогнали її на суперкомп'ютері в місцевому університеті. У результаті вони змогли знайти 25-е і 26-е прості числа Мерсенна з показниками 21 701 і 23 209 відповідно. Це були найбільші прості числа з відомих на той момент. Нолл після цього став володарем ще одного рекорду - в 1989 році він взяв участь у відкритті найбільшого простого числа, яке не є числом Мерсенна (це так зване просте число Амдала 6, назване так на честь робочої групи, яка відкрила його, і рівне 391581* 2²¹⁶¹⁹³-1).

Історія з відкриттям школярів потрапила на телеекрани, і пошук простих чисел Мерсенна знову повернувся в моду. Наступні успіхи у цій діяльності були пов'язані з суперкомп'ютерами Крей - один зі співробітників компанії-виробника Девід Словінскі написав програму для пошуку простих чисел Мерсенна, що працювала на цих машинах, поки вони не використовувалися. Нарешті, сучасний вигляд цей процес набув за допомогою програміста Джорджа Уолтмана, в 1995 році створив проект розподілених обчислень GIMPS (Great Internet Mersenne Prime Search).

Проект, призначений для роботи на i386, до кінця першого року існування налічував вже більше тисячі учасників. Це був перший дослідний проект розподілених обчислень в історії. Перше просте число Мерсенна (в даний час в рамках проекту відкрито вже 14 штук) стало відомо в 1996 році. Зараз програму, що працює під усіма основними операційними системами,може встановити собі будь-який бажаючий. Сумарна обчислювальна потужність проекту до кінця 2012 року становила вже 95 терафлопс.

48-е за рахунком і невелика премія

Найостаннішим відкриттям в проекті GIMPS стало виявлення 48-го простого числа Мерсенна. Це відкриття було зроблено математиком з Університету Центрального Міссурі Кертісом Купером. На прогонку тесту Люка-Лемера на одній з машин в університеті у Купера пішло 39 днів. Його результат був перевірений ще раз трьома незалежними користувачами, один з яких використовував 32-ядерний сервер, наданий компанією Новартіс.

Розміри нового числа потрясають - його запис у десятковій системі числення складається з 17425170 знаків. Для самого ж Кертіса це відкриття стало вже третім - раніше найбільші прості числа йому вдавалося виявляти в 2005 і 2006 роках.

У 2008-му рекорд Кертіса був побитий групою дослідників з Каліфорнійського університету в Лос-Анджелесі. Вони виявили просте число Мерсенна, в десяткового запису якого було 12978189 знаків. На момент відкриття це число було 45-м простим числом Мерсенна, проте через деякий час було відкрито ще два простих числа, менших цього (числа не завжди відкриваються у порядку зростання), тому його номер в даний час - 47. Саме воно до відкриття Купера було рекордсменом за розміром.

За відкриття GIMPS отримав премію в 100 тисяч доларів від фонду EFF, обіцяну за відкриття першого простого числа, записуваного більш ніж 10 мільйонами знаків. Отримані гроші проект розділив на невеликі премії для заохочення наступних відкриттів - так, Купер з 48-м числом Мерсенна претендує на три тисячі доларів.

Примітно, що з числами Мерсенна пов'язана велика кількість досі невирішених завдань. Наприклад, поки невідомо, чи нескінченна множина простих чисел Мерсенна. На закінчення хочеться згадати ще про одну чудову властивість чисел Мерсенна. Число називається досконалим, якщо воно дорівнює сумі всіх своїх власних (тобто додатних і відмінних від самого числа) дільників, включаючи 1. Наприклад, 6 - досконале, оскільки 6 = 3 + 2 + 1. Ще Евклід виявив, що число виду 2^{n - 1} (2ⁿ - 1) досконале, якщо в дужках стоїть просте число, тобто просте число Мерсенна з показником n. Пізніше Леонард Ейлер довів, що всі парні досконалі числа мають такий вигляд, де в дужках стоїть просте число Мерсенна. На даний момент невідомо жодного непарного досконалого числа, проте існують припущення, що шукати такі числа також слід за допомогою чисел Мерсенна.

Замість висновку

У допитливого читача, зрозуміло, може виникнути питання, навіщо взагалі потрібен пошук простих чисел Мерсенна. По-перше, обчислювальні навантаження, що стоять за тим же проектом GIMPS, вже не одного разу використовувалися для тестування обчислювальних потужностей - добре відомо, що Intel апробувала Pentium II і Pentium Pro саме на GIMPS.

По-друге, числа Мерсенна використовуються в ролі тестів для різного роду алгоритмів факторизації чисел. За великим рахунком, на розкладанні великих чисел на прості множники заснована значна частина методів сучасної криптографії. Отже і тут числа Мерсенна бувають корисні.

Нарешті, подібні проекти дозволяють зацікавити публіку в наукових проектах, залучити молодих людей до заняття справжньою наукою, нехай і у фоновому режимі власного комп'ютера. А цікавість у науці - це і є найголовніше.