PrimeGrid

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

PrimeGrid — проект добровільних розподілених обчислень на платформі BOINC і PRPNet, метою якого є пошук простих чисел різного виду. Проект стартував 12 червня 2005 року.

Основна мета проекту — нести задоволення пересічному користувачу від знаходження простих чисел. Другою метою PrimeGrid є надання відповідних навчальних матеріалів про прості числа.

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

Участь у проекті PrimeGrid можлива у два способи: через BOINC і через Project Staging Area (PSA)

Зміст

Історія проекту[ред. | ред. код]

2005 рік[ред. | ред. код]

Проект започатковано 12 червня 2005 року приблизно о 14:00 UTC. Message@Home (тепер PrimeGrid) відкрив реєстрацію для 50 перших користувачів. Проект стартував на домашньому лептопі Rytis Slatkevičius.

Message@Home було розроблено як тестовий проект для PerlBOINC у спробі реалізувати BOINC сервер мовою програграмування . Першочерговою метою проекту на PerlBOINC було отримати короткі завдання (WU) із стандартних постійним результатом. Першим проектом був Message7, в якому ми намагалися за допомогою прямого перебору відновити повідомлення, зашифроване за допомогою md5. У серпні 2005 до проекту було долучено додаток RSA 640 Factoring Challenge. Подібно до Message7 у цьому проекті ми намагалися прямим перебором віднайти дільник для 640 цифрового RSA ключа. Message7 було припинено. 1 вересня 2005 року після невеличкої наради було обрано нову назву для проекту, PrimeGrid було обрано з варіації PrimeGrid@Home, що була запропонована користувачем на ім'я Heffed. За це він отримав 999 очок. :)

У листопаді 2005 зусиллями іншого проекту було факторизовано RSA 640, отже PrimeGrid рушив на штурм RSA 768. Оскільки шанси на факторизацію залишалися нескінченно малими, подальший розвиток залишено для PerlBOINC.

2006 рік[ред. | ред. код]

У березні 2006 проект RSA 768 було перервано для запуску нового, PrimeGen. У цьому проекті ми намагалися побудувати базу послідовних простих чисел, що на деякий час навернуло PrimeGrid на стежину пошуку простих чисел. Вторинною метою залишалась допомога RSA Factoring Challenges. Однак, незабаром з'ясувалося, що ці зусилля теж мають нескінченно малі шанси на успіх. Тим не менш пошук проекту, гідного розподілених обчислень, було продовжено.

В червні 2006 розпочався діалог з ведучими проекту Riesel Sieve із пропозицією перенести їхній проект на рейки BOINC. Rytis надавав підтримку PerlBOINC і команда Riesel Sieve успішно започаткувала їхній відсів (sieve), так само як додаток LLR для пошуку простих чисел. У співпраці з Riesel Sieve PrimeGrid вдалось реалізувати додаток LLR в партнерстві з іншими проектом з пошуку простих чисел, Twin Prime Search. У листопаді 2006, підпроект TPS LLR було офіційно запущено в PrimeGrid.

2007 рік[ред. | ред. код]

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

Літо 2007 виявилось досить спекотним, адже саме тоді було запущено пошук простих Cullen та Woodall. Восени, завдяки партнерським відносинам з Prime Sierpinski Problem і проектом 321, ще більше пошуків простих було додано. Додатково було додано 2 відсіва: Prime Sierpinski Problem об'єднаний відсів, що включає підтримку відсіву за проблемою Seventeen or Bust; а також комбінований Cullen/Woodall відсів.

Восени 2007 PrimeGrid мігрував деякі системи з PerlBOINC до стандартного програмного забезпечення BOINC. Тим не менш, багато з сервісів до цього часу залишаються на базі PerlBOINC.

2008 рік[ред. | ред. код]

2009 рік[ред. | ред. код]

2010 рік[ред. | ред. код]

2011 рік[ред. | ред. код]

2012 рік[ред. | ред. код]

На початку січня 2012 програма GeneferCUDA була портована з клієнта PRPNet до BOINC. Почавши у статусі бета тесту, дуже швидко Genefer став офіційним проектом, відкритим для доєднання для будь-кого з відповідним залізячним начинням. Протягом лише першого місяця у проекті було віднайдено 2 нових простих числа форми General Fermat Number (GFN).

2013 рік[ред. | ред. код]

2014 рік[ред. | ред. код]

У травні 2014 року розпочато повторну перевірку в BOINC результатів підпроекту SR5, отриманих в PRPNet.

На початку червня 2014 року підпроект Extended Sierpinski Problem портовано з PRPNet до BOINC.

29 червня 2014 року розпочато підпроект ESP Sieve — проект «сіялка» для підпроекта ESP LLR.

2015 рік[ред. | ред. код]

Визначні дати[ред. | ред. код]

  • 12 червня 2005 року — народився Message@Home з підпроектом Message7, у якому було відкрито реєстрацію для перших 50 користувачів
  • серпень 2005 року — підпроект RSA 640 Factoring Challenge було додано, а Message7 припинено
  • 1 вересня 2005 року — Message@Home змінює назву на PrimeGrid
  • листопад 2005 року — підпроект RSA 768 Factoring Challenge додано, а RSA 640 Factoring Challenge перервано
  • березнь 2006 року — підпроект primegen було додано, RSA 768 Factoring Challenge припинено
  • 26 листопада 2006 року — встановлено співпрацю з Twin Prime Search. Підпроект TPS LLR додано
  • 14 травня 2007 року — PrimeGrid досяг найвищого рангу за кількістю простих у the Top 5000 на сторніках The Prime Pages (разом з TPS)
  • липень 2007 року — додано підпроект Woodall LLR
  • серпень 2007 року — додано підпроект Cullen LLR
  • 15 вересня 2007 року — розпочато об'єднаний Cullen/Woodall Sieve
  • 13 жовтня 2007 року — додано підпроект PSP Sieve
  • 2 листопада 2007 року — PrimeGrid позбувається звання проекту з найбільшою кількістю простих чисел
  • 18 листопада 2007 року — встановлено співпрацю з 321search. Додано підпроект 321 LLR
  • 11 грудня 2007 року — додано підпроект PSP LLR
  • 29 лютого 2008 року — встановлено співпрацю з Proth Search
  • 15 березня 2008 року — розпочато серію челенджів. Встановлено рекорд одного дня — понад 820К очок
  • 13 квітня 2008 року — Project Staging Area додано задля допомоги у адаптації нових застосунків для BOINC
  • 10 березня 2008 року — підпроект PrimeGen завершено
  • 20 липня 2008 року — рекорд одного дня побито з результатом понад 3.4М очок протягом Lunar Landing Challenge (попередній рекорд 820К)
  • 28 серпня 2008 року — чат Meebo додано до форуму
  • грудень 2008 року — рекорд одного дня побито з результатом понад 5.2М очок протягом Winter Solstice Challenge (попередній рекорд 3.4М)
  • 26 грудня 2008 року — підпроект AP26 запущено
  • 13 лютого 2009 року — PrimeGrid товаришує з 12121 Search у пошуку простих форм 121·2n−1 та 27·2n−1. PrimeGrid додає форму +1 і розпочинає пошук усіх чотирьох форм у підпроекті 27121 Search.
  • 1 травня 2009 року — рекорд одного дня побито з результатом понад 7.7М очок протягом Showers to Flowers Challenge (попередній рекорд 5.2М)
  • 12 травня 2009 року — розпочато Factorial Prime Search
  • 3 серпня 2009 року — в PrimeGrid введено систему бейджів
  • 16 серпня 2009 року — розпочато Sophie Germain Prime Search
  • 27 серпня 2009 року — PrimeGrid повертає собі звання проекту з найбільшою кількістю простих у Top 5000 на сторінках The Prime Pages
  • 16 вересня 2009 року — PrimeGrid доєднує до підпроектів Seventeen or Bust задля розв'язання проблеми Серпинського
  • 20 жовтня 2009 року — випущено ppsieve для PPSE sieve, що у 6 разів швидший за попередній
  • 5 листопада 2009 року — розпочато Generalized Fermat Prime Search
  • 8 листопада 2009 року — з'явилась надія на появу застосунку для GPU в PrimeGrid. Розпочато розробку та тестування.
  • 14 листопада 2009 року — рекорд одного дня побито з результатом понад 9.5М протягом Giving Thanks Challenge (попередній рекорд 7.7М)
  • грудень 2009 року — додано підтримку CUDA для AP26
  • 14 грудня 2009 року — PrimeGrid позбувається звання проекту з найбільшою кількістю простих чисел у Top 5000 на сторінках The Prime Pages
  • 20 грудня 2009 року — рекорд одного дня побито з результатом понад 15.9М протягом Winter Solstice Challenge (попередній рекорд 9.5М)
  • 1 лютого 2010 року — офіційно розпочинається співпраця з Seventeen or Bust заради розв'язання проблеми Серпінського
  • 7 березня 2010 року — відновлено The Riesel Problem з TRP (Sieve)
  • 9 березня 2010 року — розпочато тестування CUDA в Proth Prime Sieve
  • 19 березня 2010 року — розпочато extended Sierpinski problem
  • 21 березня 2010 року — розпочато The Riesel Problem (LLR)
  • 18 червня 2010 року — рекорд одного дня побито з результатом понад 19.6М протягом Summer Solstice Challenge (попередній рекорд 15.9М)
  • 4 грудня 2013 року — знайдено перше МЕГА просте в підпроекті Sierpinski/Riesel Base 5 Problem
  • 7 червня 2014 року — підпроект Extended Sierpinski Problem портовано з PRPNet до BOINC.
  • 29 червня 2014 року — розпочато підпроект ESP Sieve — проект «сіялка» для підпроекта ESP LLR.

Підпроекти (BOINC)[ред. | ред. код]

Завершені / призупинені підпроекти[ред. | ред. код]

Застосунки[ред. | ред. код]

Застосунок app_name Windows Linux MacOS NVIDIA ATI/AMD
32-bit 64-bit 32-bit 64-bit 32-bit 64-bit CUDA OpenCL.jpg OpenCL.jpg
321 Prime Search (LLR) llr321 Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
AP27 Search ap26 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif Yes.gif Yes.gif Yes.gif Yes.gif
Cullen Prime Search (LLR) llrCUL Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Extended Sierpinski Problem (LLR) llrESP Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Generalized Cullen/Woodall Prime Search (LLR) llrGCW Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Prime Sierpinski Problem (LLR) llrPSP Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Proth Prime Search (LLR) llrPPS Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Proth Prime Search Extended (LLR) llrPPSE Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Proth Mega Prime Search (LLR) llrMEGA Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Seventeen or Bust (LLR) llrSOB Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Sierpinski / Riesel Base 5 Problem (LLR) llrSR5 Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Sophie Germain Prime Search (LLR) llrTPS Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
The Riesel Problem (LLR) llrTRP Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Woodall Prime Search (LLR) llrWOO Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Generalized Cullen/Woodall Prime Search (Sieve) gcw_sieve Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif 20 x 20 pixel square.gif
Proth Prime Search (Sieve) pps_sr2sieve Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=15 (GFN-15) genefer15 Yes.gif Yes.gif Yes.gif Yes.gif 20 x 20 pixel square.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=16 (GFN-16) genefer16 Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=17 Low (GFN-17-Low) genefer17low Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=17 Mega (GFN-17-Mega) genefer17mega Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=18 (GFN-18) genefer18 Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=19 (GFN-19) genefer19 Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=20 (GFN-20) genefer20 Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=21 (GFN-21) genefer Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search n=22 (GFN-22) genefer_wr Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif

Переваги застосунків[ред. | ред. код]

  • виконання завдань Sieve на GPU дає перевагу над CPU у 10-100 разів (в залежності від моделі GPU і CPU)
  • виконання завдань Sieve на GPU з CUDA (NVIDIA) має перевагу над аналогічним за рівнем GPU з OpenCL (AMD)
  • виконання завдань Genefer / Genefer (World Record) на GPU (NVIDIA) з використанням CUDA має перевагу над OpenCL для відеокарт родини Fermi та старших
  • виконання завдань Genefer / Genefer (World Record) на GPU (NVIDIA) з використанням OpenCL має перевагу над CUDA для відеокарт родини Kepler та молодших
  • виконання завдань LLR та Genefer з оптимізацією під інструкції AVX сучасних Intel процесорів (Sandy/Ivy Bridge, Haswell) дає перевагу над SSE3 у декілька разів
  • виконання завдань Sieve на 64-бітному CPU дає перевагу над 32-бітних CPU клієнтом у ~1.7 раза
  • виконання завдань LLR на 64-бітному CPU має невеличку перевагу над 32-бітним CPU

Підпроекти LLR[ред. | ред. код]

321 Prime Search[ред. | ред. код]

Підпроект 321 Prime Search — це продовження проекту 321 Search, що було розпочато Paul Underwood, який шукав прості виду 3·2n−1. PrimeGrid додав пошук за формою +1 і продовжує пошук аж до n=25M.

Експоненти n, для яких відповідні числа форми 3·2n+1 прості, утворюють послідовність:

1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912, 20909, 34350, 42294, 42665, 44685, 48150, 54792, 55182, 59973, 80190, 157169, 213321, 303093, 362765, 382449, 709968, 801978, 916773, 1832496, 2145353, 2291610, 2478785, 5082306, 7033641, 10829346

Експоненти n, для яких відповідні числа форми 3·2n−1 прості, утворюють послідовність:

0, 1, 2, 3, 4, 6, 7, 11, 18, 34, 38, 43, 55, 64, 76, 94, 103, 143, 206, 216, 306, 324, 391, 458, 470, 827, 1274, 3276, 4204, 5134, 7559, 12676, 14898, 18123, 18819, 25690, 26459, 41628, 51387, 71783, 80330, 85687, 88171, 97063, 123630, 155930, 164987, 234760, 414840, 584995, 702038, 727699, 992700, 1201046, 1232255, 2312734, 3136255, 4235414, 6090515, 11484018, 11731850, 11895718

Про 321 Search[ред. | ред. код]

Проект 321 Search було розпочато у лютому 2003 із листа від Paul Underwood, що шукав допомогу зацікавлених у пошуку простих виду 3·2n−1. Початкова мета була перевірити результати роботи вже проведені проектом Proth Search і розширити перелік простих до експоненти в 1 мільйон (n=1M). Ця мета була швидко досягнута, тому вони розвинули мету з пошуку мега великих простих, для яких вони провели відсів аж до n=5M.

Результати підпроекту[ред. | ред. код]

Прості числа виду 3·2n±1, що було знайдено у PrimeGrid (станом на 23 червня 2015 року):

Просте число Цифр Дата Автор
3·24235414−1 1 274 988 23.03.2008 Dylan Bennett
3·22291610+1 689 844 11.08.2008 Thomas Wolfram
3·25082306+1 1 529 928 03.04.2009 Andy Brady
3·26090515−1 1 833 429 24.04.2010 David Mumper
3·27033641+1 2 117 338 21.02.2011 Michael Herder
3·210829346+1 3 259 959 14.01.2014 Sai Yik Tang
3·211484018−1 3 457 035 22.11.2014 Serhiy Gushchak
3·211731850−1 3 531 640 13.03.2015 Karsten Klopffleisch
3·211895718−1 3 580 969 23.06.2015 Michael Schulz

AP27 Search[ред. | ред. код]

Про AP26 (Arithmetic Progression of 26 primes)[ред. | ред. код]

Арифметична прогресія — послідовність чисел, різниця між послідовними членами якої є сталим числом. Наприклад послідовність 3, 5, 7, 9, 11, 13, 15, … є арифметичною прогресією з фіксованою різнецею, що дорівнює 2.

Таким чином, арифметична прогресія простих чисел — це послідовність простих чисел, різниця між послідовними членами якої є сталим числом. Наприклад, послідовність 3, 7, 11 є арифметичною прогресією 3 простих із фіксованою різницею 4.

Для арифметичної прогресії (AP) простих, AP-k означає k простих форми p+d*n для деяких p і d, а n приймає значення від 0 до k−1. Арифметичну прогресію, що наведено вище, можна записати як AP-3 виду 3+4·n для n=0,1,2.

n=0; 3+4·0 = 3+0 = 3

n=1; 3+4·1 = 3+4 = 7

n=2; 3+4·2 = 3+8 = 11

Іншим прикладом арифметичної прогресії простих є AP-10 виду 199+210·n для n=0..9. Вона продукує наступну послідовність простих: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089.

AP-k також інколи записують як PAP-k (Primes in Arithmetic Progression).

Підпроект AP26 займався пошуком найдовшої (але не найбільшої) арифметичної прогресії простих чисел. На той час найдовшою відомою AP була AP-25, що була віднайдена 17 травня 2008 року і має вигляд 6171054912832631+366384·23#·n (8132758706802551)

12 квітня 2010 року у підпроекті AP26 було знайдено першу відому послідовність AP-26:

43142746595714191+23681770·23#·n для n=0..25

, де 23#=2·3·5·7·11·13·17·19·23=223092870

У травні 2010 року підпроект AP26 було завершено.

20 вересня 2016 року підпроект пошуку арифметичної прогресії простих чисел було відновлено під назвою AP27 (arithmetic progression of 27 primes)

Результати підпроекту[ред. | ред. код]

Арифметичні прогресії простих, що було знайдено у PrimeGrid (станом на 5 вересня 2017 року):

AP Тип Дата Автор
43142746595714191+23681770*23#*n для n=0..25 AP26 12.04.2010 Benoãt Perichon
149836681069944461+7725290*23#*n для n=0..25 AP26 03.11.2016 Takeshi Nakamura
142099325379199423+16549135*23#*n для n=0..25 AP26 11.12.2016 Koichi Soraku
48277590120607451+37835074*23#*n для n=0..25 AP26 05.09.2017 Bruce E. Slade

Cullen Prime Search[ред. | ред. код]

Cullen Prime Search — це підпроект з пошуку простих чисел Каллена. В теорії чисел число Каллена — натуральне число виду Cn = n·2n+1

Експоненти n, для яких відповідні числа Каллена прості, утворюють послідовність:

1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881

В 1976 році Христофер Хулей (англ. Christopher Hooley) показав, що майже всі числа Каллена складені. Доведення Христофера Хулей було перероблено математиком Хірмі Суяма, щоб показати, що воно вірне для будь-якої послідовності n·2n+a+b, де a і b — цілі числа, а також частково для чисел Вудала.

Є гіпотеза, що простих чисел Каллена є нескінчено багато.

Результати підпроекту[ред. | ред. код]

Прості числа Каллена, що було знайдено у PrimeGrid (станом на 25 липня 2009 року):

Просте число Цифр Дата Автор
6328548·26328548+1 1 905 090 20.04.2009 Dennis R. Gesker
6679881·26679881+1 2 010 852 25.07.2009 Anonymous

Extended Sierpinski Problem[ред. | ред. код]

В 1962 році Джон Селфридж (John Selfridge) висунув гіпотезу, що число Серпінського k = 78557 є найменшим з таких чисел. Проблема Серпінського намагається підтвердити цю гіпотезу. В 1976 році Натан Мендельсон (Nathan Mendelsohn) висунув гіпотезу, що другим числом Серпінського є просте число k = 271129. Prime Sierpinski Problem намагається підтвердити гіпотезу, що це число не найменшим простим числом Серпінського.

Якщо обидві ці проблеми будуть розв'язані і буде встановлено, що k = 78557 є найменшим числом Серпінського, і k = 271129 — найменшим простим числом Серпінського, однак це не доводить, що k = 271129 є другим числом Серпінського. Оскільки Prime Sierpinski Problem перевіряє всі прості k у проміжку 78557 < k < 271129, все що достатньо зробити, це перевірити всі складені з проміжку 78557 < k < 271129. Таким чином було розпочато проект Extended Sierpinski Problem.

Станом на квітень 2018 року пошук залишається для 10-ти k, до яких досі не знайдено простих:

91549, 99739, 131179, 163187, 200749, 202705, 209611, 227723, 229673, 238411

Результати підпроекту[ред. | ред. код]

Прості, що було знайдено у PrimeGrid (станом на 3 квітня 2018 року):

Generalized Cullen/Woodall Prime Search[ред. | ред. код]

Узагальнене число Каллена визначається як число виду n·bn+1, де n+2>b. Якщо просте число можна записати таким чином, його називають узагальненим простим числом Каллена.

Узагальнене число Вудала визначається як число виду n·bn−1, де n+2>b. Якщо просте число можна записати таким чином, його називають узагальненим простим числом Вудала.

Метою GCW Prime Search є пошук узагальнених простих Каллена і Вудала за основами, для яких досі не віднайшли жодного простого. З самого початку GCW13 Search пощастило знайти найбільше відоме узагальнене просте Вудала: 563528·13563528−1.

Наступні бази було обрано для подальшого пошуку узагальнених простих:

  • Вудал: b = 43, 104 і 121
  • Каллен: b = 13, 25, 29, 41, 47, 49, 53, 55, 68, 69, 73, 79, 101, 109, 113, 116 і 121

Основа 149 — наступна основа без відомих простих для обох і GC, і GW.

Початкова глибина відсіву для цих основ становила 1.5T. Lennart Vogel перевірив на простоту всі основи аж до n=100K (лише GW121 до 50K). Як побачимо нижче, це все була подвійна перевірка попередніх зусиль.

Результати проекту[ред. | ред. код]

b Узагальнене Просте число Цифр Дата Автор
13 Woodall 563528·13563528−1 627 745 07.12.2009 Lennart Vogel
43 Woodall 404882·43404882−1 661 368 24.02.2011 Ricky L. Hubbard
104 Woodall 129840·104129840−1 261 897 26.05.2010 Sideshow_Larry
121 Woodall 94112·12194112−1 196 021 19.05.2010 unconnected
13 Cullen
25 Cullen
29 Cullen
41 Cullen 1806676·411806676+1 2 913 785 11.03.2018 Hiroyuki Okazaki
47 Cullen
49 Cullen
53 Cullen 1341174·531341174+1 2 312 561 25.05.2010 Hiroyuki Okazaki
55 Cullen
68 Cullen 129897·68129897+1 238 043 25.05.2010 [SG-SPEG]Puzzle-Peter
69 Cullen
73 Cullen
79 Cullen 682156·79682156+1 1 294 484 08.10.2016 Franz-Xaver Harvanek
101 Cullen
109 Cullen
113 Cullen 427194·113427194+1 877 069 29.01.2012 Ricky L. Hubbard
116 Cullen 1323365·1161323365+1 2 732 038 18.01.2018 Scott Brown
121 Cullen

Message7[ред. | ред. код]

Першим проектом Message@Home (тепер PrimeGrid) був Message7, в якому за допомогою прямого перебору намагалися відновити повідомлення, зашифроване за допомогою md5. У серпні 2005 року Message7 було припинено.

PrimeGen[ред. | ред. код]

У березні 2006 було запущено проект PrimeGen, метою якого було побудувати базу послідовних простих чисел. Однак, незабаром з'ясувалося, що ці зусилля мають нескінченно малі шанси на успіх, отже підпроект було зупинено.

Prime Sierpinski Problem[ред. | ред. код]

Числом Серпінського називається таке непарне натуральне число k, що для довільного натурального n число k·2n+1 не є простим.

Послідовність відомих чисел Серпінського починається так:

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, …

Те, що число 78557 є числом Серпінського, було доведено в 1962 році Джоном Селфріджем (англ. John Selfridge), який виявив, що кожне число виду 78557·2n+1 ділиться принаймні на одне число із множини {3, 5, 7, 13, 19, 37, 73}. Аналогічно, 271129 також є числом Серпінського: кожне число число виду 271129·2n+1 ділиться принаймні на одне число із множини {3, 5, 7, 13, 17, 241}.

Початково проблему Серпінського можна сформулювати так: «Яким є найменше число Серпінського?», а проблему простого Серпінського: «Яким є найменше просте число Серпінського

Більшість знавців теорії чисел вірять, що 78557 є найменшим числом Серпінського. Щоб це довести, достатньо показати, що для кожного k, такого, що 0 < k < 78557, існує таке n, що число k·2n+1 є простим.

Найменше доведене просте число Серпінського — 271129. Щоб довести, що 271129 є найменшим простим числом Серпінського, необхідно показати, що кожне просте k, таке, що 0 < k < 271129, не є числом Серпінського.

Seventeen or Bust працює над проблемою Серпінського, а Prime Sierpinski Project — над проблемою простого Серпінського.

Для наступних k до цього часу залишаються невідомі прості для кожного з проектів:

Seventeen or Bust Prime Sierpinski Project
21181
22699 22699[1]
24737
55459
67607 67607[1]
79309
79817
152267
156511
222113
225931
237019

Результати підпроекту[ред. | ред. код]

Прості, що було знайдено у PrimeGrid (станом на 17 вересня 2017 року):

Просте число Цифр Дата Автор
168451·219375200+1 5 832 522 17.09.2017 Ben Maloney

Proth Prime Search[ред. | ред. код]

У підпроекті Proth Prime Search відшукуються прості числа виду k·2n+1, за умови 2n > k, що часто називають простими числами Прота. Цей проект також дає можливість віднайти дільники для «класичних» чисел Ферма, узагальнених чисел Ферма чи розширених узагальнених чисел Ферма. Як тільки у PrimeGrid знаходиться просте Прота, воно одразу проходить додаткову перевірку на сервері PrimeGrid, чи є воно дільником однієї з форм чисел Ферма.

Proth Prime Search проводиться у співпраці з проектом Proth Search. Початковою метою проекту PrimeGrid було перевірити всю попередню роботу проекту Proth Search аж до n=500K для непарних k<1200 і заповнити будь-які можливі прогалини. PrimeGrid перевірив все аж до n=200000 і знайшов деякі прості, що було випущено минулим пошуком. Незважаючи на те, що прості вже надто малі, щоб потрапити до бази Top 5000, цей пошук був важливим, адже він міг призвести до відшукання нових дільників для «класичних» чисел Ферма, узагальнених чисел Ферма або розширених узагальнених чисел Ферма.

Про Proth Search[ред. | ред. код]

Проект Proth Search було започатковано 1998 року за участю Ray Ballinger та Wilfrid Keller, які організували розподілені обчислення для знаходження простих Прота (прості виду k·2n+1) для k < 300. Ray був зацікавлений у пошуку простих, а Wilfrid — у пошуку дільників для чисел Ферма. Пізніше проект розширив межі свого пошуку до k < 1200. Mark Rodenkirch (aka rogue) допомагав Ray в утримані веб-сайту останні декілька літ.

На початку 2008 року PrimeGrid та Proth Search розпочали співпрацю з надання програмного забезпечення для об'єднання зусиль розподілених обчислень.

Від того часу PrimeGrid веде пошук простих Прота у декількох різних підпроектах, як у вигляді підпроектів BOINC, так і в PRPNet.

Станом на 18 липня 2014 року в PrimeGrid існує 3 діапазони пошуку простих Прота, які оформлені як 3 різних підпроекта BOINC:

  • PPSE: k·2n+1 для 1200<k<10000
  • PPS: k·2n+1 для k<1200
  • PPS-Mega: k·2n+1 для 100<k<300 і 3.322M<=n<3.6M

Мега Просте визначається як просте з щонайменше одним мільйоном десяткових знаків (титанічні прості містять щонайменше 1000 знаків, гігантське просте — 10000 знаків). Станом на 3 березня 2015 року відомо про 125 Мега Простих[2].

Підпроект PPS-Mega фокусується на пошуку Мега Простих. Час перевірки на одному ядрі швидкого комп'ютера займає близько 1 години (Intel Haswell CPU). Пошук простих форми k·2n+1 було розпочато з n=3322000 для k<100, виключаючи k=3, 5, 7, 27. 18 липня 2014 року підпроект було перенесено з PRPNet в BOINC із зміною діапазонів пошуку з k<100 на 100<k<300.

PrimeGrid має намір продовжити пошук простих чисел Прота невизначено довго.

Результати підпроекту[ред. | ред. код]

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

У табличці, що наведена нижче, представлені прості Прота, що було знайдено у PrimeGrid, що є дільниками чисел Ферма (станом на 14 лютого 2015 року):

Просте число Цифр Ділить Дата Автор
651·2476632+1 143 484 F(476624) 27.12.2008 Eric Ueda
519·2567235+1 170 758 F(567233) 06.03.2009 Senji Yamashita
659·2617815+1 185 984 F(617813) 31.03.2009 Eric Embling
7333·2138560+1 41 715 F(138557) 12.05.2011 Dirk D'huyvetters
9·22543551+1 765 687 F(2543548) 22.06.2011 Scott Brown
3771·2221676+1 66 736 F(221670) 01.07.2011 Mark Doom
4479·2226618+1 68 223 F(226614) 08.07.2011 Peter Doggart
25·22141884+1 644 773 F(2141872) 09.09.2011 Grzegorz Granowski
329·21246017+1 375 092 F(1246013) 04.01.2012 Bruce Dodson
131·21494099+1 449 771 F(1494096) 07.02.2012 Rob Derrera
7905·2352281+1 106 052 F(352279) 02.05.2012 James Boerner
1705·2906110+1 272 770 F(906108) 13.06.2012 Robert Boniecki
183·21747660+1 526 101 F(1747656) 10.03.2013 Bart van Rooijen
57·22747499+1 827 082 F(2747497) 13.05.2013 Marshall Bishop
2145·21099064+1 330 855 F(1099061) 18.06.2013 Sai Yik Tang
193·23329782+1 1 002 367 F(3329780) 25.07.2014 Raymond Ottusch
267·22662090+1 801 372 F(2662088) 13.02.2015 Jay Parangalan

Станом на 18 липня 2014 року підпроектом MEGA у PRPNet було знайдено 7 Мега Простих:

Просте число Цифр Дата Автор
81·23352924+1 1 009 333 17.01.2012 Michał Gasewicz
87·23496188+1 1 052 460 28.03.2014 Stefan Larsson
51·23490971+1 1 050 889 28.03.2014 Gary Craig
93·23544744+1 1 067 077 06.05.2014 Michał Gasewicz
33·23570132+1 1 074 719 10.06.2014 Fabrice Le Foulher
35·23570777+1 1 074 913 10.06.2014 Robert Lacroix
35·23587843+1 1 080 050 04.07.2014 Peter Tibbott

Станом на 28 грудня 2017 року підпроектом Proth Mega Prime Search були знайдені наступні Мега Прості:

З 2018 року у проекті відбулась зміна політики анонсування відкриттів визначних простих чисел. Лише числа, що потрапляють у топ 100 простих, анонсуються.

RSA 640[ред. | ред. код]

У серпні 2005 до проекту було долучено додаток RSA 640 Factoring Challenge. Подібно до Message7 у цьому проекті відбувались намагання прямим перебором віднайти дільник для 640 цифрового RSA ключа.

У листопаді 2005 зусилями іншого проекту було факторизовано RSA 640, отже PrimeGrid рушив на штурм RSA 768 Factoring Challenge.

RSA 768[ред. | ред. код]

Оскільки шанси на факторизацію RSA 768 виявились нескінченно малими, подальший розвиток залишено для PerlBOINC. У березні 2006 проект RSA 768 було перервано для запуску нового, PrimeGen.

Seventeen or Bust[ред. | ред. код]

Числом Серпінського називається таке непарне натуральне число k, що для довільного натурального n число k·2n+1 не є простим.

Послідовність відомих чисел Серпінського починається:

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, …

Те, що число 78557 є числом Серпінського, було доведено в 1962 році Джоном Селфріджем (англ. John Selfridge), який виявив, що кожне число виду 78557·2n+1 ділиться принаймні на одне число із множини {3, 5, 7, 13, 19, 37, 73}.

Проблему Серпінського можна сформулювати так: «Яким є найменше число Серпінського

Більшість знавців теорії чисел вірять, що 78557 є найменшим числом Серпінського. Щоб це довести, достатньо показати, що для кожного непарного k, такого, що 0<k<78557, існує таке n, що число k·2n+1 є простим.

Підпроект Seventeen or Bust працює над проблемою Серпінського. Проект так називається, бо до його початку не біло відомо, чи існують прості для 17 чисел k. Наразі залишається знайти прості числа для 5 k:

k Просте число Цифр Дата Автор
1 4847 4847·23321063+1 999 744 15.10.2005 Richard Hassler
2 5359 5359·25054502+1 1 521 561 06.12.2003 Randy Sundquist
3 10223 10223·231172165+1 9 383 761 31.10.2016 Szabolcs Peter
4 19249 19249·213018586+1 3 918 990 26.03.2007 Константин Агафонов
5 21181
6 22699
7 24737
8 27653 27653·29167433+1 2 759 677 08.06.2005 Derek Gordon
9 28433 28433·27830457+1 2 357 207 30.12.2004 анонімний учасник
10 33661 33661·27031232+1 2 116 617 13.10.2007 Sturle Sunde
11 44131 44131·2995972+1 299 823 05.12.2002 deviced (нік)
12 46157 46157·2698207+1 210 186 27.11.2002 Stephen Gibson
13 54767 54767·21337287+1 402 569 22.12.2002 Peter Coels
14 55459
15 65567 65567·21013803+1 305 190 03.12.2002 James Burt
16 67607
17 69109 69109·21157446+1 348 431 07.12.2002 Sean DiMichele

Результати підпроекту[ред. | ред. код]

Прості, що було знайдено у PrimeGrid (станом на 31 жовтня 2016 року):

Просте число Цифр Дата Автор
10223·231172165+1 9 383 761 31.10.2016 Szabolcs Peter

Sierpinski/Riesel Base 5 Problem[ред. | ред. код]

Проблема Серпінського/Різеля за основою 5[ред. | ред. код]

Цей підпроект є поширенням проблеми Серпинського/Різеля (SoB/TRP). Він намагається розв'язати проблему Серпінського/Різеля за основою 5, віднайти найменше число Серпинського/Різеля. Таким чином відшукуються прості виду k·5n±1 з парними значеннями k.

Числа Серпінського за основою 5[ред. | ред. код]

Гіпотеза полягає у тому, що найменшим парним числом Серпінського за основою 5 є k = 159986. Щоб довести це, достатньо показати, що існує просте число виду k·5n+1 для кожного парного k < 159986. Наразі це доведено для всіх парних k, окрім наступних 32 значень (станом на 20 червня 2018 року): k = 6436, 7528, 10918, 26798, 29914, 31712, 36412, 41738, 44348, 44738, 45748, 51208, 58642, 60394, 62698, 64258, 67612, 67748, 71492, 74632, 76724, 83936, 84284, 90056, 92906, 93484, 105464, 118568, 126134, 138514, 139196, 152588

Числа Різеля за основою 5[ред. | ред. код]

Гіпотеза полягає у тому, що найменшим парним числом Різеля за основою 5 є k=346802. Щоб довести це, достатньо показати, що існує просте число виду k·5n−1 для кожного парного k < 346802. Наразі це доведено для всіх парних k, окрім наступних 72 значень (станом на 19 червня 2018 року): k = 3622, 4906, 23906, 26222, 35248, 35816, 52922, 63838, 64598, 66916, 68132, 71146, 76354, 81134, 88444, 92936, 102818, 102952, 109238, 109838, 109862, 127174, 131848, 134266, 136804, 143632, 145462, 145484, 146264, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 177742, 182398, 187916, 189766, 190334, 194368, 195872, 201778, 204394, 206894, 207494, 213988, 231674, 238694, 239062, 239342, 246238, 248546, 259072, 265702, 267298, 271162, 273662, 285598, 285728, 298442, 304004, 313126, 318278, 322498, 325922, 335414, 338866

Історія[ред. | ред. код]

17 вересня 2004 року на сторінках yahoo групи primeform Роберт Сміт (Robert Smith) вперше презентував ідею пошуку найменших чисел Серпінського/Різеля за основою 5. Використовуючи покриваючу множину {3, 7, 13, 31, 601}, він висунув гіпотезу, що k=346802 є найменшим числом Різеля за основою 5. Невдовзі Гвідо Сметрійнз (Guido Smetrijns) запропонував k=159986 як найменше число Серпінського за основою 5.

Після виконання великої частини самостійних обрахунків, Роберт оголосив про це на форумі mersenneforum.org 28 вересня 2004 року, і таким чином, зусилля з розподіленого обчислення було розпочато. Іншими важливими гравцями у справі розробки, управління і розвитку проекту є Lars Dausch, Geoff Reynolds, Anand S Nair, і Thomas Masser.

Результати підпроекту[ред. | ред. код]

Прості, що було знайдено у PrimeGrid (станом на 20 червня 2018 року):

Sophie Germain Prime Search[ред. | ред. код]

Просте число p називається простим Софі Жермен, якщо число 2·p+1 також є простим. Наприклад просте число 5 є простим Софі Жермен, адже число 2·5+1 = 11 також є простим. Ці числа названі числами Софі Жермен на честь екстраординарної французської математички, що зробила важливий внесок в галузі диференційної геометрії і теорії чисел та у вивчені Останньої Теореми Ферма.

В підпроекті Sophie Germain Prime Search спочатку перевіряється на простоту число виду k·2n−1. Якщо воно є простим, тоді перевіряються числа k·2n+1, k·2n-1−1 та k·2n+1−1. Якщо виявиться, що простим є також k·2n-1−1 або k·2n+1−1 — це означає, що знайдено просте Софі Жермен. Якщо простим виявиться k·2n+1, тоді можна сказати, що знайдено прості числа-близнюки. Можливість знайти просте Софі Жермен або прості-близнюки робить пошук саме у цьому підпроекті привабливішим.

Результати підпроекту[ред. | ред. код]

Прості Софі Жермен, що було знайдено у PrimeGrid (станом на 29 лютого 2016 року):

Просте число SGS 2p+1 Цифр Дата Автор
18543637900515·2666667−1 18543637900515·2666668−1 200 701 09.04.2012 Philipp Bliedung
2618163402417·21290000−1 2618163402417·21290001−1 388 342 29.02.2016 Scott Brown

Прості-близнюки, що було знайдено у PrimeGrid (станом на 14 вересня 2016 року):

Просте число Цифр Дата Автор
3756801695685·2666669±1 200 700 25.12.2011 Timothy D. Winslow
18543637900515·21290000±1 388 342 14.09.2016 Tom Greer

The Riesel Problem[ред. | ред. код]

Ганс Івар Різель (англ. Hans Ivar Riesel, нар. 1929 у Стокгольмі) — шведський математик, у 1956 показав, що існує нескінчено велика кількість додатніх непарних чисел k таких, що k·2n−1 є числом складеним для будь-якого цілого n ≥ 1. Такі числа тепер отримали назву чисел Різеля. Він також показав, що число k = 509203 є одним з таких. А також 509203 плюс будь-яке натуральне число, помножене на 11184810. Кожне число виду 509203·2n−1 ділиться принаймні на одне число із множини {3, 5, 7, 13, 17, 241}.

Існує гіпотеза, що 509203 є найменшим числом Різеля. Проблема Різеля полягає у тому, щоб довести, що 509203 є найменшим числом Різеля. Щоб показати, що це число є найменшим, достатньо віднайти просте число для кожного додатнього непарного k, меншого за 509203. Станом на 13 грудня 2017 року залишається віднайти прості для 49 чисел k:

2293, 9221, 23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 146561, 161669, 192971, 206039, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743

Результати підпроекту[ред. | ред. код]

Прості, що було знайдено у PrimeGrid (станом на 5 жовтня 2014 року):

Просте число Цифр Дата Автор
191249·23417696−1 1 028 835 21.11.2010 Jonathan Pritchard
428639·23506452−1 1 055 553 14.01.2011 Brett Melvold
65531·23629342−1 1 092 546 05.04.2011 Adrian Schori
123547·23804809−1 1 145 367 08.05.2011 Jakub Łuszczek
415267·23771929−1 1 135 470 08.05.2011 Alexey Tarasov
141941·24299438−1 1 294 265 26.05.2011 Scott Brown
353159·24331116−1 1 303 802 31.05.2011 Jaakko Reinman
162941·2993718−1 299 145 02.02.2012 Dmitry Domanov
252191·25497878−1 1 655 032 23.06.2012 Jan Haller
398023·26418059−1 1 932 034 05.11.2013 Vladimir Volynsky
304207·26643565−1 1 999 918 10.11.2013 Randy Ready
40597·26808509−1 2 049 571 25.12.2013 Frank Meador
402539·27173024−1 2 159 301 02.10.2014 Walter Darimont
502573·27181987−1 2 162 000 04.10.2014 Denis Iakovlev
273809·28932416−1 2 688 931 13.12.2017 Wolfgang Schwieger

Twin Prime Search[ред. | ред. код]

Twin Prime Search (TPS) — підпроект, що займався пошуком великих простих-близнюків (twin primes). Підпроект використовує програму LLR (для тестування на простоту) та NewPGen (для відсіву), був розпочатий 13 квітня 2006 Майклом Квоком (Michael Kwok).

До цього часу не відомо, чи існує нескінченно багато простих-близнюків.

Проектом TPS було знайдено рекордні прості-близнюки 2003663613·2195000±1 15 січня 2007 році на комп'ютері користувача Eric Vautier. Ці числа складаються з 58711 цифри, що зробило їх найбільшими відомими на той час простими-близнюками. Проект працював у співпраці з PrimeGrid, що зробив більшість LLR тестів.

6 серпня 2009 року 2 проекта (PrimeGrid та Twin Prime Search) оголосили, що рекорд простих-близнюків поновлено. Це прості 65516468355·2333333±1 і складаються з 100355 цифр. Найменше з цих двох простих станом на серпень 2009 також є найбільшим з відомих простих Чена.

Woodall Prime Search[ред. | ред. код]

Woodall Prime Search — це підпроект з пошуку простих чисел Вудала. В теорії чисел число Вудала (що інколи називають числами Каллена другого порядку) — натуральне число виду Wn = n·2n−1

Експоненти n, для яких відповідні числа Вудала прості, утворюють послідовність:

2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, 462, 512, 751, 822, 5312, 7755, 9531, 12379, 15822, 18885, 22971, 23005, 98726, 143018, 151023, 667071, 1195203, 1268979, 1467763, 2013992, 2367906, 3752948, 17016602

В 1976 році Христофер Хулей (англ. Christopher Hooley) показав, що майже всі числа Каллена складені. Доведення Христофера Хулей було перероблено математиком Хірмі Суяма, щоб показати, що воно вірне для будь-якої послідовності n·2n+a+b, де a і b — цілі числа, а також частково для чисел Вудала.

Є гіпотеза, що простих чисел Вудала є нескінчено багато.

Результати підпроекту[ред. | ред. код]

Прості числа Вудала, що було знайдено у PrimeGrid (станом на 21 березня 2018 року):

Просте число Цифр Дата Автор
2013992·22013992−1 606 279 04.08.2007 Lasse Mejling Andersen
2367906·22367906−1 712 818 13.08.2007 Stephen Kohlman
3752948·23752948−1 1 129 757 21.12.2007 Matthew J. Thompson
17016602·217016602−1 5 122 515 21.03.2018 Diego Bertolotti

Підпроекти PRP[ред. | ред. код]

Метою проектів PRP (англ. PRobably Prime) є пошук ймовірно простих чисел, що вимагають додаткової перевірки на простоту методом LLR.

Generalized Fermat Prime Search[ред. | ред. код]

Це підпроект з пошуку узагальнених простих чисел Ферма виду bn+1, де n є ступінню 2.

Про узагальнені прості Ферма[ред. | ред. код]

Протягом XVII сторіччя П'єр Ферма (Pierre de Fermat) та Марен Мерсенн (Marin Mersenne) вивчали дві певні форми чисел, з надією, що вони можуть продукувати велику кількість простих чисел, чи навіть нескінчену кількість простих. Мерсенн працював над переліком простих виду 2n−1, таких, що n < 257. Знадобилось багато років праці, щоб створити коректний перелік таких чисел. У листуванні з Френікл (Frénicle) Ферма висловив переконання, якщо n є ступінню 2, тоді 2n+1 є простим числом. Ферма знав, що 3, 5, 17, 257 і 65537 є простими, але пізніше Леонард Ейлер (Leonhard Euler) показав, що Ферма помилявся, віднайшовши дільник для наступного числа.

На честь натхнених піонерів теорії чисел, числа виду 2n−1 тепер називаються числами Мерсенна, а числа виду 2n+1 числами Ферма. Пошук простих Мерсенна та Ферма значно просунувся від часів XVII сторіччя. Тепер відомі всі прості Мерсенна з кількістю цифр менше за 2'000'000 і досліджено всі числа Ферма аж до 2'000'000'000 цифр! Це стало можливим, тому що протягом XIX ст. було винайдено декілька ефектнивних методів перевірки цих чисел на простоту. Одночасно з цим, деякі тести не менш швидкі були знайдені для перевірки всіх чисел N, якщо відома факторизація чисел N−1 або N+1. Таким чином багато форм чисел можуть бути використані для пошуку найбільших відомих простих, але на диво пошук найбільших простих обмежується числами Мерсенна. Відомими виключенями стали (2148+1)/17 (винайдено у 1951 році з використанням ручного обчислювального методу), 180·(2127−1)2+1 (винайдено у 1951 році) і 391581·2216193−1 (знайдено за допомогою «Amdahl 6» в 1989).

З 50-х по 70-ті розмір найбільших відомих простих постійно ріс разом із швидкостями комп'ютерів, але використовувані алгоритми залишались тими самими, що і наприкінці XIX ст. Але в 80-х роках XX ст., методи, що використовуються для обчислення базової операції алгоритму, добутку, змінилась. Помітивши, що добуток може бути представлений у вигляді суми скінченої послідовності, теорія дискретних транформація показала, як швидко обчислити цю операцію за допомогою швидких перетворень Фур'є (Fast Fourier Transform, FFT). За допомогою цього методу було знайдено деякі прості з більш ніж 10'000 та 100'000 цифр.

В 1994 R. Crandall та B. Fagin винайшли, що за допомогою дискретних зважених трансформацій (Discrete Weighted Transform, DWT) швидкість пошуку простих Мерсенна та Ферма може бути подвоєна. Цей метод було використано у пошуку шости нових простих Мерсена (найбільше з них містило понад 6'000'000 цифр) і довести складеність деяких чисел Ферма. Але прості серед чисел Мерсена та Ферма є рідкістю і шанс знайти нове просте малий.

В 1998 році Y. Gallot помітив, що дискретна зважена трансформація є поліноміальною операцією і якщо представлення чисел не обмежується базою 2, тоді багато чисел можуть бути перевірені на тому ж рівні швидкості, як і числа Мерсенна: узагальнені числа Ферма (Generalized Fermat Numbers, GFN), які є числами виду bn+1, де n є ступінню 2. Він реалізував алгоритм в 1999 у програмі Proth.exe, яка з того часу була ще оптимізована. Теоретичні гіпотези стали дійсністю: пошук узагальнених простих Ферма так само швидкий, як і пошук простих Мерсенна такого ж розміру. За допомогою десятків комп'ютерів було знайдено багато простих, що містять більше ніж 100'000 цифр. У 2002 P. Carmody разом з B. Frey досягли великих успіхів в алгоритмі відсіву узагальнених чисел Ферма. P. Carmody організував прикладання великих зусиль до відсіву за допомогою програми, що була написана D. Underbakke, що таким чином прискорило пошук узагальнених простих чисел Ферма.

Узагальнених чисел Ферма існує набагато більше, ніж чисел Мерсенна того ж розміру і багато з них чекають на те, щоб заповнити прогалини між простими Мерсена, що вже знайдено і тими, що ще ні. Якщо ви зацікавлені у пошуку простих XXI сторіччя, вас запрошують долучитися до Generalized Fermat Prime Search!

Результати підпроекту[ред. | ред. код]

Мега прості GFN (b2n+1, де n>17), що було знайдено у PrimeGrid (станом на 17 червня 2018 року):

Просте число Цифр Дата Автор
9194441048576+1 6 253 210 29.08.2017 Sylvanus A. Zimmerman
2061748524288+1 3 310 478 20.03.2018 Cesare Marini
1880370524288+1 3 289 511 15.01.2018 Scott Brown
475856524288+1 2 976 633 08.08.2012 Masashi Kumagai
356926524288+1 2 911 151 20.06.2012 (bherbihyewrbg)
341112524288+1 2 900 832 15.06.2012 Peyton Hayslette
75898524288+1 2 558 647 19.11.2011 Michael Goetz
5205422262144+1 1 760 679 17.06.2018 Scott Brown
5152128262144+1 1 759 508 05.06.2018 Rob Gahan
4489246262144+1 1 743 828 01.03.2018 Wolfgang Schwieger
4246258262144+1 1 737 493 15.02.2018 Rob Gahan
3933508262144+1 1 728 783 27.01.2018 Alen Kecic
3853792262144+1 1 726 452 10.01.2018 Rod Skinner
3673932262144+1 1 721 010 03.12.2017 Sean Humphries
3596074262144+1 1 718 572 16.11.2017 Howard Gordon
3547726262144+1 1 717 031 30.10.2017 Scott Brown
3060772262144+1 1 700 222 30.06.2017 Sean Humphries
2676404262144+1 1 684 945 22.03.2017 Wolfgang Schwieger
2611204262144+1 1 682 141 11.03.2017 Roman Vogt
2514168262144+1 1 677 825 24.02.2017 William de Thomas
2042774262144+1 1 654 187 24.11.2016 Tsuyoshi Ohsugi
1828858262144+1 1 641 593 10.08.2016 Brook Harste
1615588262144+1 1 627 477 04.05.2016 Brook Harste
1488256262144+1 1 618 131 05.03.2016 Stefan Larsson
1415198262144+1 1 612 400 16.02.2016 Frank Matillek
773620262144+1 1 543 643 19.04.2012 Senji Yamashita
676754262144+1 1 528 413 12.02.2012 Carlos Loureiro
525094262144+1 1 499 526 18.01.2012 David Tomecko
361658262144+1 1 457 075 29.10.2011 Michel Johnson
145310262144+1 1 353 265 08.02.2011 Ricky L Hubbard
40734262144+1 1 208 473 08.03.2011 Senji Yamashita

Підпроекти Sieve[ред. | ред. код]

Підпроекти Sieve (з англ. sieve — відсів) займаються відсіюванням кандидатів для підпроектів LLR. Відсів складених кандидатів може бути набагато ефективніше за перевірку на простоту методом LLR. Із часом, коли глибина відсіву росте, ефективність відсіву падає і видалення складених чисел із кандидатів на простоту відбувається все рідше. Коли середній час на відсів кандидатів стає спвіставний з середнім часом на перевірку методом LLR, доцільність використання відсіву втрачається.

321 Prime Search Sieve[ред. | ред. код]

Підпроект 321 Prime Search Sieve займається відсівом для підпроекту 321 Prime Search

Наразі підпроект поставлено на паузу, оскільки була досягнута оптимальна глибина відсіву.

Cullen/Woodall Sieve[ред. | ред. код]

Підпроект Cullen/Woodall Sieve займається відсівом для Cullen та Woodall Prime Search

Наразі підпроект поставлено на паузу, оптимальна глибина відсіву у 2500T була досягнута навесні 2012.

Generalized Cullen/Woodall Sieve[ред. | ред. код]

Підпроект Generalized Cullen/Woodall Sieve займається відсівом для Generalized Cullen/Woodall Prime Search

Proth Prime Search Sieve[ред. | ред. код]

Підпроект Proth Prime Search Sieve займається відсівом для Proth Prime Search

Sierpinski (ESP/PSP/SoB) Sieve[ред. | ред. код]

Підпроект об'єднує зусилля з відсіву для підпроектів Seventeen or Bust, Prime Sierpinski Project, Extended Sierpinski Project

Відсів для Seventeen or Bust та Prime Sierpinski Project поставлено на паузу, оскільки була досягнута оптимальна глибина відсіву.

Відсів Extended Sierpinski Project Sieve для Extended Sierpinski Project розпочато 29 червня 2014 року.

Наразі підпроект поставлено на паузу, оптимальна глибина відсіву для Extended Sierpinski Project була досягнута у червні 2016 року.

The Riesel Problem Sieve[ред. | ред. код]

Підпроект The Riesel Problem Sieve займається відсівом для The Riesel Problem

Наразі підпроект поставлено на паузу, оскільки була досягнута оптимальна глибина відсіву.

Project Staging Area (PSA)[ред. | ред. код]

Від початку PSA було створено задля дослідження, тестування та підготовки майбутніх BOINC підпроектів для PrimeGrid. У PSA досі ведеться пошук простих чисел інших форм, яких немає в підпроектах BOINC. Існує два напрямки участі у PSA — PRPNet та Manual Sieving:

  • PRPNet було розроблено Марком Роденкірхом (англ. Mark Rodenkirch), PRPNet дуже подібний до BOINC, але використовується тільки для пошуку простих чисел. PRPNet не має  (інтерфейсної оболонки). Натомість він стартує або в DOS вікні (Windows) або в командному терміналі (Linux). Все досить просто — скачай, розпакуй файл для твоєї ОС, відредагуй декілька рядків у файлі prpclient.ini і запускай.
  • Ручний відсів (Manual Sieving) — гарний відсів веде до кращого результату під час перевірки чисел на простоту. Деякі пошуки вимагають досить значних зусиль, тому для таких відсівів залучається спільнота. Є ділька проектів, що координуються за допомогою постингу на форумі.

За участь в PSA існує ручна процедура нарахування очок в віртуальний підпроект PSA в BOINC.

Підпроекти PRPNet[ред. | ред. код]

  1. 121 Prime Search
    • server=121:0:1:prpnet.primegrid.com:12001
  2. 27 Prime Search
    • server=27:0:1:prpnet.primegrid.com:12006
  3. Factorial Prime Search
    • server=FPS:0:1:prpnet.primegrid.com:12002
  4. Generalized Cullen/Woodall Prime Search
    • server=GCW:0:1:prpnet.primegrid.com:12004
  5. Generalized Fermat Prime Search
    • server=GFN32768:0:1:prpnet.primegrid.com:12005
    • server=GFN65536:0:1:prpnet.primegrid.com:12003
    • server=GFN262144:0:1:prpnet.primegrid.com:11002
    • server=GFN524288:0:1:prpnet.primegrid.com:11001
  6. Primorial Prime Search
    • server=PRS:0:1:prpnet.primegrid.com:12008
  7. Wieferich Prime Search
    • server=WIEFERICH:0:2:prpnet.primegrid.com:13000
  8. Wall-Sun-Sun Prime Search
    • server=WALLSUNSUN:0:2:prpnet.primegrid.com:13001

Підпроекти Manual Sievieng[ред. | ред. код]

  1. Factorial Prime Search (Manual Sieve)
  2. Primorial Prime Search (Manual Sieve)
  3. Sierpinski/Riesel base 5 Project (Manual Sieve)
  4. Generalized Fermat Prime Search (Manual Sieve)
  5. PPS/RSP (Manual Sieve)

Бейджики[ред. | ред. код]

PrimeGrid нагороджує користувачів, що досягли певного рівня зароблених очок, бейджиками. Ці відзнаки не дають нікому ніякої переваги, але багато хто сприймає бейджі як знак певного досягнення. Нагорода бейджами використовується також для заохочення участі у менш популярних підпроектах. Поточні рівні бейджів: Бронза (10'000) / Срібло (100'000) / Золото (500'000) / Аметист (1'000'000) / Рубін (2'000'000) / Бірюза (5'000'000) / Нефрит (10'000'000) / Сапфір (20'000'000) / Смарагд (50'000'000) / Подвійна Бронза (100'000'000) / Подвійне Срібло (200'000'000) / Подвійне Золото (500'000'000) / Подвійний Аметист (1'000'000'000) / Подвійний Рубін (2'000'000'000) / Подвійна Бірюза (5'000'000'000) / Подвійний Нефрит (10'000'000'000) / Подвійний Сапфір (20'000'000'000) / Подвійний Смарагд (50'000'000'000)

Підпроект Бейджики
321 LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
321 Sieve More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
AP More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
Cullen LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
CW Sieve More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
ESP LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
GCW LLR
GCW Sieve
GFN More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
PSP LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
PSP Sieve More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
PSA More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
PPS LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
PPS Sieve More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
SOB LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
SGS LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
SR5 LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
TRP LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
TRP Sieve More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
TPS LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits
Woodall LLR More than 10'000 credits More than 100'000 credits More than 500'000 credits More than 1'000'000 credits More than 2'000'000 credits More than 5'000'000 credits More than 10'000'000 credits More than 20'000'000 credits More than 50'000'000 credits More than 100'000'000 credits More than 200'000'000 credits More than 500'000'000 credits More than 1'000'000'000 credits More than 2'000'000'000 credits More than 5'000'000'000 credits More than 10'000'000'000 credits More than 20'000'000'000 credits More than 50'000'000'000 credits

До квітня 2014 року між підпроектами LLR та AP26/Sieve/GFN/PSA існувала різниця у рівнях для бейджиків одного кольору. 9 квітня 2014 року цю різницю було скасовано, у тому числі ретроспективно по відношенню до тих підпроектів, що на той час вже були завершені або призупинені.

29 червня 2014 року розпочато ESP Sieve в підпроекті PSP Sieve, перейменований на Sierpinski (ESP/PSP/SoB) Sieve, досягнення за яким використовуються для бейджа PSP Sieve.

18 липня 2014 року із PRPNet в BOINC перенесено підпроект PPS-Mega, досягнення за яким зараховуються для бейджа PPS LLR.

20 вересня 2016 року розпочато підпроект AP27 Search, досягнення за яким зараховуються для бейджа AP.

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. а б перевіряються проектом Seventeen or Bust
  2. Chris Caldwell, The Largest Known Primes

Джерела[ред. | ред. код]