GIMPS

Визначення того, чи є дане число простим, у загальному випадку не є тривіальною задачею. Тільки у 2002 році доведено, що вона має поліноміальну складність. Попри це, запропонований (і строго обґрунтований теоретично) детермінований алгоритм практично непридатний, зважаючи на його значну, хоча й поліноміальну, складність. Тому в криптографії з відкритим ключем, де застосовуються прості числа порядку ${\displaystyle 10^{300}}$, простоту як і раніше визначають за допомогою ефективних імовірнісних тестів, таких як тест Міллера — Рабіна. Важливо відзначити, що якщо для практики достатньо чисел, які є простими з імовірністю близькою до ${\displaystyle 1}$, то теорія таких чисел не сприймає: якщо про число стверджується, що воно просте, це повинно бути строго доведено. Ця різниця підкреслюється в поділі алгоритмів на ймовірнісні і детерміновані.

Відповіддю на питання, яке найбільше просте число[1] відоме людству, буде якесь із простих чисел Мерсенна. Числа Мерсенна мають вигляд ${\displaystyle M_{p}=2^{p}-1}$. Зауважимо, що простота числа ${\displaystyle 2^{p}-1}$ тягне простоту ${\displaystyle p}$; в іншому випадку ${\displaystyle p=xy}$ для ${\displaystyle x,y>1}$ і число ${\displaystyle 2^{p}-1=2^{xy}-1}$ не буде простим завдяки подільності на ${\displaystyle 2^{x}-1}$ (як, втім, і на ${\displaystyle 2^{y}-1}$).

Як видно з назви, метою проекту GIMPS є пошук нових простих чисел Мерсенна. Найбільше відоме на даний момент просте число ${\displaystyle M_{82589933}=2^{82589933}-1}$ знайдено в рамках проєкту GIMPS 7 грудня 2018 року і складається з 24 862 048 десяткових цифр. Більш того, 15 попередніх рекордів також встановлено учасниками GIMPS. Причина криється в наявності ефективного (детермінованого) критерію їх простоти, що носить ім'я тест Люка — Лемера. Для пошуку простих чисел Мерсенна сервер GIMPS роздає клієнтам прості «експоненти» ${\displaystyle p}$ для перевірки числа ${\displaystyle M_{p}}$ на простоту саме цим тестом.

На жовтень 2020 року відомо 51 просте число Мерсенна, при цьому напевно відомо порядкові номери перших 47 з них. Порядкові номери чотирьох найбільших відомих простих чисел Мерсенна поки точно не встановлено (між ними можуть виявитися інші, ще не відкриті прості числа Мерсенна).[2]

Прості числа Мерсенна цікаві вже тим, що вони стабільно утримують рекорд як найбільші відомі прості числа.

Крім того, прості числа Мерсенна відіграють важливу роль у деяких проблемах теорії чисел. Наприклад, Евклід виявив, що якщо число ${\displaystyle M_{p}=2^{p}-1}$ просте, то число ${\displaystyle M_{p}(M_{p}+1)/2=2^{p-1}(2^{p}-1)}$ досконале, тобто дорівнює сумі своїх дільників (приклади таких чисел: 6=1+2+3, 28=1+2+4+7+14, 496=1+2+4+8+16+31+62+124+248, а Ейлер згодом довів, що всі парні досконалі числа мають зазначений вигляд (питання про існування непарного досконалого числа відкрите досі).

Залишається відкритим питання про нескінченність кількості простих чисел Мерсенна і про їх асимптотику. Знайдені прості числа Мерсенна можуть служити відправною точкою для висунення й перевірки гіпотез про поведінку простих чисел Мерсенна.

На практиці прості числа Мерсенна застосовуються для побудови генераторів псевдовипадкових чисел з великими періодами (див. Вихор Мерсенна).

GIMPS виграла[3] грошовий приз 100 000 доларів США за відшукання простого числа з більше ніж 10 мільйонів десяткових цифр і має намір виграти аналогічні призи 150 000 і 250 000 доларів США, обіцяні[4] Electronic Frontier Foundation за відшукання простих чисел відповідно з більш ніж зі 100 мільйонів і 1 мільярда десяткових цифр. Із суми цього призу планується зробити виплати всім «відкривачам» попередніх простих чисел Мерсенна, авторам програмного забезпечення і авторам нових, ефективніших алгоритмів пошуку (якщо такі алгоритми будуть знайдені).

Отримати GIMPS премію 100 000 доларів США дозволило знайдене в серпні 2008 року число ${\displaystyle M_{43112609}=2^{43112609}-1}$, яке містить 12 978 189 десяткових цифр. Проте, щоб отримати премію 150 000 доларів США, доведеться перевіряти на простоту числа з більш ніж 100 млн десяткових цифр, кожне з яких за поточного рівня обчислювальної та алгоритмічної техніки зажадає більше трьох років.

Щодня в проєкті GIMPS вивантажують результати своїх обчислень сотні учасників. Щодо кожного з них проєкт веде статистику, публікує й регулярно оновлює рейтинги продуктивності/результативності. Для посилення змагального ефекту в проєкті реалізовано можливість об'єднання учасників у команди. В цьому випадку накопичена статистика учасника йде в залік не тільки йому, але і його команді. Як і для окремих учасників, проєкт веде й оновлює рейтинги команд.

Команди зазвичай формуються за місцем розташування учасників (країна або місто), за належністю до певної організації (навчальний заклад або компанія) чи просто з бажання підтримати ту чи іншу інтернет-спільноту.

Всього в проєкті більше 1000 команд. Абсолютна більшість з них зовсім невеликі — з одного або декількох учасників, багато хто вже давно перестали бути активними. Найбільші команди включають десятки/сотні учасників, нерідко — власників значних обчислювальних потужностей: від декількох особистих комп'ютерів до великого парку комп'ютерної техніки «підшефної» компанії або університету.

Нерідко за кожну сходинку в командних рейтингах розігрується неабияка боротьба. Деякі команди цілеспрямовано координують дії своїх учасників, щоб здійснити прорив у запланованому вигляді обчислень і в підсумку якомога швидше піднятися на вищі позиції. В цілому ж командний ТОП-10 усіх рейтингів відносно стабільний, підносять сюрпризи переважно нові учасники, які несподівано вступають у гру за ту або іншу команду. Саме тому команди завжди раді прибульцям, а старожили допомагають їм з налаштуваннями обладнання та програм, консультують щодо вибору найцікавіших видів обчислень.

Евристичні оцінки показують, що існують ще чотири невідомих простих чисел Мерсенна, які складаються менш ніж зі 100 мільйонів десяткових цифр, а найближче з них може складатися приблизно з 26 мільйонів цифр[5]. Детальну інформацію про їх можливий розподіл, а також про очікувані витрати на їх знаходження можна отримати на сторінці статистики.[6]

Клієнтська програма GIMPS проводить інтенсивні обчислення, постійно стежачи за їх точністю. Тому багато хто розглядає її як хороший інструмент для тестування стабільності роботи апаратної частини комп'ютера. Пікові навантаження і жорсткий контроль дозволяють легко виявляти проблеми з пам'яттю, кешем, шиною даних, розгоном і перегріванням процесора тощо. Для полегшення процедури тестування клієнт GIMPS надає можливість роботи в режимі «stress testing», коли обчислення проводяться для відомих простих чисел Мерсенна і результати обчислень звіряються з очікуваними.

Клієнтська частина ПЗ проєкту GIMPS доступна[7] для таких операційних систем:

• Microsoft Windows 7/Vista/XP/2008/2003/2000/NT/Me/98/95. Також є версія для 64-бітових варіантів Windows 7/Vista/XP/2008.
• Mac OS X
• GNU/Linux (64-бітова і 32-бітова версій)
• FreeBSD (64-бітова і 32-бітова версій)

• Офіційний сайт (англ.)
• Інструменти і розширена статистика GIMPS (англ.)
• Офіційний форум GIMPS (англ.)
• Рейтинг учасників в проєкті GIMPS (англ.)
• Рейтинг команд у проєкті GIMPS (англ.)