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 OpenCL.jpg OpenCL.jpg
321 Prime Search (LLR) llr321 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
Cullen Prime Search (LLR) llrCUL 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
Extended Sierpinski Problem (LLR) llrESP 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
Prime Sierpinski Problem (LLR) llrPSP 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 (LLR) llrPPS 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 Extended (LLR) llrPPSE 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 Mega Prime Search (LLR) llrMEGA 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
Seventeen or Bust (LLR) llrSOB 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
Sierpinski/Riesel Base 5 Problem (LLR) llrSR5 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
Sophie Germain Prime Search (LLR) llrTPS 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
Woodall Prime Search (LLR) llrWOO 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
The Riesel Problem (LLR) llrTRP 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
Sierpinski Problem ESP/PSP/SoB (Sieve) psp_sr2sieve 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
The Riesel Problem (Sieve) trp_sr2sieve 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 20 x 20 pixel square.gif Yes.gif
Generalized Fermat Prime Search n=15 (GFN-15) genefer15 Yes.gif Yes.gif Yes.gif Yes.gif Yes.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) genefer 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) genefer21 Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif Yes.gif
Generalized Fermat Prime Search World Record n=22 (GFN-WR) 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

AP26[ред.ред. код]

Про 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 року підпроект було завершено.

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.

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

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

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

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

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
10223 10223[1]
21181
22699 22699[1]
24737
55459
67607 67607[1]
79309
79817
152267
156511
168451
222113
225931
237019

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

Станом на 30 жовтня 2015 року підпроектом Proth Prime Search були знайдені наступні Мега Прості:

Просте число Цифр Дата Автор
9·23497442+1 1 052 836 23.10.2012 Heinz Ming
7·25775996+1 1 738 749 02.11.2012 Martyn Elvy
129·23328805+1 1 002 073 24.07.2014 Eric Clifton
193·23329782+1 1 002 367 25.07.2014 Raymond Ottusch
179·23371145+1 1 014 819 23.09.2014 John Christy
255·23395661+1 1 022 199 01.12.2014 John Christy
177·23411847+1 1 027 071 06.01.2015 William Darney
245·23411973+1 1 027 109 07.01.2015 Rick Channing
159·23425766+1 1 031 261 01.02.2015 Evelyn Chew
113·23437145+1 1 034 686 14.02.2015 Evelyn Chew
197·23477399+1 1 046 804 19.04.2015 Tom Greer
249·23486411+1 1 049 517 10.05.2015 Evelyn Chew
195·23486379+1 1 049 507 10.05.2015 Naoki Yoshioka
135·23518338+1 1 059 128 02.08.2015 Evelyn Chew
141·23529287+1 1 062 424 01.09.2015 Chris Hoefliger
191·23548117+1 1 068 092 30.10.2015 Roman Azarenko

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. Наразі залишається знайти прості числа для 6 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
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

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

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

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

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

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

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

Гіпотеза полягає у тому, що найменшим парним числом Різеля за основою 5 є k=346802. Щоб довести це, достатньо показати, що існує просте число виду k·5n−1 для кожного парного k < 346802. Наразі це доведено для всіх парних k, окрім наступних 78 значень (станом на 21 жовтня 2015 року): k = 3622, 4906, 23906, 26222, 35248, 35816, 52922, 53546, 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, 171362, 177742, 180062, 182398, 187916, 189766, 190334, 194368, 195872, 201778, 204394, 206894, 207494, 213988, 231674, 238694, 239062, 239342, 246238, 248546, 259072, 265702, 267298, 271162, 273662, 285598, 285728, 296024, 298442, 301562, 304004, 306398, 313126, 318278, 322498, 325922, 327926, 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 (станом на 21 жовтня 2015 року):

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, тоді можна сказати, що знайдено прості числа-близнюки. Можливість знайти просте Софі Жермен або прості-близнюки робить пошук саме у цьому підпроекті привабливішим.

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. Станом на 5 жовтня 2014 року залишається віднайти прості для 50 чисел 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, 273809, 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

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 також є найбільшим з відомих простих Чена.

25 грудня 2011 року Timothy D Winslow знайшов найбільшу відому пару простих-близнюків 3756801695685·2666669±1. Ці прості складаються з 200700 цифр.

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

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

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

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

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

Просте число Цифр Дата Автор
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

Підпроекти 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, що було знайдено у PrimeGrid (станом на 9 листопада 2015 року):

Просте число Цифр Дата Автор
145310262144+1 1 353 265 08.02.2011 Ricky L Hubbard
40734262144+1 1 208 473 08.03.2011 Senji Yamashita
361658262144+1 1 457 075 29.10.2011 Michel Johnson
75898524288+1 2 558 647 19.11.2011 Michael Goetz
525094262144+1 1 499 526 18.01.2012 David Tomecko
676754262144+1 1 528 413 12.02.2012 Carlos Loureiro
773620262144+1 1 543 643 19.04.2012 Senji Yamashita
341112524288+1 2 900 832 15.06.2012 Peyton Hayslette
356926524288+1 2 911 151 20.06.2012 (bherbihyewrbg)
475856524288+1 2 976 633 08.08.2012 Masashi Kumagai
42654182131072+1 1 000 075 09.11.2015 Nortech

Прості GFN, що було знайдено у PrimeGrid (станом на 2 грудня 2015 року):

Підпроекти 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.

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 року.

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
AP26 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
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 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
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.

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

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

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

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

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