stringtranslate.com

Наибольшее известное простое число

Наибольшее известное простое число — 2 82 589 933 − 1 , число, которое имеет 24 862 048 цифр при записи в десятичной системе счисления . Оно было найдено с помощью компьютера, добровольно предоставленного Патриком Ларошем из Great Internet Mersenne Prime Search (GIMPS) в 2018 году. [1]

График 2020 года количества цифр в самом большом известном простом числе по годам с момента изобретения электронного компьютера. Вертикальная шкала логарифмическая .

Простое число — это натуральное число, большее 1, не имеющее делителей , кроме 1 и самого себя. Согласно теореме Евклида существует бесконечно много простых чисел, поэтому наибольшего простого числа не существует.

Многие из самых больших известных простых чисел являются простыми числами Мерсенна , числами, которые на единицу меньше степени двойки, поскольку они могут использовать специализированный тест на простоту, который быстрее общего. По состоянию на июнь 2023 года шесть самых больших известных простых чисел являются простыми числами Мерсенна. [2] Последние семнадцать рекордных простых чисел были простыми числами Мерсенна. [3] [4] Двоичное представление любого простого числа Мерсенна состоит из всех единиц, поскольку двоичная форма 2 k − 1 — это просто k единиц. [5]

Широко распространено мнение , что нахождение больших простых чисел позволяет обеспечить более надежное шифрование , однако это неверно. [6] [7]

Текущая запись

Рекорд в настоящее время принадлежит числу 2 82 589 933 − 1 с 24 862 048 цифрами, найденному GIMPS в декабре 2018 года. [1] Первые и последние 120 цифр его значения показаны ниже:

148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ...

(пропущено 24 861 808 цифр)

... 062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591 [ 8]

По состоянию на сентябрь 2024 года это простое число удерживало рекорд более 6 лет, дольше, чем любое другое простое число со времен M 19937 (которое удерживало рекорд 7 лет с 1971 по 1978 год).

Призы

Фонд Electronic Frontier Foundation (EFF) предлагает несколько призов за рекордные простые числа. [9] В 1999 году было найдено простое число из миллиона цифр, первооткрыватель которого получил приз в размере 50 000 долларов США. [10] В 2008 году простое число из десяти миллионов цифр получило приз в размере 100 000 долларов США и премию Cooperative Computing Award от EFF. [9] Журнал Time назвал это простое число 29-м главным изобретением 2008 года. [11]

Оба эти простых числа были обнаружены в рамках Великого интернет-поиска простых чисел Мерсенна (GIMPS), который координирует долгосрочные поисковые усилия среди десятков тысяч компьютеров и тысяч добровольцев. Приз в размере 50 000 долларов достался первооткрывателю, а приз в размере 100 000 долларов достался GIMPS. GIMPS разделит приз в размере 150 000 долларов США за первое простое число, состоящее из более чем 100 миллионов цифр, с победившим участником. Еще один приз в размере 250 000 долларов США предлагается за первое простое число, состоящее не менее чем из миллиарда цифр. [9]

GIMPS также предлагает премию в размере 3000 долларов США за научное открытие для участников, которые откроют новое простое число Мерсенна длиной менее 100 миллионов знаков. [12]

История крупнейших известных простых чисел

Памятный почтовый штемпель, использованный математическим факультетом UIUC после доказательства того, что M 11213 является простым числом

В следующей таблице перечислены прогрессии наибольшего известного простого числа в порядке возрастания. [3] Здесь M p = 2 p − 1 — число Мерсенна с показателем  p , где p — простое число. Самый длинный известный рекордсмен — M 19 = 524 287 , который был наибольшим известным простым числом в течение 144 лет. До 1456 года не известно никаких записей.

GIMPS обнаружил пятнадцать последних записей (все они являются простыми числами Мерсенна) на обычных компьютерах, используемых участниками по всему миру.

Двадцать крупнейших известных простых чисел

Список из 5000 крупнейших известных простых чисел поддерживается PrimePages [ 18] , из которых двадцать крупнейших перечислены ниже. [19]

Смотрите также

Ссылки

  1. ^ abc "Проект GIMPS обнаружил самое большое известное простое число: 282,589,933-1". Mersenne Research, Inc. 21 декабря 2018 г. Получено 21 декабря 2018 г.
  2. ^ "Самые большие известные простые числа – Вывод поиска в базе данных". Prime Pages . Получено 19 марта 2023 г. .
  3. ^ ab Caldwell, Chris. "The Largest Known Prime by Year: A Brief History". Prime Pages . Получено 19 марта 2023 г.
  4. ↑ Последнее немерсенновское наибольшее известное простое число было 391 581 ⋅ 2216 193 − 1; см. также «Наибольшее известное простое число по годам: краткая история», первоначально написанная Колдуэллом.
  5. ^ "Perfect Numbers". Университет штата Пенсильвания . Получено 6 октября 2019 г. Интересное примечание касается двоичных представлений этих чисел...
  6. ^ Маккиннон, Мика (4 января 2018 г.). «Это самое большое известное простое число». Смитсоновский институт . Получено 6 июля 2024 г.
  7. ^ Джонстон, Натаниэль (11 сентября 2009 г.). «Нет, простые числа с миллионами цифр бесполезны для криптографии». njohnston.ca . Получено 6 июля 2024 г.
  8. ^ «Открыто 51-е известное простое число Мерсенна».
  9. ^ abc "Рекордное простое число из 12 миллионов цифр принесло приз в размере 100 000 долларов". Electronic Frontier Foundation . Electronic Frontier Foundation . 14 октября 2009 г. Получено 26 ноября 2011 г.
  10. ^ Electronic Frontier Foundation, Big Prime Nets Big Prize.
  11. ^ "Лучшие изобретения 2008 года - 29. 46-е простое число Мерсенна". Time . Time Inc . 29 октября 2008 г. Архивировано из оригинала 2 ноября 2008 г. Получено 17 января 2012 г.
  12. ^ "GIMPS by Mersenne Research, Inc". mersenne.org . Получено 21 ноября 2022 г. .
  13. ^ Эдвард Сэндифер, К. (19 ноября 2014 г.). Как Эйлер сделал даже больше. Математическая ассоциация Америки. ISBN 9780883855843.
  14. ^ Миллер, JCP (1951). "Большие простые числа". Nature . 168 (4280): 838. Bibcode : 1951Natur.168..838M. doi : 10.1038/168838b0.
  15. ^ abcdefghi Лэндон Курт Нолл , Большое простое число, найденное суперкомпьютером SGI/Cray.
  16. ^ Браун, Джон; Нолл, Лэндон Курт; Паради, Б.К.; Смит, Джоэл Ф.; Зарантонелло, Серджио Э.; Смит, Джин Уорд; Робинсон, Рафаэль М.; Эндрюс, Джордж Э. (1990). «Письма в редакцию». The American Mathematical Monthly . 97 (3): 214–215. doi :10.1080/00029890.1990.11995576. JSTOR  2324686.
  17. ^ Код проверки: Z, The Prime Pages .
  18. ^ "База данных простых чисел: Домашняя страница списка крупнейших известных простых чисел". t5k.org/primes . Получено 19 марта 2023 г. .
  19. ^ "The Top Twenty: Largest Known Simples" . Получено 19 марта 2023 г. .
  20. ^ "Проект GIMPS обнаружил самое большое известное простое число: 277,232,917-1". mersenne.org . Великий интернет-поиск простых чисел Мерсенна . Получено 3 января 2018 г. .
  21. ^ "Проект GIMPS обнаружил самое большое известное простое число: 274,207,281-1". mersenne.org . Великий интернет-поиск простых чисел Мерсенна . Получено 29 сентября 2017 г. .
  22. ^ "GIMPS обнаруживает 48-е простое число Мерсенна, 257,885,161-1 теперь является самым большим известным простым числом". mersenne.org . Great Internet Mersenne Prime Search . 5 февраля 2013 г. . Получено 29 сентября 2017 г. .
  23. ^ ab "GIMPS открывает 45-е и 46-е простые числа Мерсенна, 243,112,609-1 теперь является крупнейшим известным простым числом". mersenne.org . Great Internet Mersenne Prime Search . 15 сентября 2008 г. . Получено 29 сентября 2017 г. .
  24. ^ "GIMPS обнаруживает 47-е простое число Мерсенна, 242,643,801-1 — новейшее, но не самое большое известное простое число Мерсенна". mersenne.org . Great Internet Mersenne Prime Search . 12 апреля 2009 г. . Получено 29 сентября 2017 г. .
  25. ^ "PrimePage Простые числа: Phi(3, - 516693^1048576)". t5k.org .
  26. ^ "PrimePage Простые числа: Phi(3, - 465859^1048576)". t5k.org .
  27. ^ "GIMPS обнаруживает 44-е простое число Мерсенна, 232,582,657-1 теперь является самым большим известным простым числом". mersenne.org . Great Internet Mersenne Prime Search . 11 сентября 2006 г. . Получено 29 сентября 2017 г. .
  28. ^ "PrimeGrid's Seventeen or Bust Subproject" (PDF) . primegrid.com . PrimeGrid . Получено 30 сентября 2017 г. .
  29. ^ "GIMPS обнаруживает 43-е простое число Мерсенна, 230,402,457-1 теперь является самым большим известным простым числом". mersenne.org . Great Internet Mersenne Prime Search . 24 декабря 2005 г. . Получено 29 сентября 2017 г. .
  30. ^ "4 × 511786358 + 1". t5k.org . PrimePages . 1 октября 2024 г. . Получено 5 октября 2024 г. .
  31. ^ "GIMPS обнаруживает 42-е простое число Мерсенна, 225,964,951-1 теперь является самым большим известным простым числом". mersenne.org . Great Internet Mersenne Prime Search . 27 февраля 2005 г. . Получено 29 сентября 2017 г. .
  32. ^ "69 × 224612729 − 1". t5k.org . PrimePages . 13 августа 2024 . Получено 29 августа 2024 .
  33. ^ "GIMPS обнаруживает 41-е простое число Мерсенна, 224,036,583-1 теперь является самым большим известным простым числом". mersenne.org . Great Internet Mersenne Prime Search . 28 мая 2004 г. . Получено 29 сентября 2017 г. .
  34. ^ "107347 × 223427517 − 1". t5k.org . PrimePages . 4 августа 2024 . Получено 25 августа 2024 .
  35. ^ «321 Prime Search от PrimeGrid» (PDF) . primegrid.com .{{cite web}}: CS1 maint: url-status ( ссылка )
  36. ^ "Обобщенный поиск простых чисел Ферма в PrimeGrid" (PDF) . primegrid.com . PrimeGrid . Получено 7 октября 2022 г. .
  37. ^ "Обобщенный поиск простых чисел Ферма в PrimeGrid" (PDF) . primegrid.com . PrimeGrid . Получено 17 сентября 2022 г. .

Внешние ссылки