PrimeGrid

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

PrimeGrid — проект добровольных распределенных вычислений на платформе BOINC, целью которого является поиск различных простых чисел специального вида. Проект стартовал 12 июня 2005 года. По состоянию на 25 марта 2012 года в нём приняли участие более 49 000 пользователей (156 565 компьютеров) из 188 стран, в совокупности обеспечивая производительность 3,3 петафлопс[1].

Список подпроектов[править | править вики-текст]

В проекте производится поиск простых чисел специального вида следующих типов:

Поиск простых чисел Каллена, Вудалла, Прота и обобщенных простых чисел Ферма эффективно реализуется с использованием вычислительных возможностей современных видеокарт Nvidia (технология CUDA).

Часть вычислительных мощностей проекта используется для решения открытых математических проблем:

  • проблемы Ризеля: поиск такого минимального нечётного k, что число k \cdot 2^n - 1 является составным для всех натуральных n;
  • проблемы Серпинского: поиск такого минимального нечетного натурального k, что число k \cdot 2^n + 1 является составным для всех натуральных n (совместно с проектом Seventeen or Bust);
  • проблемы Серпинского — Ризеля по основанию 5: поиск такого минимального нечётного k, что число k \cdot 5^n - 1 является составным для всех натуральных n.

В 2010 году была успешно найдена арифметическая прогрессия из 26 простых чисел (подпроект AP26).

Для тестов простоты используются алгоритмы Люка-Лемера-Ризеля (англ.) и решета (англ.).

История проекта[править | править вики-текст]

3 июля 2007 года добавлен подпроект, направленный на поиск простых чисел Каллена/Вудалла[2]. Уже 8 августа 2007 года было открыто первое новое простое число Вудалла 2013992×22013992−1, содержащее 606 279 цифр[3].

13 октября 2007 года добавлен подпроект, целью которого является решение проблемы Серпинского[4].

5 декабря 2007 года добавлен подпроект для поиска чисел вида 3 \cdot 2^n - 1 с использованием программного обеспечения LLR[5].

29 июня 2008 года подпроект по поиску чисел вида 3 \cdot 2^n - 1, проверивший диапазон значений n < 5·106, переключен на поиск чисел вида 3 \cdot 2^n + 1[6].

26 декабря 2008 года добавлен подпроект, направленный на поиск праймориальных простых чисел[7].

27 декабря 2008 года добавлен подпроект AP26, целью которого является поиск арифметической прогрессии из 26 простых чисел[8].

16 августа 2009 года добавлен подпроект, направленный на поиск простых чисел Софи Жермен[9].

10 ноября 2009 года добавлен подпроект по поиску обобщенных чисел Ферма[10].

10 декабря 2009 года для подпроекта AP26 добавлен расчетный клиент с поддержкой технологии CUDA[11].

31 января 2010 года начато сотрудничество с проектом Seventeen or Bust, направленное на решение проблемы Серпинского[12].

1 декабря 2010 года анонсирован новый расчетный модуль для поиска простых чисел Прота методом решета с поддержкой технологий CUDA и OpenCL[13].

7 января 2011 года добавлен подпроект для решения проблемы Серпинского/Ризеля по основанию 5[14].

9 января 2012 года в модуле LLR реализована поддержка векторных расширений системы команд процессора AVX, что обеспечивает 20—50 % прибавку в производительности в зависимости от приложения[15].

4 февраля 2012 года реализован расчетный модуль genefer для поиска обобщенных чисел Ферма с поддержкой технологии CUDA[16].

Достижения[править | править вики-текст]

В результаты выполняемых расчетов был открыт ряд простых чисел специального вида и арифметических прогрессий из простых чисел.

2007 год[править | править вики-текст]

  • Числа Вудалла:
    • 3752948×23752948−1 (1 129 757 цифр) — самое большое известное простое число Вудалла;
    • 2367906×22367906−1 (712 818 цифр);
    • 2013992×22013992−1 (606 279 цифр).

2008 год[править | править вики-текст]

  • 321-числа:
    • 3×24235414−1 (1 274 988 цифр).
  • Числа Прота:
    • 258317×25450519+1 (1 640 776 цифр);
    • 265711×24858008+1 (1 462 412 цифры);
    • 651×2476632+1 (143 484 цифры);
    • 825×2373331+1 (112 387 цифр).

2009 год[править | править вики-текст]

  • Арифметические прогрессии из 25 простых чисел (0 \le n \le 24):
    • 12353443596260323+23793841×23#×n;
    • 46176957093163301+1109121×23#×n;
    • 18162964758258289+3755664×23#×n;
    • 20919497549238289+3155495×23#×n;
    • 2960886048458003+2346233×23#×n.
  • Арифметические прогрессии из 24 простых чисел (0 \le n \le 23):
    • 4891686128805269+19453568×23#×n;
    • 4687877159107031+18203167×23#×n;
    • 1948053460212667+17745794×23#×n;
    • 3634080452156039+16981607×23#×n;
    • 10307159737232191+14120563×23#×n;
    • 13678065943093049+13223804×23#×n;
    • 10317962076055027+10241601×23#×n;
    • 7979661543967237+9936237×23#×n;
    • 39421708111691+9740894×23#×n;
    • 5531900872160491+9383796×23#×n;
    • 13432401425380607+9219580×23#×n;
    • 14992521666441877+8832442×23#×n;
    • 167806194923077+4935146×23#×n;
    • 6274259724784693+2522655×23#×n;
    • 7960592659339799+2326495×23#×n;
    • 6872932294461509+2042703×23#×n;
    • 20187352211709911+1799216×23#×n;
    • 2725131905640097+1342336×23#×n;
    • 25545151920212759+1140241×23#×n;
    • 13785500104035967+1004314×23#×n;
    • 19471368812966089+410682×23#×n;
    • 19516186145019209+313705×23#×n;
    • 20909681071069667+234797×23#×n.
  • 321-числа:
    • 3×25082306+1 (1 529 928 цифр).
  • Числа Каллена:
    • 6679881×26679881+1 (2 010 852 цифры) — самое большое известное простое число Каллена;
    • 6328548×26328548+1 (1 905 090 цифр).
  • Числа Прота:
    • 27×22218064+1 (667 706 цифр);
    • 659×2617815+1 (185 984 цифры);
    • 519×2567235+1 (170 758 цифр);
    • 15×2483098+1 (145 429 цифр).
  • Обобщенные простые числа Вудалла:
    • 563528×13563528−1 (627 745 цифр).
  • Предположительно простые числа:
    • 24583176+2131 (1 379 674 цифры).
  • Другие:
    • 27×21902689−1 (572 768 цифр).

2010 год[править | править вики-текст]

  • Арифметическая прогрессия из 26 простых чисел (0 \le n \le 25):
    • 43142746595714191+23681770×23#×n.
  • Арифметические прогрессии из 25 простых чисел (0 \le n \le 24):
    • 18626565939034793+30821486×23#×n;
    • 25300381597038677+28603610×23#×n;
    • 42592855872841649+19093314×23#×n;
    • 24715375237181843+19071018×23#×n;
    • 46428033558097831+12893265×23#×n;
    • 58555890166091939+10416756×23#×n;
    • 49644063847333931+7851809×23#×n.
  • 321-числа:
    • 3×26090515−1 (1 833 429 цифр).
  • Числа Прота:
    • 90527×29162167+1 (2 758 093 цифры).
  • Факториальные простые числа:
    • 103040!−1 (471 794 цифры);
    • 94550!−1 (429 390 цифр).
  • Праймориальные простые числа:
    • 843301#−1 (365 851 цифра) — самое большое известное праймориальное простое число на момент открытия;
    • 392113#+1 (169 966 цифр).
  • Проблема Серпинского — Ризеля по основанию 5:
    • 151026×5559670−1 (391 198 цифр);
    • 3938×5558032−1 (390 052 цифры);
    • 105782×5551766−1 (385 673 цифры);
    • 183916×5519597−1 (363 188 цифр);
    • 53542×5515155−1 (360 083 цифры).
  • Проблема Ризеля: найдено простое число 191249×23417696−1 (1 028 835 цифр), основание 191249 исключено из рассмотрения.

2011 год[править | править вики-текст]

  • Простые Софи Жермен:
    • 3756801695685×2666669±1 (200 700 цифр) — самая большая известная пара простых-близнецов.
  • Обобщенные простые числа Ферма:
    • 75898524288+1 (2 558 647 цифр);
    • 361658262144+1 (1 457 075 цифр);
    • 145310262144+1 (1 353 265 цифр);
    • 40734262144+1 (1 208 473 цифр).
  • Числа Прота:
    • 9×22543551+1 (765 687 цифр);
    • 25×22141884+1 (644 773 цифры);
    • 4479×2226618+1 (68 223 цифры);
    • 3771×2221676+1 (66 736 цифр);
    • 7333×2138560+1 (41 716 цифр).
  • Факториальные простые числа:
    • 110059!-1 (507 082 цифр).
  • 321-числа:
    • 3×27033641+1 (2 117 338 цифр).
  • Обобщенные числа Вудалла:
    • 404882×43404882-1 (661 368 цифр).
  • Проблема Ризеля: в результате нахождения простых чисел
    • 353159×24331116-1 (1 303 802 цифр),
    • 141941×24299438-1 (1 294 265 цифр),
    • 123547×23804809-1 (1 145 367 цифр),
    • 415267×23771929-1 (1 135 470 цифр),
    • 65531×23629342-1 (1 092 546 цифр),
    • 428639×23506452-1 (1 055 553 цифры)

исключены из рассмотрения основания 428639, 415267, 353159, 141941, 123547, 65531. Непроверенными на тот момент оставались ещё 57 оснований.

2012 год[править | править вики-текст]

  • Числа Прота:
    • 7×25775996+1 (1 738 749 цифр)[17];
    • 9×23497442+1 (1 052 836 цифр)[18];
    • 81×23352924+1 (1 009 333 цифры)[19];
    • 131×21494099+1 (449 771 цифра)[20];
    • 329×21246017+1 (375 092 цифры)[21];
    • 1705×2906110+1 (272 770 цифр)[22];
    • 7905×2352281+1 (106 052 цифры)[23].
  • Обобщенные простые числа Ферма:
    • 475856524288+1 (2 976 633 цифры) — самое большое известное обобщенное простое число Ферма[24];
    • 341112524288+1 (2 900 832 цифры)[25];
    • 773620262144+1 (1 543 643 цифры)[26]
    • 676754262144+1 (1 528 413 цифр)[27]
    • 525094262144+1 (1 499 526 цифр)[28].
  • Обобщенные простые числа Каллена:
    • 427194×113427194+1 (877 069 цифр) — самое большое известное обобщенное простое число Каллена[29].
  • Праймориальные простые числа:
    • 1098133#−1 (476 311 цифр) — самое большое праймориальное простое число среди известных[30].
  • Проблема Ризеля: в результате нахождения простых чисел
    • 252191×25497878−1 (1 655 032 цифры)[31]
    • 162941×2993718−1 (299 145 цифр)[32]

исключены из рассмотрения основания 162941 и 252191. Непроверенными остаются ещё 55 оснований.

  • Проблема Серпинского: в результате нахождения простых чисел
    • 147559×22562218+1 (771 310 цифр),
    • 123287×22538167+1 (764 070 цифр)

исключены из рассмотрения основания 123287 и 147559. Непроверенными остаются ещё 15 оснований[33].

  • Простые Софи Жермен:
    • 18543637900515×2666667−1 (200 701 цифра) — самое большое известное простое Софи Жермен[34].
  • Другие:
    • 27×23855094−1 (1 160 501 цифра)[35].

2013 год[править | править вики-текст]

  • Числа Прота:
    • 57×22747499+1 (827 082 цифры)[36]
    • 183×21747660+1 (526 101 цифра)[37]
    • 2145×21099064+1 (330 855 цифр)[38]
  • Проблема Ризеля: в результате нахождения простых чисел
    • 40597×26808509–1 (2 049 571 цифра)[39] — самое большое известное число Ризеля;
    • 304207×26643565−1 (1 999 918 цифр)[40]
    • 398023×26418059−1 (1 932 034 цифры)[41]

исключены из рассмотрения основания 40597, 304207 и 398023. Непроверенными остаются ещё 52 основания.

  • Факториальные простые числа:
    • 147855!−1 (700 177 цифр)[42]
  • Проблема Серпинского — Ризеля по основанию 5:
    • 37292×51487989+1 (1 040 065 цифр)[43]
    • 173198×51457792−1 (1 018 959 цифр)[44]

2014 год[править | править вики-текст]

  • Проблема Серпинского — Ризеля по основанию 5:
    • 138172×51714207−1 (1 198 185 цифр)[45];
    • 22478×51675150−1 (1 170 884 цифры)[46];
    • 326834×51634978−1 (1 142 807 цифр)[47];
    • 207394×51612573−1 (1 127 146 цифр)[48];
    • 104944×51610735−1 (1 125 861 цифра)[49];
    • 330286×51584399−1 (1 107 453 цифры)[50];
    • 22934×51536762−1 (1 074 155 цифр)[51];
    • 178658×51525224−1 (1 066 092 цифры)[52];
    • 59912×51500861+1 (1 049 062 цифр)[53].
  • 321-числа:
    • 3×210829346+1 (3 259 959 цифр)[54] — самое большое известное 321-число.
  • Числа Прота:
    • 35×23587843+1 (1 080 050 цифр)[55];
    • 35×23570777+1 (1 074 913 цифр)[56];
    • 33×23570132+1 (1 074 719 цифр)[57];
    • 93×23544744+1 (1 067 077 цифр)[58];
    • 87×23496188+1 (1 052 460 цифр)[59];
    • 51×23490971+1 (1 050 889 цифр)[60].

Примечания[править | править вики-текст]

  1. Boinc all Project Stats
  2. New subproject added
  3. Biggest ever Woodall prime discovered!
  4. Prime Sierpinski Project sieve available
  5. New subproject available
  6. 3*2^n-1 switched to +1
  7. Primorial Prime Search
  8. AP26 Search
  9. Sophie Germain Prime Search
  10. Generalized Fermat Prime Search
  11. AP26 CUDA Application Released
  12. Seventeen or Bust
  13. Official release of tpsieve for PPS (Sieve)
  14. Sierpinski/Riesel Base 5 Project
  15. AVX build of llr
  16. Generalized Fermat Prime Search
  17. PPS Mega Prime!
  18. PPS Mega Prime!
  19. Mega Prime Found
  20. Prime Fermat Divisor Found
  21. Prime Fermat Divisor Found
  22. Prime Fermat Divisor Found
  23. Prime Fermat Divisor Found
  24. World Record GFN Prime!
  25. World Record GFN Prime!
  26. Generalized Fermat Mega Prime
  27. Generalized Fermat Mega Prime
  28. Generalized Fermat Mega Prime
  29. World Record Generalized Cullen Prime
  30. World Record Primorial prime
  31. World Record TRP Prime!
  32. Prime found for the Riesel Problem
  33. March was a great month for the Extended Sierpinski Problem project
  34. World Record Sophie Germain prime found!
  35. 27 Mega Prime
  36. PPS Mega Prime!
  37. Fermat Divisor!
  38. Fermat Divisor!
  39. New TRP Mega Prime Found!
  40. Another Record TRP Prime!!
  41. World Record TRP Prime!
  42. Factorial Prime Found!
  43. New SR5 Mega Prime Found!
  44. First base 5 mega prime found!
  45. http://www.primegrid.com/forum_thread.php?id=5809
  46. http://www.primegrid.com/forum_thread.php?id=5808
  47. Yet another SR5 prime discovered!
  48. http://www.primegrid.com/download/SR5-207394.pdf
  49. New SR5 Mega Prime Found!!
  50. World record SR5 prime discovered!
  51. Deja Vu: World Record SR5 Discovery
  52. Another Record SR5 Prime!
  53. New SR5 Mega Prime Found!
  54. World Record 321 Mega Prime Found!
  55. http://www.primegrid.com/forum_thread.php?id=5810
  56. http://www.primegrid.com/forum_thread.php?id=5796
  57. http://www.primegrid.com/forum_thread.php?id=5794
  58. New MEGA prime found!
  59. MEGA Prime Found
  60. Another MEGA Prime Found

Ссылки[править | править вики-текст]

Обсуждение проекта в форумах:

См. также[править | править вики-текст]