Число Мерсенна – Університет Каліфорнії в Лос-Анджелесі

Оригінал: https://www.math.ucla.edu/~edson/prime/

У серпні 2008 року нове просте число Мерсенна було виявлено на одному з комп’ютерів, що належать до Програми з обчислювальної техніки (PIC) кафедри математики Каліфорнійського університету в Лос-Анджелесі . Це число виявилося найбільшим відомим простим числом у світі, і відкриття викликало великий інтерес. Щоб заощадити час і енергію, я вирішив розмістити деяку інформацію в Інтернеті у форматі поширених запитань. Оскільки багато запитань, які я отримав, надійшли від людей із нетехнічним досвідом (включаючи дітей), цей поширений запит є нетехнічним. Однак ви повинні знати, що таке просте число.

Проте я змушений зробити таке застереження: хоча я працюю на факультеті математики, я системний адміністратор, а не математик! Якщо ви шукаєте серйозну інформацію про прості числа Мерсенна, я направляю вас на чудовий веб-сайт Кріса Колдвелла Прості числа Мерсенна: історія, теореми та списки. Інші цікаві сайти включають сторінку Вольфрама «Прості числа Мерсенна» та розважальний «Числа Мерсенна та імена» Лендона Курта Нолла.

А тепер до питань!

З. Отже, що таке просте число Мерсенна?

В. Коротше кажучи, існує певний підклас простих чисел, відомий як прості числа Мерсенна. Вони названі на честь Маріна Мерсенна, математика XVII століття. На момент написання цієї статті відомо менше 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 років за допомогою комп'ютерів було виявлено ще кілька десятків. Нещодавно відкриті прості числа Мерсенна вражаюче великі з мільйонами цифр. Довжина числа Мерсенна UCLA становить близько 12,9 мільйонів цифр.

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

З. Що таке число Мерсенна UCLA? Чому він особливий?

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

Усі прості числа Мерсенна є особливими, тому що вони дуже рідкісні, але це привернуло додаткову увагу, оскільки воно претендує на приз (див. нижче).

Просте число Мерсенна UCLA дорівнює 2 43112609 - 1. Справжнє число складається з 12 978 189 цифр. Якщо ви так схильні, давній дослідник числа Мерсенна Лендон Курт Нолл зробив це число доступним тут. Якщо ви дуже, дуже схильні, він також надає тут повний номер англійською мовою (всі 328 мегабайт).

З. Це перше число Мерсенна в UCLA?

В. Фактично, це восьме число Мерсенна від UCLA!

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

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

Тепер, через 47 років, традиція пошуку простих чисел Мерсенна продовжується!

З. Хто шукає прості числа Мерсенна? Як вони це роблять?

В. Тисячі людей, які використовують десятки тисяч комп’ютерів, беруть участь у Великому пошуку простих чисел Мерсенна в Інтернеті (GIMPS), організованому заході, присвяченому пошуку простих чисел Мерсенна. Це одна з багатьох поточних спроб у сфері розподілених обчислень і, можливо, найуспішніша.

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

Одній машині можуть знадобитися місяці, щоб перевірити лише один номер-кандидат, але, використовуючи потужність підключених до Інтернету окремих комп’ютерів у всьому світі, можна досягти швидкого прогресу. З. Яка ймовірність відкриття простого числа Мерсенна? A. Відповідно до проекту GIMPS,

Імовірність того, що будь-яке число-кандидат виявиться простим числом Мерсенна, становить 1 до 150 000.

З. Як насправді перевірити числа, щоб побачити, чи є вони простими числами Мерсенна?

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

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

З. Добре, чому люди шукають прості числа Мерсенна? Чим вони корисні?

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

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

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

З. Чому, окрім виклику, ви вирішили взяти участь?

В. Як це було на багатьох інших сайтах, ми зрозуміли, що наша велика (75 місць) PIC/Math Computer Lab використовує лише незначну частину доступної потужності ЦП. Замість того, щоб усі ці цикли пропали даремно, ми переглянули низку проектів розподілених обчислень і визначили , що 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» була частиною нашої серії комп’ютерів Classic Rock Band.

З. Що це стосується призових грошей?

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

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

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

З. Що я чую про плакат? Чи буде такий для числа Мерсенна UCLA?

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

Річард Крендалл з Perfectly Scientific нещодавно зв’язався зі мною, щоб повідомити, що постер Пройм Мерсенна UCLA тепер доступний для покупки. Він коштує 99 доларів, без рамки та доступний на веб-сайті Perfectly Scientific .

З. А як щодо іншого нещодавно відкритого простого числа Мерсенна?

В. Через два тижні після відкриття простого числа Мерсенна UCLA Ганс-Міхаель Ельвеніх у Німеччині відкрив ще одне число, що містить 10 мільйонів цифр плюс число Мерсенна. Маючи 11,2 мільйона цифр, це приблизно на 10% менше, ніж число Мерсенна UCLA.

Це не перший раз, коли прості числа Мерсенна виявляють не в порядку. У 1988 році Колквітт і Велш відкрили просте число Мерсенна, яке було меншим за попередні два, відкриті в 1983 і 1985 роках.

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

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