PrimeGrid — проєкт добровільних розподілених обчислень на платформі BOINC і PRPNet, метою якого є пошук дуже великих простих чисел різного виду, водночас прагнучи вирішити давні математичні гіпотези. PrimeGrid пропонує низку підпроєктів з відсіву й пошуку простих чисел. Більшість з них доступні через клієнт BOINC, у якому повністю автоматизовано завантаження, обробку й повернення результатів. Решта проєктів доступні через клієнт PRPNet, вони потребують запуску вручну. Є також активності, що зараховуються в PRPNet, які потребують завантаження, запуску і вивантаження результатів вручну. Різні підпроєкти можуть бути запущені на різноманітних операційних системах, є підпроєкти, що можуть бути виконанні із застосуванням CPU, GPU, або CPU та GPU одночасно. Під час виконання тестів LLR (Lucas–Lehmer–Riesel) CPU з набором інструкцій AVX (Advanced Vector Extensions) і FMA (Fused Multiply-Add) дають кращий результат без використання GPU.

PrimeGrid
Тип добровільні обчислення і проєкт BOINCd
Автор Rytis Slatkevičius
Перший випуск 12 червня 2005; 18 років тому (2005-06-12)
Апаратна платформа Intel x86, x86_64 CPU, AMD x86_64 CPU, Nvidia OpenCL/CUDA, ATI OpenCL
Платформа BOINC, PRPNet, Genefer, LLR, PFGW
Операційна система Microsoft Windows, Linux, Mac OS 10.5+
Стан розробки Діючий
Вебсайт primegrid.com

CMNS: PrimeGrid у Вікісховищі

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

Історія проєкту ред.

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 року розпочато підпроєкт Woodall LLR.
  • у серпні 2007 року розпочато підпроєкт Cullen LLR.
  • 15 вересня 2007 року розпочато об'єднаний Cullen/Woodall Sieve.
  • 13 жовтня 2007 року розпочато підпроєкт PSP Sieve.
  • 18 листопада 2007 року розпочато підпроєкт 321 LLR.
  • 11 грудня 2007 року розпочато підпроєкт PSP LLR.

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

2008 рік

  • 29 лютого 2008 року встановлено співпрацю з Proth Search.
  • 15 березня 2008 року розпочато серію челенджів. Встановлено рекорд одного дня — понад 820К очок.
  • 13 квітня 2008 року Project Staging Area додано задля допомоги у адаптації нових застосунків для BOINC.
  • 10 березня 2008 року завершено підпроєкт PrimeGen.
  • 28 серпня 2008 року чат Meebo додано до форуму.
  • 26 грудня 2008 року розпочато підпроєкт AP26.

2009 рік

  • У лютому 2009 року PrimeGrid товаришує з 12121 Search у пошуку простих форм 121·2n−1 та 27·2n−1. PrimeGrid додає форму +1 і розпочинає пошук усіх чотирьох форм у підпроєкті 27121 Search.
  • 12 травня 2009 року розпочато Factorial Prime Search.
  • 3 серпня 2009 року — в PrimeGrid введено систему бейджів.
  • 16 серпня 2009 року — розпочато Sophie Germain Prime Search.
  • 16 вересня 2009 року PrimeGrid долучається до підпроєктів Seventeen or Bust задля розв'язання проблеми Серпінського.
  • 20 жовтня 2009 року випущено ppsieve для PPSE sieve, що у 6 разів швидший за попередній.
  • 5 листопада 2009 року розпочато Generalized Fermat Prime Search.
  • 8 листопада 2009 року з'явилась надія на появу застосунку для GPU в PrimeGrid. Розпочато розробку та тестування.
  • У грудні 2009 року додано підтримку CUDA для AP26.

2010 рік

  • 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).

2011 рік

  • На початку січня 2011 року розпочалась співпраця PrimeGrid з Sierpinski/Riesel Base 5 Project. Підпроєкт SR5 було розпочато в PRPNet у тестовому режимі.
  • 22 квітня 2011 року призупинено підпроєкт 321 Prime Search (Sieve).
  • 1 жовтня 2011 року в PRPNet розпочато підпроєкт The dual Sierpinski problem (Five or Bust).

2012 рік

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

2013 рік

  • Наприкінці січня 2013 року відбулась міграція проєкту PrimeGrid на новий сервер.
  • У лютому 2013 року усі LLR додатки отримали підтримку AVX для 64-бітних платформ.
  • У травні 2013 року введено нову систему бейджиків.
  • 28 травня 2013 року підпроєкт PPS-Sieve отримав підтримку OpenCL для Mac/ATI.
  • Наприкінці червня 2013 року введено систему бонусного преміювання за участь у проєктах із перевірки гіпотез SR5, TRP, PSP і SoB (+10 %) та підпроєктів з довготривалими завданнями: 321, TRP-LLR (+10 %), CUL, WOO (+20 %), PSP (+35 %), SoB, GFN-WR (+50 %).
  • У вересні 2013 року додатки GFN отримали підтримку AVX та OpenCL.

2014 рік

  • У травні 2014 року розпочато повторну перевірку в BOINC результатів підпроєкту SR5, отриманих в PRPNet.
  • На початку червня 2014 року підпроєкт Extended Sierpinski Problem портовано з PRPNet до BOINC.
  • 29 червня 2014 року розпочато підпроєкт ESP Sieve — підпроєкт «сіялка» для підпроєкту ESP LLR.
  • 18 липня 2014 року підпроєкт PPS-MEGA портовано з PRPNet до BOINC.

2015 рік

  • У жовтні 2015 року підпроєкти GFN 32768, GFN 65536, GFN 131072 (Low) і GFN 131072 (Mega) портовано з PRPNet до BOINC, а у листопаді — GFN 262144, GFN 524288 та GFN 1048576.

2016 рік

  • У вересні 2016 року розпочато підпроєкт AP27.
  • У жовтні 2016 року розпочато підпроєкт GCW (Sieve).

2017 рік

  • У квітні 2017 року розпочато підпроєкт GCW (LLR).
  • 25 квітня 2017 року завершено підпроєкт TRP (Sieve).
  • У квітні 2017 року в PRPNet призупинено підпроєкти Wall-Sun-Sun і Wieferich.

2018 рік

  • Наприкінці січня 2018 року зупинено видачу завдань GFN-15 для CPU. Завдання GFN-15 стали виключно GPU-сумісні.

2019 рік

  • У лютому 2019 року розпочато підпроєкт Do You Feel Lucky?.
  • 1 травня 2019 року завершено підпроєкт GCW (Sieve).
  • У травні 2019 року усі LLR додатки отримали підтримку AVX-512.
  • 6 вересня 2019 року розпочато підпроєкт Fermat Divisor Search.

2020 рік

  • 1 лютого 2020 року зупинено видачу завдань GFN-16 для CPU. Завдання GFN-16 стали виключно GPU-сумісні.
  • 4 листопада 2020 року завершено підпроєкт 321 Sieve.
  • У листопаді 2020 року розпочато підпроєкт Wieferich and Wall-Sun-Sun Prime Search.

2021 рік

  • У березні 2021 року завершено підпроєкт Fermat Divisor Search.
  • У листопаді 2021 року завершено підпроєкт GFN-17-Low.

Визначні дати ред.

  • 12.06.2005 — народився Message@Home з підпроєктом Message7, у якому було відкрито реєстрацію для перших 50 користувачів
  • 01.09.2005 — Message@Home змінює назву на PrimeGrid
  • 07.08.2007 — в PrimeGrid знайдено найбільше відоме просте Вудала: 2013992·22013992−1
  • 20.08.2007 — в PrimeGrid знайдено найбільше відоме просте Вудала: 2367906·22367906−1
  • 21.12.2007 — в PrimeGrid знайдено найбільше відоме просте Вудала: 3752948·23752948−1
  • 20.04.2009 — в PrimeGrid знайдено найбільше відоме просте Каллена: 6328548·26328548+1
  • 25.07.2009 — в PrimeGrid знайдено найбільше відоме просте Каллена: 6679881·26679881+1
  • 07.12.2009 — в PRPNet знайдено найбільше відоме узагальнене просте Вудала: 563528·13563528−1
  • 12.04.2010 — в PrimeGrid знайдено першу відому арифметичну прогресію 26 простих чисел: 43142746595714191+23681770*23#*n для n=0..25
  • 04.10.2010 — в PRPNet знайдено найбільше відоме факторіальне просте: 94550!−1
  • 14.12.2010 — в PRPNet знайдено найбільше відоме факторіальне просте: 103040!−1
  • 20.12.2010 — в PRPNet знайдено найбільше відоме прайморіальне просте: 843301#−1
  • 08.02.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Ферма: 145310262144+1
  • 24.02.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Вудала: 404882·43404882−1
  • 11.06.2011 — в PRPNet знайдено найбільше відоме факторіальне просте: 110059!+1
  • 22.06.2011 — в PrimeGrid знайдено найбільший відомий дільник числа Ферма: 9·22543551+1 ділить F(2543548)
  • 29.10.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Ферма: 361658262144+1
  • 19.11.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Ферма: 75898524288+1
  • 25.12.2011 — в PrimeGrid знайдено найбільшу відому пару простих−близнюків: 3756801695685·2666669±1
  • 29.01.2012 — в PRPNet знайдено найбільше відоме узагальнене просте Каллена: 427194·113427194+1
  • 28.02.2012 — в PRPNet знайдено найбільше відоме прайморіальне просте: 1098133#−1
  • 09.04.2012 — в PrimeGrid знайдено найбільше відоме просте Софі Жермен: 18543637900515·2666667−1, 18543637900515·2666668−1 (2p+1)
  • 15.06.2012 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 341112524288+1
  • 20.06.2012 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 356926524288+1
  • 08.08.2012 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 475856524288+1
  • 13.05.2013 — в PrimeGrid знайдено найбільший відомий дільник числа Ферма: 57·22747499+1 ділить F(2747497)
  • 29.12.2013 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 37292·51487989+1
  • 14.01.2014 — в PrimeGrid знайдено найбільше відоме просте 321: 3·210829346+1
  • 17.01.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 59912·51500861+1
  • 31.01.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 178658·51525224−1
  • 06.02.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 22934·51536762−1
  • 21.03.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 330286·51584399−1
  • 09.04.2014 09:13:42 UTC — в PrimeGrid знайдено найбільше відоме просте за основою 5: 104944·51610735−1
  • 09.04.2014 18:33:30 UTC — в PrimeGrid знайдено найбільше відоме просте за основою 5: 207394·51612573−1
  • 25.04.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 326834·51634978−1
  • 19.06.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 22478·51675150−1
  • 27.06.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 138172·51714207−1
  • 23.07.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 24032·51768249+1
  • 25.07.2014 — в PrimeGrid знайдено найбільший відомий дільник числа Ферма: 193·23329782+1 ділить F(3329780)
  • 17.08.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 133778·51785689+1
  • 21.09.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 325918·51803339−1
  • 18.10.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 109208·51816285+1
  • 22.11.2014 — в PrimeGrid знайдено найбільше відоме просте 321: 3·211484018−1
  • 13.03.2015 — в PrimeGrid знайдено найбільше відоме просте 321: 3·211731850−1
  • 23.05.2015 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 144052·52018290+1
  • 23.06.2015 — в PrimeGrid знайдено найбільше відоме просте 321: 3·211895718−1
  • 21.10.2015 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 100186·52079747−1
  • 10.11.2015 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 154222·52091432+1
  • 11.01.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 306398·52112410−1
  • 29.02.2016 — в PrimeGrid знайдено найбільше відоме просте Софі Жермен: 2618163402417·21290000−1, 2618163402417·21290001−1 (2p+1)
  • 06.03.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 77072·52139921+1
  • 15.03.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 92158·52145024+1
  • 25.03.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 296024·52185270−1
  • 30.05.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 53546·52216664−1
  • 20.08.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 180062·52249192−1
  • 14.09.2016 — в PrimeGrid знайдено найбільшу відому пару простих−близнюків: 2996863034895·21290000±1
  • 08.10.2016 — в PRPNet знайдено найбільше відоме узагальнене просте Каллена: 682156·79682156+1
  • 31.10.2016 — в PrimeGrid знайдено найбільше відоме просте Прота, а також найбільше відоме просте Кольбера: 10223·231172165+1
  • 21.08.2017 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 1341174·531341174+1
  • 25.08.2017 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 171362·52400996−1
  • 29.08.2017 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 9194441048576+1
  • 17.09.2017 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 301562·52408646−1
  • 18.01.2018 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 1323365·1161323365+1
  • 11.03.2018 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 1806676·411806676+1
  • 21.03.2018 — в PrimeGrid знайдено найбільше відоме просте Вудала: 17016602·217016602+1
  • 19.06.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 327926·52542838−1
  • 20.06.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 81556·52539960+1
  • 29.07.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 66916·52628609−1
  • 15.08.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 194368·52638045−1
  • 31.10.2018 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 10590941048576+1
  • 26.04.2019 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 138514·52771922+1
  • 21.06.2019 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 88444·52799269−1
  • 23.06.2019 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 322498·52800819−1
  • 02.09.2019 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 2805222·252805222+1
  • 23.09.2019 — в PrimeGrid знайдено першу відому арифметичну прогресію з 27 простих чисел: 224584605939537911+81292139*23#*n для n=0..26
  • 05.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 35816·52945294−1
  • 09.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 146264·52953282−1
  • 12.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 238694·52979422−1
  • 16.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 207494·53017502−1
  • 01.05.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 118568·53112069+1
  • 13.08.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 109838·53168862−1
  • 28.08.2021 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 2525532·732525532+1
  • 18.09.2021 — в PRPNet знайдено найбільше відоме прайморіальне просте: 3267113#−1
  • 09.08.2022 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 19517341048576+1

Підпроєкти (BOINC) ред.

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

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

Застосунок app_name      
         
CPU NVIDIA   CPU NVIDIA   CPU NVIDIA   CPU NVIDIA   CPU NVIDIA  
CUDA     CUDA     CUDA     CUDA     CUDA    
321 Prime Search LLR (321) llr321                                        
AP27 Search (AP27) ap26                                        
Cullen Prime Search LLR (CUL) llrCUL                                        
Extended Sierpinski Problem LLR (ESP) llrESP                                        
Generalized Cullen/Woodall Prime Search LLR (GCW) llrGCW                                        
Prime Sierpinski Problem LLR (PSP) llrPSP                                        
Proth Prime Search LLR (PPS) llrPPS                                        
Proth Prime Search Extended LLR (PPSE) llrPPSE                                        
Proth Mega Prime Search LLR (MEGA) llrMEGA                                        
Seventeen or Bust LLR (SOB) llrSOB                                        
Sierpinski / Riesel Base 5 LLR (SR5) llrSR5                                        
Sophie Germain Prime Search LLR (SGS) llrTPS                                        
The Riesel Problem LLR (TRP) llrTRP                                        
Woodall Prime Search LLR (WOO) llrWOO                                        
Proth Prime Search Sieve (PPS-Sieve) pps_sr2sieve                                        
Generalized Fermat Prime Search n=15 (GFN-15) genefer15                                        
Generalized Fermat Prime Search n=16 (GFN-16) genefer16                                        
Generalized Fermat Prime Search n=17 Mega (GFN-17-Mega) genefer17mega                                        
Generalized Fermat Prime Search n=18 (GFN-18) genefer18                                        
Generalized Fermat Prime Search n=19 (GFN-19) genefer19                                        
Generalized Fermat Prime Search n=20 (GFN-20) genefer20                                        
Generalized Fermat Prime Search n=21 (GFN-21) genefer                                        
Generalized Fermat Prime Search n=22 (GFN-22) genefer_wr                                        
Do You Feel Lucky? (GFN World Record) genefer_extreme                                        
Wieferich and Wall-Sun-Sun ww                                        

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

  • виконання завдань 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

Початкові підпроєкти ред.

Message7 ред.

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

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.

PrimeGen ред.

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

Підпроєкти AP ред.

AP26 ред.

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

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

12 квітня 2010 року у підпроєкті AP26 було знайдено першу відому арифметичну прогресію 26 простих чисел:

AP Тип Дата Автор
43142746595714191+23681770*23#*n для n=0..25 AP26 12.04.2010 Benoãt Perichon

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

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

AP27 Search ред.

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

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

23 вересня 2019 року у підпроєкті AP27 було знайдено першу відому арифметичну прогресію 27 простих чисел:

AP Тип Дата Автор
224584605939537911+81292139*23#*n для n=0..26 AP27 23.09.2019 Rob Gahan

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

Підпроєкти LLR ред.

321 Prime Search ред.

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

Експоненти n, для яких відповідні числа форми 3·2n+1 прості, утворюють послідовність A002253 [Архівовано 29 липня 2021 у Wayback Machine.]:

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, 16408818.

Експоненти n, для яких відповідні числа форми 3·2n−1 прості, утворюють послідовність A002235 [Архівовано 24 березня 2022 у Wayback Machine.]:

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, 16819291, 17748034, 18196595, 18924988.

Про 321 Search ред.

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

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

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

Cullen Prime Search ред.

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

Експоненти n, для яких відповідні числа Каллена прості, утворюють послідовність A005849 [Архівовано 15 червня 2021 у Wayback Machine.]:

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 анонімний користувач з Японії

Extended Sierpinski Problem ред.

В 1962 році Джон Селфридж[en] висунув гіпотезу, що число Серпінського 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.

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

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

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

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

Fermat Divisor Search ред.

Підпроєкт з пошуку простих чисел Прота k·2n+1 — дільників чисел Ферма.

Підпроєкт вважається частиною проєкту Proth Prime Search, отож всі результати і досягнення зараховуються до PPS-LLR.

У березні 2021 року підпроєкт Fermat Divisor Search було завершено.

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

Анонсовані результати підроєкту:

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 2805222·252805222+1 3 921 539 02.09.2019 Tom Greer
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 21.08.2017 Hiroyuki Okazaki
55 Cullen
68 Cullen 129897·68129897+1 238 043 25.05.2010 [SG-SPEG]Puzzle-Peter
69 Cullen
73 Cullen 2525532·732525532+1 4 705 888 28.08.2021 Tom Greer
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

Prime Sierpinski Problem ред.

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

Послідовність A076336 [Архівовано 16 липня 2021 у Wayback Machine.] відомих чисел Серпінського починається так:

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

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

Найменше відоме просте число Серпінського — 271129. Щоб довести, що 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.

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

  • PPS: k·2n+1 для k<1200
  • PPSE: k·2n+1 для 1200<k<10000
  • MEGA: k·2n+1 для 100<k<300 і 3.322M<=n<3.6M
  • DIV: k·2n+1 для 5<=k<=49 і n<=9M

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

Підпроєкт 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 року):

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

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

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

Seventeen or Bust ред.

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

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

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

Те, що число 78557 є числом Серпінського, було доведено в 1962 році Джоном Селфриджем[en] (англ. 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, для яких відомі прості k·2n+1, наведено в таблиці:

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

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

Прості підпроєкту SoB, що було знайдено у 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, окрім наступних 30 значень (станом на 1 травня 2020 року): 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, 126134, 139196, 152588.

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

Гіпотеза полягає у тому, що найменшим парним числом Різеля за основою 5 є k=346802. Щоб довести це, достатньо показати, що існує просте число виду k·5n−1 для кожного парного k < 346802. Наразі це доведено для всіх парних k, окрім наступних 57 значень (станом на 19 червня 2022 року): k = 4906, 23906, 26222, 35248, 52922, 68132, 71146, 76354, 81134, 92936, 102952, 109238, 109862, 127174, 131848, 134266, 136804, 143632, 145462, 145484, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 177742, 182398, 187916, 189766, 190334, 195872, 201778, 204394, 206894, 213988, 231674, 239062, 239342, 246238, 248546, 259072, 265702, 267298, 271162, 285598, 285728, 298442, 304004, 313126, 318278, 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 (станом на 19 червня 2022 року):

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
2996863034895·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. Станом на 11 березня 2021 року залишається віднайти прості для 44 чисел k:

23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 161669, 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 (станом на 7 лютого 2021 року):

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, для яких відповідні числа Вудала прості, утворюють послідовність A002234 [Архівовано 29 липня 2021 у Wayback Machine.]:

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

Підпроєкти WW ред.

Wieferich Prime Search ред.

Просте p називається простим Віферіха, якщо   ділить  . Ці прості названі за ім'ям Артура Віферіха, німецького математика, який у 1909 році довів, що якщо перша частина останньої теореми Ферма не виконується для деякої експоненти p, тоді p задовільняє умові   для  .

Незважаючи на численні пошуки, донині відомо лише 2 простих числа Віферіха — це 1093 та 3511 (послідовність A001220 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Рідкісність таких простих веде до зацікавлення у пошуку «майже» простих Віферіха. Вони визначаються як спеціяльні випадки   для малих значень  .

Класичне означення близькості ред.

Просте число p, що задовільняє рівнянню   для малих значень  , назагал називається майже простим Віферіха.

Історія пошуку ред.

Пошук простих і майже простих Віферіха триває вже більше 80 років. Ось історія прогресу:

Верхня межа Автор Дата
16000 Beeger 1940
50000 Froberg unknown
100000 Kravitz 1960
200183 Pearson 1964
500000 Riesel 1964
30·106 Froberg 1968
3·109 Brillhart, Tonascia, and Weinberger 1971
6·109 Lehmer 1981
61·109 Clark 1996
4·1012 Crandall, Dilcher, and Pomerance 1997
46·1012 Brown and McIntosh 2001
200·1012 Crump 2002
1.25·1015 Knauer and Richstein 2005
3·1015 Carlisle, Crandall, and Rodenkirch 2006
6.7·1015 Dorais and Klyve 2011
10·1015 PrimeGrid 13.01.2012
14·1015 PrimeGrid 14.04.2012
14·1016 PrimeGrid 11.08.2014

За цей час верхня межа пошуку досягла вже 136·1015. PrimeGrid почав пошук з 3·1015. Причина цього полягає в тому, що Dorais і Klyve дали інше означення майже простого Віферіха. Таким чином вони не шукали майже простих Віферіха за класичним означенням. PrimeGrid не сподівався знайти простих Віферіха у проміжку між 3·1015 та 6.7·1015, але сподівався знайти декілька майже простих. Так сталося, що визначення майже простого Віферіха, що дали Dorais та Klyve, зловило декілька «класичних» майже простих Віферіха, але не всі. PrimeGrid шукає майже прості за умовою |A| < = 1000.

Wall-Sun-Sun Prime Search ред.

Просте Вола-Суня-Суня (або Фібоначчі-Віферіха) — це таке просте p > 5, для якого p2 ділить число Фібоначчі  , де символ Лежандра   визначається як  

Хоча існує гіпотеза, що таких простих існує нескінчено багато, досі не відомо жодного Вола-Суня-Суня простого. Станом на листопад 2013, якщо вони і існують, вони мають бути більші за 26·1015.

Брак удачі в пошуку простих веде до зацікавленості в пошуку «майже» простих Вола-Суня-Суня. Вони визначаються як спеціальні випадки   для малих значень |A|.

Класичне означення близькості ред.

Просте число p, що задовільняє рівнянню   для малих значень |A|, назагал називається майже простим Вола-Суня-Суня.

Історія пошуку ред.

Вехня межа Автор Дата
109 Williams 1982
232 Montgomery 1991
100·1012 Knauer and McIntosh 2003
200·1012 McIntosh and Roettger 2005
970·1012 Dorais and Klyve 2011
1015 PrimeGrid 28.12.2011
1.5·1015 PrimeGrid 10.01.2012
2·1015 PrimeGrid 22.01.2012
2.5·1015 PrimeGrid 02.03.2012
6·1015 PrimeGrid 29.07.2012
28·1015 PrimeGrid 31.03.2014

Числа названі на честь Доналда Дайнса Вола (Donald Dines Wall) і братів близнюків Чжи Хон Суня (Zhi Hong Sun) та Чжи Вей Суня (Zhi Wei Sun), які в 1992 році показали, що якщо перша умова великої теореми Ферма не виконується для певного простого p, то p має бути простим числом Фібоначчі — Віферіха. Таким чином, до того, як велика теорема Ферма була доведена Ендрю Вайлсом, пошук простих Фібоначчі — Віферіха переслідував мету знайти потенційний контрприклад.

PrimeGrid шукає майже прості за умовою |A| < = 1000.

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

Підпроєкти 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. Primorial Prime Search
    • server=PRS:0:1:prpnet.primegrid.com:12008
  5. Wieferich Prime Search (ПРИЗУПИНЕНО)
    • server=WIEFERICH:0:2:prpnet.primegrid.com:13000
  6. 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                                    
321 Sieve                                    
AP                                    
Cullen LLR                                    
CW Sieve                                    
ESP LLR                                    
GCW LLR
GCW Sieve
GFN                                    
PSP LLR                                    
PSP Sieve                                    
PSA                                    
PPS LLR                                    
PPS Sieve                                    
SOB LLR                                    
SGS LLR                                    
SR5 LLR                                    
TRP LLR                                    
TRP Sieve                                    
TPS LLR                                    
Woodall LLR                                    
WW

До квітня 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 [Архівовано 9 листопада 2013 у Wayback Machine.]

Джерела ред.