Оригінал тексту під авторством Edson Smith доступний за посиланням.

У серпні 2008 року на одному з комп’ютерів, що належать до
Програми обчислень (PIC) факультету математики
Каліфорнійського університету у Лос-Анджелесі , було виявлено
нове число Мерсенна. Виявляється, це число є найбільшим,
відомим у світі простим числом. Тому відкриття викликало такий
великий інтерес. Намагаючись заощадити час та енергію кожного,
я подумав, що виставлю інформацію в Інтернеті у форматі FAQ.
Оскільки деякі питання, що я отримав, надійшли від людей, які не
мають технічних знань (включаючи дітей), ці FAQ часто не є
технічним. Хоча ви все одно повинні знати, що таке прості числа.
Однак, змушений попередити: хоча я працюю на факультеті
математики, я системний адміністратор, а не математик! Якщо ви
шукаєте серйозну інформацію про Число Марсенна, пропоную
вам відмінний веб-сайт Кріса Колдвелла Числа Мерсенна: історія,
теореми та списки. Інші цікаві сайти: сторінка Вольфрама про
Числа Мерсенна і цікаві цифри та назви Числа Марсенна від
Лендона Курта Нолла.
А тепер, до питань!

П: Що ж таке Число Мерсенна?

В: Якщо коротко, є такий підклас натуральних чисел під назвою
Числа Мерсенна. Вони названі на честь Марена Марсенна,
математика 17-го сторіччя. На момент написання, існує менш ніж
50 відомих чисел Мерсенна.
Усі числа Мерсенна виглядають як 2^P -1, де P — відоме натуральне
число. Перше число Мерсенна — 3, тому що 2 ^2 -1 = 3. Зауважте, що
показник P є простим числом, у цьому випадку 2. Наступне число Мерсенна — 7, оскільки 2 ^3 — 1 = 7, де P є простим числом 3. Далі
йде 31 (2^ 5 — 1), потім 127 (2^ 7 — 1), 8191 (2^ 13 — 1) та 131071 (2^ 17 — 1).
Як бачите, після декількох перших чисел, числа Мерсенна стають
більше дуже швидко. Ось гарна табличка з відомими числами
Мерсенна, що надасть певну перспективу.

Найменші з цих цифр були відомі ще за часів античності, але
навіть у 1951 році було виявлено лише 12. За останні 50 років ще
кілька десятків було виявлено за допомогою комп’ютерів.
Нещодавно відкриті числа Мерсенна надзвичайно великі, з
мільйонами цифр. Число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі має близько 12,9 мільйонів цифр у
довжину.

Зауважте, що всі числа Мерсенна є простими числами, але не всі
прості числа — числа Мерсенна.

П: Що таке число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі? Чому воно таке особливе?

В: Число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі — це перше число, яке має понад 10 мільйонів цифр.
Воно було відкрито 23 серпня 2008 року на факультеті
математики Каліфорнійського університету у Лос-Анджелесі.
Всі числа Мерсенна особливі, оскільки вони дуже рідкісні, але ця
особливість привернула особливу увагу, оскільки вона претендує
на приз (див. нижче).

Число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі — 243112609 — 1. Фактичне число — 12 978 189 цифр.
Якщо ви дуже зацікавлені, Лендон Курт Нолл, який вже давно
досліджує число Мерсенна, зрозробив його ось тут . Якщо ви ну,
дуже-дуже зацікавлені, він також надає ціле число англійською
мовою (всі 328 мегабайт) тут .

П: Це перше число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі?

В: Взагалі-то, це восьме число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі!

У 1952 р. Професор Рафаель Робінсон знайшов 5 нових чисел
Мерсенна, використовуючи Західний автоматичний комп’ютер
(SWAC) стандартів Каліфорнійського університету у Лос-
Анджелесі, один з найшвидших комп’ютерів свого часу. Були
відкриті 13те та 17те числа Мерсенна, і кожне мало сотні цифр.
Робінсонові числа Мерсенна були знайдені першими за 75 років, і
були першими, які були відкриті за допомогою цифрового
комп’ютера.

У 1961 році, математик Каліфорнійського університету у Лос-
Анджелесі, Олександр Гурвіц, відкрив 19те та 20те число
Мерсенна за допомогою комп’ютерного центру IBM 7090
Каліфорнійського університету у Лос-Анджелесі. Кожне з цих
чисел мало понад 1200 цифр.

І тепер, через 47 років, традиція Каліфорнійського університету у
Лос-Анджелесі знаходити числа Мерсенна продовжується!
П: Хто шукає числа Мерсенна? І як вони їх знаходять?
В: Тисячі людей, використовують десятки тисяч комп’ютерів та
беруть участь у Широкомасштабному проекті добровільних
обчислень з пошуку простих чисел Мерсенна (GIMPS) —
організоване зусилля, присвячене пошуку чисел Мерсенна. Це
одне з багатьох поточних зусиль у сфері розподілених обчислень, і, можливо, найбільш успішне.

Пошук дуже добре організований. Добрі люди в Primenet
координують ці зусилля протягом останніх 12 років і надають
відмінну програму Prime95 для всіх, хто хоче її запустити. Вони
стежать за тим, які номери було протестовано та забезпечують стійкий потік неперевірених кандидатів у спільноту GIMPS.

Учасники GIMPS оцінюються відповідно до їх продуктивності.
Ви можете знайти нас під назвою UCLA_Math. Ми, як правило,
десь між 40-м і 55-м місцями в рейтингу.

Для того, щоб перевірити лише один номер кандидата, у машини
може зайняти місяць. Але використовуючи силу окремих
комп’ютерів, підключених до інтернету по всьому світі, можна
досягнути швидшого прогресу.

П: Які шанси знайти число Мерсенна?

В: згідно з проектом GIMPS, можливість того, що будь-яке число кандидата буде числом Мерсенна, складає 1 з 150 000.
П: Як насправді тестують числа, щоб виявити, що вони є
числами Мерсенна?

В: Існує багато чисел форми 2 ^P — 1, але не всі з них — числа
Мерсенна. Існує декілька прийомів для перевірки цих чисел, щоб
побачити, що це числа Мерсенна. Але початковим методом
вважається спроба розкласти коефіцієнт показника кандидата P, а
потім спробувати розкласти коефіцієнт числа кандидата, 2^P-1,
використовуючи малі числа.

Існує 75-річний алгоритм під назвою тест Лукаса-Лемера, який
всіма визнаний як найкращий інструмент для тестування чисел
Мерсенна. Програма Prime95 постійно використовує цей метод, а
також деякі інші. Пояснення виходить за обсяги цього документа,
але зацікавлений читач може більше дізнатися тут.

П: Гаразд, навіщо люди шукають числа Мерсенна? Для чого
вони потрібні?

В: З тих же причин, коли люди піднімаються в гори, плавають
невідомими морями і досліджують космос. Це виклик! Цікаво
доторкнутися до обчислювальної математики та шукати щось невідоме, те, чого як ви вважаєте не існує. Як бонус, на відміну
від старих дослідників, ми сидимо в зручних офісних стільцях,
під час наших пошуків!

Це не означає, що числа Мерсенна не мають математичного
значення. Вони, безумовно, цінні в області криптографії, і можуть
мати інші види використання, які ще не були виявлені.

Дослідник простих чисел Кріс Колдвел досліджує цю тему більш
глибоко у своїй статті «Чому люди знаходять ці прості числа?»

П: Окрім виклику, чому ви вирішили приймати участь?

В: Як це було на багатьох інших сайтах, ми зрозуміли, що наша
велика (75 місць) PIC / Математична комп’ютерна лабораторія
використовувала лише частину наявної потужності центрального
процесора. Замість того, щоб дозволити всім цим циклам
витрачати енергію даремно, ми розглянули ряд розподілених
обчислювальних проектів, визначивши, що GIMPS найкраще
підходить для нас. Окрім того, що GIMPS є математичним
проектом, ми виявили, що він дуже добре написаний та не
заважав недосвіченим комп’ютерним користувачам (це не
відносилось до іншого програмного забезпечення, яке ми
досліджували).

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

П: Що ви зробили для зауску? Чи було важко?

В: Програмне забезпечення GIMPS Prime95 дуже легке з точки
зору системної адміністрації. Його легко встановити, і воно не
потребує технічне обслуговування.

Програмне забезпечення Prime95 регулярно оновлює інформацію
про стан обробки на центральних комп’ютерах Primenet. Якщо
машина, на якій вона працює, ламається, то обчислення знов
почнуть працювати там, де вони зупинилися, після ввімкнення
комп’ютера. Якщо окремий блок не працює протягом тривалого
часу, Primenet поверне номер і призначить його іншому
користувачеві. А також призначить новий номер, коли машина
знов буде працювати.

П: Як працює верифікація?

В: Коли число Марсенна знайдене, формальне оголошення не
проводиться, поки незалежна сторона не підтвердить цю вимогу.
З винятково великими числами, такими як ці, завжди є невелика
можливість обчислювальних проблеми з використаним
алгоритмом, або з процесором самого комп’ютера (класичний
приклад — проблема з рухомую комою Intel).

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

П: Коли відбулося відкриття? Який комп’ютер це був?

В: Число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі зареєстрували 23 серпня 2008 року на комп’ютері під
назвою zeppelin.pic.ucla.edu, Dell Optiplex 745 з операційно/
системою Windows XP та процесором Intel Core 2 Duo E6600, що
працює на частоті 2,4 ГГц. Назва «zeppelin»; була частиною нашої
класичної серії Rock Band комп’ютерів.

П: А що там з приводу призових грошей?

В: Electronic Frontier Foundation (EFF), перша організація
інтернет-цивільних свобод, спонсує нагороди «Cooperative Computing Awards«. Ці нагороди мають на меті «заохочувати
звичайних користувачів Інтернету робити внесок у вирішення
величезних наукових проблем», а також надавати призові гроші за
досягнення певних орієнтирів.

EFF має постійну винагороду в розмірі 100 000 доларів США за
відкриття першого простого числа з 10 мільйонами цифр. Число
Мерсенна від Каліфорнійського університету у Лос-Анджелесі
має майже 12,9 мільйонів цифр і відповідає критеріям нагороди.
Як тільки офіційні результати будуть опубліковані в відповідному
журналі, приз віддадуть. Це вібудеться в 2009 році найближчим
часом.

За попередньою угодою, лише 50% нагороди належить
першовідкривачеві простого числа з 10 мільйоннами цифр. 25%
призначено на благодійність, і, зважаючи на колективну природу
GIMPS, основну частину від 25% віддадуть першовідкривачам
інших чисел Мерсенна, при цьому невелика сума переходить до
GIMPS.

П: А що це я чую про плакат? Чи буде такий для числа
Мерсенна від Каліфорнійського університету у Лос-
Анджелесі?

В: Роками компанія під назвою Perfectly Scientific, створює
плакат найбільшого просто числа, відомого на даний час. Плакат
для M44, випущений у 2006 році, використовував надзвичайно
малі шрифтів, щоб стиснути 9,8 мільйона цифр на одному постері
розміром 29 дюймів на 40. Компанія запропонувала ювелірну
лупу разом з плакатом, щоб його можна було прочитати.

Річард Краандалл з Perfectly Scientific нещодавно зв’язався зі
мною, для того щоб повідомити, що плакат числа Мерсенна від
Каліфорнійського університету у Лос-Анджелесі тепер можна придбати. Він коштує $ 99, без рамок і доступний на веб-сайті Perfect Scientific.

П: Як щодо інших нещодавно відкритих чисел Мерсенна?

В: Через два тижні після того як було відкрито число Мерсенна
від Каліфорнійського університету у Лос-Анджелесі, інші 10
мільйонів цифр плюс чисел Мерсенна були виявлені Гансом-
Майклом Елвініче у Німеччині. Розміром у 11.2 мільйони цифр,
десь на 10% менше від числа Мерсенна від Каліфорнійського
університету у Лос-Анджелесі.

Це не перший випадок, коли числа Мерсенна були виявлені поза
порядком. У 1988 році Колквіт і Уельс виявили менше число
Мерсенна, ніж попередні два, відкриті у 1983 і 1985 роках.
На момент написання даного матеріалу число Мерсенна від
Каліфорнійського університету у Лос-Анджелесі вважається 46-м
числом Мерсенна (названим «M46» спільнотою, що шукає числа
Мерсенна), хоч і було виявлено 45м. Число Елвініче — це M45, але
було відкрите 46-м.

Ще одним ускладнення — не всі потенційні прості числа між M39
(відкрите у 2001 році) та число Мерсенна від Каліфорнійського
університету у Лос-Анджелесі були перевірені. І в майбутньому
вони можуть бути знайдені в ширшому діапазоні. Якщо так й
буде, число Мерсенна від Каліфорнійського університету у Лос-
Анджелесі отримає «просування» до M47.

Я щиро дякую всім людям, які допомогли мені з цим документом.
Дякую Селу Зап’єн та Мері Маргарет Сміт за їх відмінну
коректуру, і Джиму Картеру за допомогу зі структурою та
організацією. Я особливо хочу подякувати Роберту Джонсону,
який переконався, що кожне висловлювання, яке я зробив, було
дійсним і який обережно виправив мої численні непорозуміння.
Ці FAQ створені та розроблені Едсоном Смітом. Остання правка
липень, 2018.