GIMPS

GIMPS (Great Internet Mersenne Prime Search) — широкомасштабний проєкт добровольчих обчислень з пошуку простих чисел Мерсенна.

Цілі і методи проекту

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

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

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

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

Практична значущість

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

Крім того, прості числа Мерсенна відіграють важливу роль у деяких проблемах теорії чисел. Наприклад, Евклід виявив, що якщо число $M_{p} = 2^{p} - 1$ просте, то число $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 року число $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-бітова версій)

Примітки

↑ The Largest Known Primes. Листопад 22 2008. Архів оригіналу за 22 листопада 2008.(англ.)
↑ GIMPS: List of Known Mersenne Prime Numbers [Архівовано 15 березня 2016 у Wayback Machine.](англ.)
↑ Record 12-Million-Digit Prime Number Nets $100,000 Prize [Архівовано 5 серпня 2011 у Wayback Machine.](англ.)
↑ EFF Cooperative Computing Awards [Архівовано 9 листопада 2008 у Wayback Machine.](англ.)
↑ Where is the next Mersenne prime? [Архівовано 9 березня 2021 у Wayback Machine.](англ.)
↑ PrimeNet Activity Summary [Архівовано 12 січня 2021 у Wayback Machine.](англ.)
↑ Download GIMPS client [Архівовано 18 жовтня 2013 у Wayback Machine.](англ.)

Посилання

Офіційний сайт (англ.)
Інструменти і розширена статистика GIMPS [Архівовано 1 квітня 2022 у Wayback Machine.] (англ.)
Офіційний форум GIMPS [Архівовано 13 січня 2021 у Wayback Machine.] (англ.)
Рейтинг учасників в проєкті GIMPS [Архівовано 13 січня 2021 у Wayback Machine.] (англ.)
Рейтинг команд у проєкті GIMPS [Архівовано 13 січня 2021 у Wayback Machine.] (англ.)

[1] The Largest Known Primes. Листопад 22 2008. Архів оригіналу за 22 листопада 2008.(англ.)

[2] GIMPS: List of Known Mersenne Prime Numbers [Архівовано 15 березня 2016 у Wayback Machine.](англ.)

[3] Record 12-Million-Digit Prime Number Nets $100,000 Prize [Архівовано 5 серпня 2011 у Wayback Machine.](англ.)

[4] EFF Cooperative Computing Awards [Архівовано 9 листопада 2008 у Wayback Machine.](англ.)

[5] Where is the next Mersenne prime? [Архівовано 9 березня 2021 у Wayback Machine.](англ.)

[6] PrimeNet Activity Summary [Архівовано 12 січня 2021 у Wayback Machine.](англ.)

[7] Download GIMPS client [Архівовано 18 жовтня 2013 у Wayback Machine.](англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]