GIMPS (Great Internet Mersenne Prime Search) — широкомасштабний проєкт добровольчих обчислень з пошуку простих чисел Мерсенна.
GIMPS | |
Офіційний сайт(англ.) |
Цілі і методи проекту
Визначення того, чи є дане число простим, у загальному випадку не є тривіальною задачею. Тільки у 2002 році доведено, що вона має поліноміальну складність. Попри це, запропонований (і строго обґрунтований теоретично) детермінований алгоритм практично непридатний, зважаючи на його значну, хоча й поліноміальну, складність. Тому в криптографії з відкритим ключем, де застосовуються прості числа порядку , простоту як і раніше визначають за допомогою ефективних імовірнісних тестів, таких як тест Міллера — Рабіна. Важливо відзначити, що якщо для практики достатньо чисел, які є простими з імовірністю близькою до
, то теорія таких чисел не сприймає: якщо про число стверджується, що воно просте, це повинно бути строго доведено. Ця різниця підкреслюється в поділі алгоритмів на ймовірнісні й детерміновані.
Відповіддю на питання, яке найбільше просте число відоме людству, буде якесь із простих чисел Мерсенна. Числа Мерсенна мають вигляд . Зауважимо, що простота числа
тягне простоту
; в іншому випадку
для
і число
не буде простим.
Як видно з назви, метою проекту GIMPS є пошук нових простих чисел Мерсенна. На даний момент[] найбільшим відомим простим числом було , знайдене в проєкті GIMPS 7 грудня 2018 року. Воно записується 24 862 048 десятковими цифрами. Більш того, 15 попередніх рекордів також було встановлено учасниками GIMPS. Причина криється в наявності ефективного (детермінованого) критерію їх простоти, що носить ім'я тест Люка — Лемера. Для пошуку простих чисел Мерсенна сервер GIMPS роздає клієнтам прості «експоненти»
для перевірки числа
на простоту саме цим тестом.
На жовтень 2020 року було відомо 51 просте число Мерсенна, при цьому напевно відомі порядкові номери перших 47 з них. Порядкові номери чотирьох найбільших відомих простих чисел Мерсенна не було точно не встановлено (між ними можуть виявитися інші, ще не відкриті прості числа Мерсенна).
Практична значущість
Прості числа Мерсенна цікаві вже тим, що вони стабільно утримують рекорд як найбільші відомі прості числа.
Крім того, прості числа Мерсенна відіграють важливу роль у деяких проблемах теорії чисел. Наприклад, Евклід виявив, що якщо число просте, то число
досконале, тобто дорівнює сумі своїх дільників (приклади таких чисел: 6=1+2+3, 28=1+2+4+7+14, 496=1+2+4+8+16+31+62+124+248, а Ейлер згодом довів, що всі парні досконалі числа мають зазначений вигляд ((питання про існування непарного досконалого числа) відкрите досі).
Залишається відкритим питання про нескінченність кількості простих чисел Мерсенна і про їх асимптотику. Знайдені прості числа Мерсенна можуть служити відправною точкою для висунення й перевірки гіпотез про поведінку простих чисел Мерсенна.
На практиці прості числа Мерсенна застосовуються для побудови генераторів псевдовипадкових чисел з великими періодами (див. Вихор Мерсенна).
Грошові призи
GIMPS виграла грошовий приз 100 000 доларів США за відшукання простого числа з більше ніж 10 мільйонів десяткових цифр і має намір виграти аналогічні призи 150 000 і 250 000 доларів США, обіцяні Electronic Frontier Foundation за відшукання простих чисел відповідно з більш ніж зі 100 мільйонів і 1 мільярда десяткових цифр. Із суми цього призу планується зробити виплати всім «відкривачам» попередніх простих чисел Мерсенна, авторам програмного забезпечення і авторам нових, ефективніших алгоритмів пошуку (якщо такі алгоритми будуть знайдені).
Отримати GIMPS премію 100 000 доларів США дозволило знайдене в серпні 2008 року число , яке містить 12 978 189 десяткових цифр. Проте, щоб отримати премію 150 000 доларів США, доведеться перевіряти на простоту числа з більш ніж 100 млн десяткових цифр, кожне з яких за поточного рівня обчислювальної та алгоритмічної техніки зажадає більше трьох років.
Змагальний ефект
Щодня в проєкті GIMPS вивантажують результати своїх обчислень сотні учасників. Щодо кожного з них проєкт веде статистику, публікує й регулярно оновлює рейтинги продуктивності/результативності. Для посилення змагального ефекту в проєкті реалізовано можливість об'єднання учасників у команди. В цьому випадку накопичена статистика учасника йде в залік не тільки йому, але і його команді. Як і для окремих учасників, проєкт веде й оновлює рейтинги команд.
Команди зазвичай формуються за місцем розташування учасників (країна або місто), за належністю до певної організації (навчальний заклад або компанія) чи просто з бажання підтримати ту чи іншу інтернет-спільноту.
Всього в проєкті більше 1000 команд. Абсолютна більшість з них зовсім невеликі — з одного або декількох учасників, багато хто вже давно перестали бути активними. Найбільші команди включають десятки/сотні учасників, нерідко — власників значних обчислювальних потужностей: від декількох особистих комп'ютерів до великого парку комп'ютерної техніки «підшефної» компанії або університету.
Нерідко за кожну сходинку в командних рейтингах розігрується неабияка боротьба. Деякі команди цілеспрямовано координують дії своїх учасників, щоб здійснити прорив у запланованому вигляді обчислень і в підсумку якомога швидше піднятися на вищі позиції. В цілому ж командний ТОП-10 усіх рейтингів відносно стабільний, підносять сюрпризи переважно нові учасники, які несподівано вступають у гру за ту або іншу команду. Саме тому команди завжди раді прибульцям, а старожили допомагають їм з налаштуваннями обладнання та програм, консультують щодо вибору найцікавіших видів обчислень.
Ймовірність успіху
Евристичні оцінки показують, що існують ще чотири невідомих простих чисел Мерсенна, які складаються менш ніж зі 100 мільйонів десяткових цифр, а найближче з них може складатися приблизно з 26 мільйонів цифр. Детальну інформацію про їх можливий розподіл, а також про очікувані витрати на їх знаходження можна отримати на сторінці статистики.
Тестування апаратного забезпечення
Клієнтська програма GIMPS проводить інтенсивні обчислення, постійно стежачи за їх точністю. Тому багато хто розглядає її як хороший інструмент для тестування стабільності роботи апаратної частини комп'ютера. Пікові навантаження і жорсткий контроль дозволяють легко виявляти проблеми з пам'яттю, кешем, шиною даних, розгоном і перегріванням процесора тощо. Для полегшення процедури тестування клієнт GIMPS надає можливість роботи в режимі «stress testing», коли обчислення проводяться для відомих простих чисел Мерсенна і результати обчислень звіряються з очікуваними.
Підтримувані операційні системи
Клієнтська частина ПЗ проєкту GIMPS доступна для таких операційних систем:
- 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-бітова версій)
Примітки
- . November 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.] (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
GIMPS Great Internet Mersenne Prime Search shirokomasshtabnij proyekt dobrovolchih obchislen z poshuku prostih chisel Mersenna GIMPS Oficijnij sajt angl Cili i metodi proektuViznachennya togo chi ye dane chislo prostim u zagalnomu vipadku ne ye trivialnoyu zadacheyu Tilki u 2002 roci dovedeno sho vona maye polinomialnu skladnist Popri ce zaproponovanij i strogo obgruntovanij teoretichno determinovanij algoritm praktichno nepridatnij zvazhayuchi na jogo znachnu hocha j polinomialnu skladnist Tomu v kriptografiyi z vidkritim klyuchem de zastosovuyutsya prosti chisla poryadku 10 300 displaystyle 10 300 prostotu yak i ranishe viznachayut za dopomogoyu efektivnih imovirnisnih testiv takih yak test Millera Rabina Vazhlivo vidznachiti sho yaksho dlya praktiki dostatno chisel yaki ye prostimi z imovirnistyu blizkoyu do 1 displaystyle 1 to teoriya takih chisel ne sprijmaye yaksho pro chislo stverdzhuyetsya sho vono proste ce povinno buti strogo dovedeno Cya riznicya pidkreslyuyetsya v podili algoritmiv na jmovirnisni j determinovani Vidpoviddyu na pitannya yake najbilshe proste chislo vidome lyudstvu bude yakes iz prostih chisel Mersenna Chisla Mersenna mayut viglyad M p 2 p 1 displaystyle M p 2 p 1 Zauvazhimo sho prostota chisla 2 p 1 displaystyle 2 p 1 tyagne prostotu p displaystyle p v inshomu vipadku p x y displaystyle p xy dlya x y gt 1 displaystyle x y gt 1 i chislo 2 p 1 2 x y 1 2 x 1 2 y 1 displaystyle 2 p 1 2 xy 1 2 x 1 2 y 1 ne bude prostim Yak vidno z nazvi metoyu proektu GIMPS ye poshuk novih prostih chisel Mersenna Na danij moment koli najbilshim vidomim prostim chislom bulo M 82589933 2 82589933 1 displaystyle M 82589933 2 82589933 1 znajdene v proyekti GIMPS 7 grudnya 2018 roku Vono zapisuyetsya 24 862 048 desyatkovimi ciframi Bilsh togo 15 poperednih rekordiv takozh bulo vstanovleno uchasnikami GIMPS Prichina kriyetsya v nayavnosti efektivnogo determinovanogo kriteriyu yih prostoti sho nosit im ya test Lyuka Lemera Dlya poshuku prostih chisel Mersenna server GIMPS rozdaye kliyentam prosti eksponenti p displaystyle p dlya perevirki chisla M p displaystyle M p na prostotu same cim testom Na zhovten 2020 roku bulo vidomo 51 proste chislo Mersenna pri comu napevno vidomi poryadkovi nomeri pershih 47 z nih Poryadkovi nomeri chotiroh najbilshih vidomih prostih chisel Mersenna ne bulo tochno ne vstanovleno mizh nimi mozhut viyavitisya inshi she ne vidkriti prosti chisla Mersenna Praktichna znachushistProsti chisla Mersenna cikavi vzhe tim sho voni stabilno utrimuyut rekord yak najbilshi vidomi prosti chisla Krim togo prosti chisla Mersenna vidigrayut vazhlivu rol u deyakih problemah teoriyi chisel Napriklad Evklid viyaviv sho yaksho chislo M p 2 p 1 displaystyle M p 2 p 1 proste to chislo M p M p 1 2 2 p 1 2 p 1 displaystyle M p M p 1 2 2 p 1 2 p 1 doskonale tobto dorivnyuye sumi svoyih dilnikiv prikladi takih chisel 6 1 2 3 28 1 2 4 7 14 496 1 2 4 8 16 31 62 124 248 a Ejler zgodom doviv sho vsi parni doskonali chisla mayut zaznachenij viglyad pitannya pro isnuvannya neparnogo doskonalogo chisla vidkrite dosi Zalishayetsya vidkritim pitannya pro neskinchennist kilkosti prostih chisel Mersenna i pro yih asimptotiku Znajdeni prosti chisla Mersenna mozhut sluzhiti vidpravnoyu tochkoyu dlya visunennya j perevirki gipotez pro povedinku prostih chisel Mersenna Na praktici prosti chisla Mersenna zastosovuyutsya dlya pobudovi generatoriv psevdovipadkovih chisel z velikimi periodami div Vihor Mersenna Groshovi priziGIMPS vigrala groshovij priz 100 000 dolariv SShA za vidshukannya prostogo chisla z bilshe nizh 10 miljoniv desyatkovih cifr i maye namir vigrati analogichni prizi 150 000 i 250 000 dolariv SShA obicyani Electronic Frontier Foundation za vidshukannya prostih chisel vidpovidno z bilsh nizh zi 100 miljoniv i 1 milyarda desyatkovih cifr Iz sumi cogo prizu planuyetsya zrobiti viplati vsim vidkrivacham poperednih prostih chisel Mersenna avtoram programnogo zabezpechennya i avtoram novih efektivnishih algoritmiv poshuku yaksho taki algoritmi budut znajdeni Otrimati GIMPS premiyu 100 000 dolariv SShA dozvolilo znajdene v serpni 2008 roku chislo M 43112609 2 43112609 1 displaystyle M 43112609 2 43112609 1 yake mistit 12 978 189 desyatkovih cifr Prote shob otrimati premiyu 150 000 dolariv SShA dovedetsya pereviryati na prostotu chisla z bilsh nizh 100 mln desyatkovih cifr kozhne z yakih za potochnogo rivnya obchislyuvalnoyi ta algoritmichnoyi tehniki zazhadaye bilshe troh rokiv Zmagalnij efektShodnya v proyekti GIMPS vivantazhuyut rezultati svoyih obchislen sotni uchasnikiv Shodo kozhnogo z nih proyekt vede statistiku publikuye j regulyarno onovlyuye rejtingi produktivnosti rezultativnosti Dlya posilennya zmagalnogo efektu v proyekti realizovano mozhlivist ob yednannya uchasnikiv u komandi V comu vipadku nakopichena statistika uchasnika jde v zalik ne tilki jomu ale i jogo komandi Yak i dlya okremih uchasnikiv proyekt vede j onovlyuye rejtingi komand Komandi zazvichaj formuyutsya za miscem roztashuvannya uchasnikiv krayina abo misto za nalezhnistyu do pevnoyi organizaciyi navchalnij zaklad abo kompaniya chi prosto z bazhannya pidtrimati tu chi inshu internet spilnotu Vsogo v proyekti bilshe 1000 komand Absolyutna bilshist z nih zovsim neveliki z odnogo abo dekilkoh uchasnikiv bagato hto vzhe davno perestali buti aktivnimi Najbilshi komandi vklyuchayut desyatki sotni uchasnikiv neridko vlasnikiv znachnih obchislyuvalnih potuzhnostej vid dekilkoh osobistih komp yuteriv do velikogo parku komp yuternoyi tehniki pidshefnoyi kompaniyi abo universitetu Neridko za kozhnu shodinku v komandnih rejtingah rozigruyetsya neabiyaka borotba Deyaki komandi cilespryamovano koordinuyut diyi svoyih uchasnikiv shob zdijsniti proriv u zaplanovanomu viglyadi obchislen i v pidsumku yakomoga shvidshe pidnyatisya na vishi poziciyi V cilomu zh komandnij TOP 10 usih rejtingiv vidnosno stabilnij pidnosyat syurprizi perevazhno novi uchasniki yaki nespodivano vstupayut u gru za tu abo inshu komandu Same tomu komandi zavzhdi radi pribulcyam a starozhili dopomagayut yim z nalashtuvannyami obladnannya ta program konsultuyut shodo viboru najcikavishih vidiv obchislen Jmovirnist uspihuEvristichni ocinki pokazuyut sho isnuyut she chotiri nevidomih prostih chisel Mersenna yaki skladayutsya mensh nizh zi 100 miljoniv desyatkovih cifr a najblizhche z nih mozhe skladatisya priblizno z 26 miljoniv cifr Detalnu informaciyu pro yih mozhlivij rozpodil a takozh pro ochikuvani vitrati na yih znahodzhennya mozhna otrimati na storinci statistiki Testuvannya aparatnogo zabezpechennyaKliyentska programa GIMPS provodit intensivni obchislennya postijno stezhachi za yih tochnistyu Tomu bagato hto rozglyadaye yiyi yak horoshij instrument dlya testuvannya stabilnosti roboti aparatnoyi chastini komp yutera Pikovi navantazhennya i zhorstkij kontrol dozvolyayut legko viyavlyati problemi z pam yattyu keshem shinoyu danih rozgonom i peregrivannyam procesora tosho Dlya polegshennya proceduri testuvannya kliyent GIMPS nadaye mozhlivist roboti v rezhimi stress testing koli obchislennya provodyatsya dlya vidomih prostih chisel Mersenna i rezultati obchislen zviryayutsya z ochikuvanimi Pidtrimuvani operacijni sistemiKliyentska chastina PZ proyektu GIMPS dostupna dlya takih operacijnih sistem Microsoft Windows 7 Vista XP 2008 2003 2000 NT Me 98 95 Takozh ye versiya dlya 64 bitovih variantiv Windows 7 Vista XP 2008 Mac OS X GNU Linux 64 bitova i 32 bitova versij FreeBSD 64 bitova i 32 bitova versij Primitki November 22 2008 Arhiv originalu za 22 listopada 2008 angl GIMPS List of Known Mersenne Prime Numbers 15 bereznya 2016 u Wayback Machine angl Record 12 Million Digit Prime Number Nets 100 000 Prize 5 serpnya 2011 u Wayback Machine angl EFF Cooperative Computing Awards 9 listopada 2008 u Wayback Machine angl Where is the next Mersenne prime 9 bereznya 2021 u Wayback Machine angl PrimeNet Activity Summary 12 sichnya 2021 u Wayback Machine angl Download GIMPS client 18 zhovtnya 2013 u Wayback Machine angl PosilannyaOficijnij sajt angl Instrumenti i rozshirena statistika GIMPS 1 kvitnya 2022 u Wayback Machine angl Oficijnij forum GIMPS 13 sichnya 2021 u Wayback Machine angl Rejting uchasnikiv v proyekti GIMPS 13 sichnya 2021 u Wayback Machine angl Rejting komand u proyekti GIMPS 13 sichnya 2021 u Wayback Machine angl