Просмотр кода страницы Простое число

[[Файл:Prime Factorization of 42 (Second Example).png|мини|Разложение числа 42 на простые множители: <math>42=2\times 3 \times7</math>]]
'''Просто́е число́''' — [[Натуральное число|натуральное]] (целое положительное) число, имеющее ровно два различных натуральных [[Делимость|делителя]] — {{num1|1|единицу}} и самого себя<ref name=":6">{{книга |часть=Простое число |заглавие=Математическая энциклопедия (в 5 томах) |место=М. |ref=Математическая энциклопедия !! |том=4 |год=1977 |ссылка=http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t4.djvu |издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]] }}</ref>. Другими словами, число <math>x</math> является простым, если оно больше <math>1</math> и при этом делится без остатка только на <math>1</math> и на <math>x</math>. К примеру, <math>5</math> — простое число, а <math>6</math> является составным числом, так как, помимо <math>1</math> и <math>6</math>, также делится на <math>2</math> и на <math>3</math>.

[[Основная теорема арифметики]] устанавливает центральную роль простых чисел в [[теория чисел|теории чисел]]: любое [[целое число]], большее <math>1</math>, либо является простым, либо может быть выражено как произведение простых чисел, причём это выражение единственно с точностью до порядка сомножителей. Именно чтобы обеспечить единственность в этой теореме, единица не считается простым числом (иначе можно включать произвольно много единиц в любое разложение<ref name=":7" />, например, <math>3 = 1 \cdot 3 = 1\cdot 1\cdot 3</math> и так далее.

Натуральные числа, которые больше единицы и не являются простыми, называются [[составное число|составными]]. Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один натуральный делитель), простые числа (имеющие два натуральных делителя) и составные числа (имеющие больше двух натуральных делителей)<ref name=":6" />. Изучением свойств простых чисел занимается [[теория чисел]]. Как простых, так и составных чисел бесконечно много.

Последовательность простых чисел начинается так:
: <!-- число 1 не является простым ! -->[[2 (число)|2]], [[3 (число)|3]], [[5 (число)|5]], [[7 (число)|7]], [[11 (число)|11]], [[13 (число)|13]], [[17 (число)|17]], [[19 (число)|19]], [[23 (число)|23]], [[29 (число)|29]], [[31 (число)|31]], [[37 (число)|37]], [[41 (число)|41]], [[43 (число)|43]], [[47 (число)|47]], [[53 (число)|53]], [[59 (число)|59]], [[61 (число)|61]], [[67 (число)|67]], [[71 (число)|71]], [[73 (число)|73]], [[79 (число)|79]], [[83 (число)|83]], [[89 (число)|89]], [[97 (число)|97]], [[101 (число)|101]], [[103 (число)|103]], [[107 (число)|107]], [[109 (число)|109]], [[113 (число)|113]], [[127 (число)|127]], [[131 (число)|131]], [[137 (число)|137]], [[139 (число)|139]], [[149 (число)|149]], [[151 (число)|151]], [[157 (число)|157]], [[163 (число)|163]], [[167 (число)|167]], [[173 (число)|173]], [[179 (число)|179]], [[181 (число)|181]], [[191 (число)|191]], [[193 (число)|193]], [[197 (число)|197]], [[199 (число)|199]]…<ref>{{OEIS long|A000040}}, смотри также [[список простых чисел]]</ref>

Свойство числа быть простым называется простотой. Простой, но медленный метод проверки простоты заданного числа n известен как [[перебор делителей]]; более эффективные алгоритмы описаны [[#Тест простоты|ниже]].

Многие проблемы, касающиеся простых чисел, остаются открытыми, смотри [[#Открытые вопросы|ниже]].

Простые числа широко используются в математике и в смежных науках — например, во многих алгоритмах [[Информационные технологии|информационных технологий]], таких как [[криптосистема с открытым ключом]], которая использует такие свойства, как сложность [[Факторизация целых чисел|разложения]] чисел на [[простой множитель|простые множители]]<ref>{{книга |автор=[[Гарднер, Мартин]] |часть=<!-- уточнить --> |заглавие=От мозаик Пенроуза к надёжным шифрам |оригинал=Penrose Tiles to Trapdoor Ciphers |ответственный=пер. с англ. Ю. А. Данилова |место=М. |издательство=[[Мир (издательство)|]] |год=1993 |страницы=<!-- уточнить --> |страниц=416 |isbn=5-03-001991-X |тираж=10000 |ref=Гарднер}}</ref>.

Существуют обобщения понятия простого числа для произвольных [[Кольцо (математика)|колец]] и других алгебраических структур, смотри [[#Вариации и обобщения|ниже]].

== История ==
Неизвестно, когда было определено понятие простого числа, однако первые свидетельства понимания таких чисел относятся к верхнему палеолиту, что подтверждается [[Кость Ишанго|костью Ишанго]]<ref>{{ref-fr}} ''[http://www.reunion.iufm.fr/recherche/irem/IMG/pdf/Keller_prehistoire_geometrie.pdf Préhistoire de la géométrie : le problème des sources (PDF)]{{Недоступная ссылка|date=Март 2018 |bot=InternetArchiveBot }}''. Site de l’IREM de La Réunion. Voir aussi [http://bibnum.education.fr/math%C3%A9matiques/alg%C3%A9bre/l%E2%80%99os-d%E2%80%99ishango « Les fables d’Ishango, ou l’irrésistible tentation de la mathématique-fiction»], analyse par O. Keller sur Bibnum</ref>.

В сохранившихся записях [[Математика в Древнем Египте|древних египтян]] есть намёки на то, что у них были некоторые сведения о простых числах: например, [[Папирус Ахмеса|папирус Райнда]] относящийся ко II тысячелетию до н. э. содержит в себе таблицу, выражающую дроби вида 2/n через сумму двух, трёх или четырёх [[Египетские дроби|дробей]] с числителями, равными единице, и различными знаменателями. Разложения дробей, знаменатели которых имеют общий делитель, похожи, что свидетельствует о том, что египтяне по крайней мере знали разницу между простым числом и составным<ref>{{Статья|автор=|заглавие=Egyptian Unit Fractions|ссылка=http://mathpages.com/home/kmath340/kmath340.htm издание=Mathpages |страницы=|issn=}}</ref>.

[[Файл:P. Oxy. I 29.jpg|слева|мини|Фрагмент «Начал» Евклида, обнаруженный в [[Оксиринх]]е]]
Однако самые ранние сохранившиеся исследования простых чисел исходят от [[Математика в Древней Греции|древних греков]]. [[Начала (Евклид)|Начала]] [[Евклид]]а (около 300 г. до н. э.) содержат важные теоремы о простых числах, включая бесконечность простых чисел, [[Лемма Евклида|лемму Евклида]] и [[Основная теорема арифметики|основную теорему арифметики]]<ref name=":8">{{Статья|автор=Рыбников К. |заглавие=Русские издания «Начал» Евклида. |ссылка=http://www.mathnet.ru/links/c2d03cc30a7e6f4b3c40bd7a0d6175ca/rm8809.pdf |издание=[[Успехи математических наук]] |год=1941 |номер=9 |страницы=318—321 |issn= |язык=ru |издательство=[[Математический институт имени В. А. Стеклова РАН|Российская академия наук]] }}</ref>. В древней Греции также было придумано [[решето Эратосфена]], простой алгоритм нахождения всех простых чисел от 1 до n.

[[Файл:Pierre de Fermat.jpg|мини|[[Пьер Ферма]]]]
После греков мало что произошло в изучении простых чисел до XVII века<ref>{{Cite web|url=http://www.mathnet.ru/links/c2d03cc30a7e6f4b3c40bd7a0d6175ca/rm8809.pdf|title=Prime numbers|author=John J. O'Connor, Edmund F. Robertson|website=MacTutor|date=|publisher=|lang=en}}</ref>. В 1640 году [[Ферма, Пьер|Пьер де Ферма]] сформулировал (без доказательства) [[Малая теорема Ферма|малую теорему Ферма]] (позже доказанную [[Лейбниц, Готфрид Вильгельм|Лейбницем]] и [[Эйлер, Леонард|Эйлером]]) и [[Теорема Ферма — Эйлера|теорему о сумме двух квадратов]]. Ферма также высказал предположение, что все числа вида <math>2^{2^n}</math>+ 1 — простые (они были названы [[Числа Ферма|числами Ферма]]) и доказал это до n = 4 (или <math>2^{16}</math>+ 1). Однако Эйлер показал, что уже следующее число Ферма при n = 5 (или <math>2^{32}</math> + 1) является составным (делится на число 641). На сегодняшний день нет других известных чисел Ферма, являющихся простыми. В то же время французский монах [[Мерсенн, Марен|Марен Мерсенн]] обратил внимание на простые числа вида 2<sup>p</sup> — 1, где ''p'' — простое (не все числа такого вида являются простыми)<ref>{{Cite web|url=http://www.mersenne.org/primes/|title=List of Known Mersenne Prime Numbers|author=|website=Great Internet Mersenne Prime Search|date=|publisher=|accessdate=}}</ref>. Их назвали [[Числа Мерсенна|простыми числами Мерсенна]] в его честь.

Работа Эйлера в теории чисел включала в себя множество сведений о простых числах. Он показал что бесконечный [[Числовой ряд|ряд]] 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … является расходящимся. Также в 1747 году он показал, что чётные [[Совершенное число|совершенные числа]] — это целые числа вида <math>2^{p-1}(2^p -1)</math>, где второй множитель является простым Мерсенна. В переписке Эйлера с [[Гольдбах, Христиан|Христианом Гольдбахом]] последний сформулировал знаменитую [[Проблема Гольдбаха|гипотезу Гольдбаха]] о представлении любого чётного числа, начиная с 4, в виде суммы двух простых, которая до сих пор не доказана<ref name=":2">{{Книга|автор=Apostol, Tom M.|заглавие=Introduction to analytic number theory|ссылка=https://www.worldcat.org/oclc/1859863|место=New York|издательство=Springer-Verlag|год=1976|страниц=xii, 338 pages|isbn=0387901639}}</ref>.

С начала [[XIX век|XIX века]] внимание многих математиков обратилось к изучению [[«O» большое и «o» малое|асимптотического]] распределения простых чисел<ref name=":2" />. [[Лежандр, Адриен Мари|Лежандр]] и [[Гаусс, Карл Фридрих|Гаусс]] независимо друг от друга высказали предположение, что плотность простых чисел в среднем близка к величине, обратно пропорциональной [[Натуральный логарифм|натуральному логарифму]]<ref name=":3">{{Книга|автор=Du Sautoy, Marcus.|заглавие=L'enigma dei numeri primi|ссылка=https://www.worldcat.org/oclc/799339321|место=Milano|издательство=Rizzoli|год=2005|страниц=606 p.|isbn=8817008435}}</ref>.

Долгое время считалось, что простые числа имеют ограниченное применение за пределами [[Чистая математика|чистой математики]]. Ситуация изменилась в 1970-е годы, когда появились концепции [[Криптосистема с открытым ключом|криптографии с открытым ключом]], в них простые числа составляли основу первых алгоритмов, таких как алгоритм шифрования [[RSA]]<ref name=":4">{{Книга|автор=Menezes, A. J. (Alfred J.), 1965-|заглавие=Handbook of applied cryptography|ссылка=https://www.worldcat.org/oclc/35292671|место=Boca Raton|издательство=CRC Press|год=1997|страниц=xxviii, 780 pages|isbn=9780849385230}}</ref>.

== Разложение натуральных чисел в произведение простых ==
{{main|Факторизация целых чисел}}
Представление натурального числа в виде произведения простых называется ''разложением на простые'' или [[Факторизация целых чисел|''факторизацией'' числа]]. На настоящий момент неизвестны [[полиномиальный алгоритм|полиномиальные алгоритмы]] факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой [[вычислительная сложность|вычислительной сложности]] задачи факторизации базируется криптосистема [[RSA]] и некоторые другие. Факторизация с полиномиальной сложностью теоретически возможна на [[Квантовый компьютер|квантовом компьютере]] с помощью [[Алгоритм Шора|алгоритма Шора]]<ref name=":0">{{Статья|автор=Ишмухаметов Ш. Т.|заглавие=Методы факторизации натуральных чисел: учебное пособие |язык=|издание=Казань: Казанский университет|год=2011 |страницы=190 |issn=}}</ref>.

=== Основная теорема арифметики ===
{{Main|Основная теорема арифметики}}
Основная теорема арифметики утверждает, что каждое [[натуральное число]], большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей<ref>{{Citation | last1=Dudley| first1=Underwood | title=Elementary number theory | publisher=W. H. Freeman and Co. | edition=2nd | isbn=978-0-7167-0076-0 | year=1978}}, Section 2, Theorem 2{{ref-en}}</ref>. Таким образом, простые числа являются элементарными «строительными блоками» натуральных чисел. Например:
: {|
|-
|<math>23244</math>||<math>= 2 \cdot 2 \cdot 3 \cdot 13 \cdot 149</math>
|-
|||<math> = 2^2 \cdot 3 \cdot 13 \cdot 149</math>. (<math>2^2</math> обозначает [[Квадрат (алгебра)|квадратную]] или вторую степень <math>2</math>.)
|}
Как было показано в этом примере, один и тот же простой делитель может появляться несколько раз. Разложение:
: {{math|1=''n'' = ''p''<sub>1</sub> · ''p''<sub>2</sub> · ... · ''p''<sub>''t''</sub>}}
числа {{math|''n''}} на (конечное число) простых множителей {{math|''p''<sub>1</sub>}}, {{math|''p''<sub>2</sub>}}, … ,{{math|''p''<sub>''t''</sub>}} называется ''разложением на простые множители'' числа {{math|''n''}}. Основная теорема арифметики может быть перефразирована таким образом: любое разложение на простые числа будет тождественным, за исключением порядка [[Делимость|делителей]]. На практике для большинства чисел есть много простых алгоритмов разложения на множители, все они дают один и тот же результат<ref name=":0" />.

Если {{math|''p''}} — простое число и {{math|''p''}} делит произведение {{math|''ab''}} целых чисел, то {{math|''p''}} делит {{math|''a''}} или {{math|''p''}} делит {{math|''b''}}. Это предложение известно как [[Лемма Евклида]]<ref>{{Citation | last1=Dudley| first1=Underwood | title=Elementary number theory | publisher=W. H. Freeman and Co. | edition=2nd | isbn=978-0-7167-0076-0 | year=1978}}, Section 2, Lemma 5{{ref-en}}</ref>. Она используется в некоторых доказательствах уникальности разложения на множители.

== Простота единицы ==
Большинство древних греков даже не считали <math>1</math> числом, поэтому они не могли считать его простым<ref>См, например, David E. Joyce’s комментарий на [[Начала (Евклид)]], [http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/defVII1.html Книга VII, определения 1 и 2].</ref>. К Средним векам и эпохе Возрождения многие математики включали <math>1</math> в качестве первого простого числа<ref name=faq>[https://primes.utm.edu/notes/faq/one.html Why is the number one not prime? (from the Prime Pages' list of frequently asked questions) by Chris K. Caldwell.]{{ref-en}}</ref>. В середине XVIII века [[Гольдбах, Христиан|Христиан Гольдбах]] внёс в список <math>1</math> в качестве первого простого числа в своей знаменитой переписке с [[Эйлер, Леонард|Леонардом Эйлером]]; однако сам Эйлер не считал <math>1</math> простым числом<ref>See for instance: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160—188. Variae observationes circa series infinitas,
[http://eulerarchive.maa.org/docs/originals/E072.pdf Theorema 19, p.187.]{{ref-en}}</ref>. В XIX веке многие математики по-прежнему считали число <math>1</math> простым числом. Например, список простых цифр [[Лемер, Деррик Норман|Деррика Нормана Лемера]] до <math>10006721</math> числа, переизданный 1956 году, начинался с <math>1</math> в качестве первого простого числа. Говорят, что [[Лебег, Анри Леон|Анри Лебег]] является последним математиком, который назвал <math>1</math> простым<ref>
{{Citation |last1=Derbyshire |first1=John  |title=Prime  Obsession: Bernhard Riemann and the Greatest  Unsolved Problem in  Mathematics  |year=2003  |publisher=Joseph Henry Press |location=Washington,  D.C.  |isbn=978-0-309-08549-6 |oclc=249210614  |page=33  |chapter=The  Prime Number Theorem }}{{ref-en}}</ref>. К началу XX века математики стали приходить к консенсусу о том, что <math>1</math> не является простым числом, а скорее формирует свою специальную категорию — «единицу»<ref name=faq />.

Если считать <math>1</math> простым числом, то основная теорема Евклида об арифметике (упомянутая выше) не будет выполняться, как указано. Например, число <math>15</math> может быть разложено как {{math|3 · 5 и 1 · 3 · 5}}. Если бы <math>1</math> являлась простым числом, эти два варианта считались бы разными факторизациями <math>15</math>, следовательно утверждение этой теоремы пришлось бы изменить<ref name="faq" />. Точно так же [[решето Эратосфена]] работало бы неправильно, если бы <math>1</math> считалась простым: модифицированная версия решета, которая предполагает, что <math>1</math> является простым числом, исключает все множители кратные <math>1</math> (то есть все остальные числа) и дает на выходе только одно число — <math>1</math>. Кроме того, простые числа имеют несколько свойств, которых нет у числа <math>1</math>, таких как отношение числа к его соответствующему значению [[Функция Эйлера|функции тождества Эйлера]] или суммы [[функция делителей|функции делителей]]<ref name=":7">"[http://primefan.tripod.com/Prime1ProCon.html «Arguments for and against the primality of 1]».{{ref-en}}</ref>.

== Алгоритмы поиска и распознавания простых чисел ==
[[Файл:Eratosthenes.jpg|thumb|150px|[[Эратосфен|Эратосфен Киренский]]]]
Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают [[решето Эратосфена]], [[решето Сундарама]] и [[решето Аткина]]<ref>{{Книга|автор=David Gries, Jayadev Misra.|заглавие=A Linear Sieve Algorithm for Finding Prime Numbers|ответственный=|издание=|место=|издательство=|год=1978|страницы=|страниц=|isbn=|isbn2=}}</ref>.

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются [[тест простоты|тестами простоты]]. Существует множество [[полиномиальный алгоритм|полиномиальных]] тестов простоты, но большинство их являются [[вероятностный алгоритм|вероятностными]] (например, [[тест Миллера — Рабина]]) и [[случайное простое число|используются]] для нужд [[криптография|криптографии]]<ref>{{Книга|автор=Knuth, Donald Ervin, 1938-|заглавие=The art of computer programming|ссылка=https://www.worldcat.org/oclc/823849|место=Reading, Mass.|издательство=Addison-Wesley Pub. Co|год=©1973-©1981|страниц=4 volumes|isbn=0201896842}}</ref>. В [[2002 год]]у было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный [[детерминированный алгоритм|детерминированный]] [[тест Агравала — Каяла — Саксены]] имеет довольно большую [[вычислительная сложность|вычислительную сложность]], что затрудняет его практическое применение<ref name=":9">{{Книга|автор=Vasilenko, O. N. (Oleg Nikolaevich)|заглавие=Teoretiko-chislovye algoritmy v kriptografii|ссылка=https://www.worldcat.org/oclc/85690769|место=Moskva|издательство=MT︠S︡NMO. Moskovskiĭ t︠s︡entr nepreryvnogo matematicheskogo obrazovanii︠a︡|год=2006|страниц=333 pages|isbn=5940571034}}</ref>.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

=== Тест простоты ===
'''Тестом простоты''' (или проверкой простоты) называется [[алгоритм]], который, приняв на входе число, позволяет либо не подтвердить предположение о [[Составное число|составности]] числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Задача теста простоты относится к [[Класс P|классу сложности P]], то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в [[2002 год]]у<ref name="SHN_Cr">{{книга|автор=Б. Шнайер|заглавие=Прикладная криптография|страницы=296—300}}</ref>. Появление полиномиального алгоритма предсказывалось существованием полиномиальных [[Сертификат простоты|сертификатов простоты]] и, как следствие, тем, что задача проверки числа на простоту принадлежала классам [[Класс NP|NP]] и [[Класс co-NP|co-NP]] одновременно.

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Результатом вычислений истинных тестов всегда является факт простоты либо составности числа. Вероятностный тест показывает, является ли число простым с некоторой вероятностью. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются [[Псевдопростое число|псевдопростыми]]<ref>{{Книга|автор=Кормен Т., Лейзер Ч.|заглавие=Алгоритмы. Построение и анализ|ответственный=|издание=|место=М.|издательство=МЦНМО|год=2002|страницы=765—772|страниц=|isbn=|isbn2=}}</ref>. Одним из примеров таких чисел являются [[числа Кармайкла]]<ref>{{Книга|автор=Crandall R., Pomerance C.|заглавие=Prime Numbers: A Computational Perspective|ответственный=|издание=|место=|издательство=Springer|год=2005|страницы=|страниц=|isbn=|isbn2=}}</ref>.

Одним из примеров истинных тестов простоты является [[тест Люка-Лемера]] для [[Числа Мерсенна|чисел Мерсенна]]. Очевидный недостаток этого теста заключается в его применимости только к  числам определённого вида. Среди других примеров можно привести основанные на [[Малая теорема Ферма|малой теореме Ферма]]<ref>{{Книга|заглавие=Introduction to algorithms|ссылка=https://www.worldcat.org/oclc/46792720|издание=2nd ed|место=Cambridge, Mass.|издательство=MIT Press|год=2001|страниц=xxi, 1180 pages|isbn=0262032937}}</ref>
* [[Тест Пепина]] для [[Числа Ферма|чисел Ферма]]
* [[Теорема Прота]] для [[Число Прота|чисел Прота]]
* [[Тест Агравала — Каяла — Саксены]], первый универсальный, полиномиальный, детерминированный и безусловный тест простоты.
* [[Тест Люка — Лемера — Ризеля]]
А также:
* [[Перебор делителей|метод перебора делителей]]
* [[Теорема Вильсона]]
* [[Критерий Поклингтона]]
* [[Тест Миллера (теория чисел)|Тест Миллера]]
* [[Тест Адлемана — Померанса — Румели]], усовершенствованный<ref name=":10">{{Книга|автор=Нестеренко Ю. В.|заглавие=Введение в криптографию|ответственный=|издание=|место=|издательство=Питер|год=2001|страницы=|страниц=288|isbn=|isbn2=}}</ref> Коэном и [[Ленстра, Арьен|Ленстрой]]
* [[Тест простоты с использованием эллиптических кривых]].
К вероятностным тестам простоты относят:
* [[Тест Ферма]]
* [[Тест Миллера — Рабина]]
* [[Тест Соловея — Штрассена]]
* [[Тест Бейли — Померанца — Селфриджа — Уогстаффа]]

=== Большие простые числа ===
Уже в течение многих столетий поиск «больших» простых чисел вызывает интерес математиков. В последние десятилетия эти исследования приобрели прикладное значение из-за применения таких чисел в ряде алгоритмов шифрования, таких как [[RSA]]<ref name=":4" />.

В семнадцатом столетии [[Мерсенн, Марен|Марен Мерсенн]] предположил, что числа вида <math>2^n - 1</math> простые (при ''n'' ≤ 257) только для ''n'' равных 2, 3, 5, 7, 13, 19, 31, 67, 127 и 257.<ref name=":3" /> Проверка верности предположения была намного выше возможностей того времени. Только в XX веке было обнаружено, что гипотеза была ложной и, вероятно, сделана «слепо», поскольку Мерсенн не учел три случая (для ''n'' = 61, 89 и 107); кроме того, оказалось, что числа, соответствующие ''n'' = 67 и ''n'' = 257 — составные<ref name=":3" />.

В 1876 году [[Люка, Франсуа Эдуард Анатоль|Эдуард Люка]] доказал, что число ''M ''<sub>127</sub> (39-значное число) — простое, оно оставалось самым большим известным простым числом до 1951 года, когда были найдены <math>\frac{2^{148} + 1}{17}</math> (44 цифры) и, немного позднее, <math>180 * (2^{127} - 1)^2 + 1</math> (из 79 цифр) — последнее простое число, которое было найдено с помощью электронного калькулятора. С тех пор все последующие большие простые числа были обнаружены с помощью компьютера: с 1952 года (когда [[SWAC]] показал, что ''M ''<sub>521</sub> является простым), по 1996 год они были найдены [[суперкомпьютер]]ом, и все были [[Числа Мерсенна|простыми Мерсенна]] (найденные с использованием [[Тест Люка — Лемера|теста Люка-Лемера]], специфического алгоритма для таких чисел), за исключением числа <math>391581 * 2^{216193} - 1</math>, которое было рекордом между 1989 и 1992 годами<ref>{{Cite web|url=http://primes.utm.edu/notes/by_year.html|title=The Largest Known Prime by Year: A Brief History|author=Chris Caldwell|website=The Prime Pages|date=|publisher=|lang=en}}</ref>.

=== Алгоритмы получения простых чисел ===
Некоторые задачи математики с использованием факторизации требуют ряд очень больших простых чисел, выбранных случайным образом. Алгоритм их получения, основанный на [[Постулат Бертрана|постулате Бертрана]] (Для любого натурального ''n'' ≥ 2 найдётся [[простое число]] ''p'' в интервале ''n'' < ''p'' < 2''n''.)<ref>{{Статья|автор=Jitsuro Nagura|заглавие=On the interval containing at least one prime number|ссылка=https://projecteuclid.org/euclid.pja/1195570997|язык=EN|издание=Proceedings of the Japan Academy|год=1952|том=28|выпуск=4|страницы=177—181|issn=0021-4280|doi=10.3792/pja/1195570997}}</ref>:
{| class="standard" style="margin-left: 1em"
|'''Алгоритм:'''
# '''Ввод''': натуральное число <math>N</math>
# '''Решение''' (поиск случайного простого числа P)
## <math>P \gets </math> '''Функция''' генерации произвольного натурального числа на отрезке <math>[N,2N]</math>
## '''Если''' <math>P</math> составное, '''то'''
### <math>P \leftarrow\,P+1</math>
### '''Если''' <math>P=2N</math> '''то'''
#### <math>P \leftarrow\,N</math>
## '''Возврат''' «<math>P</math> — случайное простое»
|}
Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее [[Дискретное равномерное распределение|равномерно]]. Для простых случайных чисел эти условия выполняются<ref name=":9" />.

Наиболее эффективным средством построения простых чисел является несколько модифицированная [[малая теорема Ферма]]<ref name=":10" />.

''Пусть N, S — нечётные натуральные числа, N-1 = S*R, причем для каждого простого [[Делимость|делителя]] q числа S существует целое число'' <math>a</math> ''такое, что''

<math>a^{N-1} = 1\pmod{N}</math>, <math>\gcd(a^{\frac{N-1}{q} - 1}, n) = 1</math>

''Тогда каждый простой делитель p числа N удовлетворяет сравнению''

 <math>p = 1\pmod{2S}</math>

Следствие. ''Если выполнены условия теоремы Ферма и'' <math>R \leqslant 4S + 2</math>'', то N — простое число.''<ref name=":10" />

Покажем теперь, как с помощью последнего утверждения, имея большое простое число <math>S</math>, можно построить существенно большее простое число <math>N</math>. Выберем для этого случайным образом чётное число <math>R</math> на промежутке <math>R \leqslant 4S + 2</math> и положим <math>N = SR + 1</math>. Затем проверим число <math>N</math> на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем <math>N</math> некоторое количество раз с помощью алгоритма Рабина. Если при этом выяснится, что <math>N</math> — [[Составное число|составное]] число, следует выбрать новое значение <math>R</math> и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число N, выдержавшее испытание алгоритмом Рабина достаточно много раз. В этом случае появляется надежда на то, что <math>N</math> — простое число, и следует попытаться доказать простоту с помощью тестов простоты<ref name=":10" />.

== Бесконечность множества простых чисел ==
{{main|Теорема Евклида}}
Простых чисел [[бесконечность|бесконечно]] много. Это утверждение упоминается как [[теорема Евклида]] в честь древнегреческого математика [[Евклид]]а, поскольку первое известное доказательство этого утверждения приписывается ему. Известно ещё много доказательств бесконечности простых чисел, в том числе [[Анализ (раздел математики)|аналитическое]] доказательство [[Эйлер, Леонард|Эйлера]], доказательство [[Гольдбах, Христиан|Гольдбаха]] на основе [[числа Ферма|чисел Ферма]]<ref>[http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0722.pdf Letter] in [[Латынь]] from Goldbach to Euler, July 1730.</ref>, доказательство Фурстенберга с использованием общей топологии и элегантное доказательство [[Куммер, Эрнст Эдуард|Куммера]].

== Наибольшее известное простое ==
{{main|Наибольшее известное простое число}}

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа<ref>[http://primes.utm.edu/notes/by_year.html Рекорды простых чисел по годам]</ref>. Один из рекордов поставил в своё время [[Эйлер, Леонард|Эйлер]], найдя простое число {{s|1={{power|2|31}} − 1 = {{num|2147483647}}}}.

[[Наибольшее известное простое число|Наибольшим известным простым числом]] по состоянию {{на|1|2019}} является [[Числа Мерсенна|число Мерсенна]] M<sub>{{num|82589933}}</sub> = {{s|1={{power|2|{{num|82589933}}}} − 1}}. Оно содержит {{num|24 862 048}} [[десятичная система счисления|десятичных цифр]]; в книге с записью этого числа было бы около девяти тысяч страниц. Его нашли 7 декабря 2018 года в рамках проекта по распределённому поиску простых чисел Мерсенна [[GIMPS]]. Предыдущее самое большое известное простое число, открытое в декабре 2017 года, было на {{num|1612623}} знаков меньше<ref>{{Cite news|title=The Largest Prime Number to Date Has Been Discovered And It's Hurting Our Brains|first=Michelle|last=Starr|url=https://sciencealert.com/record-breaking-mersenne-prime-number-23-million-digits-m77232917|work=ScienceAlert|accessdate=2018-01-06|language=en-gb}}</ref>.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного [[тест простоты|теста простоты]]: [[тест Люка — Лемера|теста Люка — Лемера]]. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр [[Electronic Frontier Foundation|EFF]] назначила<ref>[https://www.eff.org/awards/coop EFF Cooperative Computing Awards]{{ref-en}}</ref> денежные призы соответственно в 150 000 и 250 000 [[доллар США|долларов США]]<ref>{{cite web|url=https://www.vesti.ru/doc.html?id=1026600&tid=108323|title=Профессор из США определил самое большое простое число|author=Юлия Рудый|date=2013-02-07|publisher=Вести.Ru|accessdate=2018-02-25}}</ref>. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

== Простые числа специального вида ==
Существует ряд чисел, простота которых может быть установлена эффективно с использованием специализированных алгоритмов.

* [[Число Мерсенна|Числа Мерсенна]] — числа вида <math>M_n=2^n-1</math>, где ''n'' — натуральное число<ref name=":15">{{OEIS long|1348}}</ref>. При этом число Мерсенна может быть простым, только если ''n'' — простое число. Как уже было отмечено выше, эффективным тестом простоты является [[тест Люка — Лемера]]<ref>{{OEIS long|668|ru=простые числа Мерсенна}}</ref>.
* [[Числа Ферма]] — числа вида <math>F_n=2^{2^n}+1</math>, где ''n'' — неотрицательное целое число<ref>{{OEIS long|215}}</ref>. Эффективным тестом простоты является [[тест Пепина]]. По состоянию на февраль 2015 года известно только 5 простых чисел Ферма (для ''n'' = 0, 1, 2, 3, 4), двадцать восемь следующих чисел Ферма (до <math>F_{32}</math> включительно) оказались составными<ref>{{Citation |first=Wilfrid |last=Keller |url=http://www.prothsearch.net/fermat.html#Summary |title=Prime Factors of Fermat Numbers |work=ProthSearch.net |date=February 15, 2015 |accessdate=March 1, 2016 |archiveurl=https://web.archive.org/web/20160210152415/http://www.prothsearch.net/fermat.html#Summary |archivedate=2016-02-10 }} {{Wayback|url=http://www.prothsearch.net/fermat.html#Summary |date=20160210152415 }}</ref>, однако не доказано, что других простых чисел Ферма нет<ref>{{книга |автор=Виолант-и-Хольц, Альберт. |заглавие=Загадка Ферма. Трёхвековой вызов математике |место=М. |издательство=Де Агостини |год=2014 |страниц=151 |isbn=978-5-9774-0625-3 |серия=Мир математики: в 45 томах, том 9 |страницы=78 }}</ref>.
* [[Число Вудала|Числа Вудала]] — числа вида <math>W_n=n \cdot 2^n-1</math><ref>{{OEIS long|A003261}}</ref>. Эффективным тестом простоты является [[тест Люка — Лемера — Ризеля]]<ref>{{OEIS long|A050918|ru=простые числа Вудала}}</ref>.
* [[Числа Каллена]] — числа вида <math>C_n=n \cdot 2^n+1</math><ref>{{OEIS long|A002064}}</ref><ref>{{OEIS long|A050920|ru=простые числа Каллена}}</ref>.
* [[Число Прота|Числа Прота]] — числа вида <math>P=k \cdot 2^n+1</math>, причём ''k'' нечётно и <math>2^n>k</math><ref>{{OEIS long|A080075}}</ref>. Эффективным тестом простоты для чисел Прота является [[тест Бриллхарта — Лемера — Селфриджа]] ({{lang-en|Brillhart–Lehmer–Selfridge test}})<ref>{{статья |заглавие=New Primality Criteria and Factorizations of 2^m ± 1 |издание={{Нп3|Mathematics of Computation}} |том=29 |страницы=620—647 |doi=10.1090/S0025-5718-1975-0384673-1 |ссылка=http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf |язык=en |тип=journal |автор=[[John Brillhart]]; [[Derrick Henry Lehmer]]; [[John Selfridge]] |месяц=4 |год=1975}}</ref>. Числа Каллена и числа Ферма являются частным случаем чисел Прота (соответственно при ''k'' = ''n'' и при ''k'' = 1, <math>n=2^m</math>)<ref>{{OEIS long|A080076|ru=простые числа Прота}}</ref>.
* [[Константа Миллса|Числа Миллса]] — числа вида <math>P_n = [ A^{3^n} ] , </math> где <math>A</math> — [[константа Миллса]]<ref>{{citation|last1=Caldwell|first1=Chris K.|last2=Cheng|first2=Yuanyou|title=Determining Mills' Constant and a Note on Honaker's Problem|journal=Journal of Integer Sequences|volume=8|year=2005|issue=5.4.1|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Caldwell/caldwell78.html}}</ref>.

Для поиска простых чисел обозначенных типов в настоящее время используются проекты [[распределённые вычисления|распределённых вычислений]] [[GIMPS]], [[PrimeGrid]], [[Ramsey@Home]], [[Seventeen or Bust]], [[Riesel Sieve]], [[Wieferich@Home]].

== Некоторые свойства ==
* Если {{mvar|p}} — простое, и {{mvar|p}} делит {{mvar|ab}}, то {{mvar|p}} делит {{mvar|a}} или {{mvar|b}}. Доказательство этого факта было дано Евклидом и известно как [[лемма Евклида]]<ref name=":8" />. Оно используется в доказательстве [[Основная теорема арифметики|основной теоремы арифметики]].
* [[Кольцо вычетов]] <math>\mathbb{Z}_n</math> является [[Поле (алгебра)|полем]] тогда и только тогда, когда <math>n</math> — простое<ref name="Stepanov">{{книга|автор=Степанов С. А.|часть=|заглавие=Сравнения|ссылка=http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm|ответственный=|издание=|место=М.|издательство=«Знание»|год=1975|страницы=|страниц=64|isbn=|isbn2=}}</ref>.
* [[характеристика поля|Характеристика]] каждого поля — это ноль или простое число<ref name="Stepanov" />.
* Если <math>p</math> — простое, а <math>a</math> — натуральное, то <math>a^p-a</math> делится на <math>p</math> ([[малая теорема Ферма]]){{sfn|Винберг|2008|с=43}}.
* Если <math>G</math> — конечная группа, порядок которой <math>|G|</math> делится на <math>p</math>, то <math>G</math> содержит элемент порядка <math>p</math> ([[Теорема Коши (теория групп)|теорема Коши]])<ref name=":11">''[[Курош, Александр Геннадиевич|Курош А. Г.]]'' Теория групп. 3-е изд., М.: Наука, 1967.</ref>.
* Если <math>G</math> — конечная группа, и <math>p^n</math> — максимальная степень <math>p</math>, которая делит <math>|G|</math>, то <math>G</math> имеет подгруппу порядка <math>p^n</math>, называемую [[силовская подгруппа|силовской подгруппой]], более того, количество силовских подгрупп равно <math>pk+1</math> для некоторого целого <math>k</math> ([[теоремы Силова]])<ref>А. И. Кострикин. Введение в алгебру, III часть. М.: Физматлит, 2001.</ref>.
* Натуральное <math>p > 1</math> является простым тогда и только тогда, когда <math>(p-1)! + 1</math> делится на <math>p</math> ([[теорема Вильсона]])<ref name=":12">{{книга|автор=Виноградов И. М.|заглавие=Основы теории чисел|ссылка=http://ilib.mccme.ru/djvu/vinogradov.htm|издание=5 изд.|место=М.-Л.|издательство=Гостехиздат|год=1952}}</ref>.
* Если <math>n > 1</math> — натуральное, то существует простое <math>p</math>, такое, что <math>n < p < 2 n</math> ([[постулат Бертрана]])<ref>Chris Caldwell, [http://primes.utm.edu/glossary/page.php?sort=BertrandsPostulate ''Bertrand’s postulate''] at [[Prime Pages]] glossary.</ref>.
* [[Ряд чисел, обратных к простым]], расходится<ref name=":2" />. Более того, при <math>x\to\infty</math>
*: <math>\sum_{p<x} \frac{1}{p}\ \sim\ \ln \ln x.</math>
* Любая [[арифметическая прогрессия]] вида <math> a, a + q, a + 2 q, a + 3 q, ... </math>, где <math> a, q > 1</math> — целые [[взаимно простые числа]], содержит бесконечно много простых чисел ([[теорема Дирихле о простых числах в арифметической прогрессии]]){{sfn|Энциклопедический словарь юного математика|1985}}.
* Всякое простое число, большее 3, представимо в виде <math>6k+1</math> или <math>6k-1</math>, где <math>k</math> — некоторое натуральное число. Отсюда, если разность между несколькими [[Арифметические прогрессии из простых чисел#Последовательности без пропусков|последовательными простыми числами]] (при k>1) одинакова, то она обязательно кратна 6 — например: 251-257-263-269; 199-211-223; 20183-20201-20219.
* Если <math>p > 3</math> — простое, то <math>p^2-1</math> кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3)<ref>{{razr|Доказательство}}. Нечётное число ''p'', не кратное 3, равно 1 или 2 по модулю 3 и равно 1, 3, 5 или 7 по модулю 8. При возведении в квадрат это даёт 1 по модулю 3 и 1 по модулю 8. Вычитая 1, получаем 0 по модулю 3 и 0 по модулю 8. Следовательно, <math>p^2-1</math> кратно 3 и кратно 8; следовательно, оно кратно 24</ref>.
* [[Теорема Грина-Тао]]. Существуют сколь угодно длинные конечные [[арифметические прогрессии из простых чисел|арифметические прогрессии, состоящие из простых чисел]]<ref>{{MathWorld3|Green-Tao Theorem}}</ref>.
* Никакое простое число не может иметь вид <math>n^k-1</math>, где ''n''>2, ''k''>1. Иначе говоря, число, следующее за простым, не может быть [[квадрат (число)|квадратом]] или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид <math>2^k-1</math>, то ''k'' — простое (см. [[числа Мерсенна]])<ref name=":15" />.
* Никакое простое число не может иметь вид <math>n^{2k+1}+1</math>, где ''n''>1, ''k''>0. Иначе говоря, число, предшествующее простому, не может быть [[куб (алгебра)|кубом]] или более высокой нечётной степенью с основанием, бо́льшим 1<ref>Эти 2 свойства непосредственно следуют из [[формулы сокращённого умножения многочленов|формул разложения суммы и разности степеней]]</ref>.
* Каждое простое число (кроме чисел вида 8n-1) можно представить в виде суммы трех квадратов{{sfn|Энциклопедический словарь юного математика|1985|с=332}}.

== Применения ==
Простые числа являются фундаментальными компонентами во многих областях [[Математика|математики]].

=== Арифметические функции ===
[[Арифметическая функция|Арифметические функции]], а именно функции, определённые на множестве натуральных чисел и принимающих значения во множестве комплексных чисел, играют решающую роль в теории чисел. В частности, среди них наиболее важными являются [[Мультипликативная функция|мультипликативные]] функции, то есть функции <math>f</math>'','' обладающие следующим свойством: если пара <math>(a,b)</math> состоит из взаимно простых чисел, то имеет место равенство<ref name=":13">{{Книга|автор=Graham, Ronald L. (1935- ).|заглавие=Konkretnaâ matematika : osnovanie informatiki|ссылка=https://www.worldcat.org/oclc/1014108083|место=Moskva|издательство=Izdatelʹstvo "Mir"|год=1998|страниц=703, [1] s.|isbn=5030017933}}</ref>

<math>f(ab) = f(a)f(b)</math>

Примерами [[Мультипликативная функция|мультипликативных]] функций являются [[функция Эйлера]] <math>\phi</math>, которая ставит в соответствие числу <math>n</math> количество натуральных чисел, меньших n и взаимно простых с ним и количество делителей числа ''n''<ref>{{Книга|автор=Sandifer, Charles Edward, 1951-|заглавие=The early mathematics of Leonhard Euler|ссылка=https://www.worldcat.org/oclc/82370957|место=Washington, D.C.|издательство=Mathematical Association of America|год=2007|страниц=xix, 391 pages|isbn=0883855593}}</ref>. Значение этих функций от степени простого числа:
* [[Функция Эйлера|Функция <math>\phi</math> Эйлера]]:
<math>\phi(p^m) = p^m - p^{m-1}</math>
* [[Функция делителей|Функция делителя]]:
<math>\sigma(p^m) = m + 1</math>

Арифметические функции можно легко вычислить, зная значения, которые они принимают для степеней простых чисел<ref name=":13" />. На самом деле из [[Факторизация целых чисел|разложения натурального числа n на множители]]

<math>n = p_1^{q_1}\cdot...\cdot p_a^{q_a}</math>

мы имеем, что

<math>f(n) = f(p_1^{q_1})\cdot...\cdot f(p_a^{q_a})</math>

и следовательно, возвращаясь к задаче вычисления <math>f(n)</math> получается что вычислить <math>f</math> от каждой степени простого делителя обычно проще, чем вычислить <math>f</math> по общей формуле.<ref>{{Книга|автор=Bach, Eric.|заглавие=Algorithmic number theory|ссылка=https://www.worldcat.org/oclc/33164327|место=Cambridge, Mass.|издательство=MIT Press|год=©1996-|страниц=volumes <1>|isbn=0262024055}}</ref>

Например, чтобы узнать значение функции Эйлера <math>\phi</math> от ''n'' = 450 = 2 × 3 <sup>2</sup> × 5 <sup>2</sup>, достаточно вычислить

<math>\phi(450) = \phi(2)\cdot\phi(3^2)\cdot\phi(5^2) = (2-1)\cdot(9-3)\cdot(25-5) = 120</math>

=== Модульная арифметика ===
В [[Сравнение по модулю|модульной арифметике]] простые числа играют очень важную роль: кольцо вычетов <math>\mathbb{Z}/n\mathbb{Z}</math> является [[Поле (алгебра)|полем]] тогда и только тогда, когда ''n'' является простым.<ref name="Stepanov" /> Также существование [[Первообразный корень (теория чисел)|первообразного корня кольца]] <math>\mathbb{Z}/n\mathbb{Z}</math> привязано к простым числам: оно существует, только если ''n'' — простое число, 1, 2, 4 или число в форме <math>p^n\circ2p^n</math>, где ''p'' нечётно.

Одной из важнейших теорем модульной арифметики является [[малая теорема Ферма]]<ref name=":12" />. Эта теорема утверждает, что для любого простого числа ''р'' и любого натурального числа ''a'' имеем:

<math>a^p \equiv a \pmod{p}</math>

или для любого простого ''р'' и любого [[Натуральное число|натурального]] а не делящегося на ''р'', справедливо:

<math>a^{p-1} \equiv 1 \pmod{p}</math>

Это свойство можно использовать для проверки того, что число ''не'' является простым. На самом деле, если ''n'' таково, что:

<math>a^n \not\equiv a \pmod{n}</math>

для некоторого натурального ''а'', то ''n'' не может быть простым<ref name=":12" />. Однако это свойство не может быть использовано для проверки числа на простоту: есть некоторые числа, называемые [[Число Кармайкла|числами Кармайкла]] (наименьшее — 561) для которых это будет неверно. Числом Кармайкла называется [[Составное число|составное]] число, которое является [[Псевдопростое число|псевдопростым числом]] по каждому основанию b, взаимно простому с n. В 1994 году Уильям Роберт Альфорд, Эндрю Гранвиль и [[Померанс, Карл|Карл Померанс]] показали, что таких чисел бесконечно много<ref>{{Статья|автор=W. R. Alford, Andrew Granville, Carl Pomerance|заглавие=There are Infinitely Many Carmichael Numbers|ссылка=http://www.jstor.org/stable/2118576|издание=Annals of Mathematics|год=1994|том=139|выпуск=3|страницы=703—722|doi=10.2307/2118576}}</ref>.

=== Теория групп ===
Простые числа также играют основополагающую роль в [[Алгебра|алгебре]]. В [[Теория групп|теории групп]], группа, в которой каждый элемент является степенью простого числа ''р'' называется ''[[P-группа|р-группой]]''<ref>{{Статья|автор=Charles C. Sims|заглавие=Enumerating p-Groups|ссылка=http://onlinelibrary.wiley.com/doi/10.1112/plms/s3-15.1.151/abstract|язык=en|издание=Proceedings of the London Mathematical Society|год=1965-01-01|том=s3—15|выпуск=1|страницы=151—166|issn=1460-244X|doi=10.1112/plms/s3-15.1.151}}</ref>. P-группа является [[Конечная группа|конечной]], тогда и только тогда, когда [[порядок группы]] (число её элементов) является степенью р. Примером бесконечной р-группы является '''[[Квазициклическая группа|''p''-группа Прюфера]]'''<ref>{{Книга|автор=Jacobson, Nathan, 1910-1999.|заглавие=Basic algebra |ссылка=https://www.worldcat.org/oclc/294885194|издание=2nd ed., Dover ed|место=Mineola, N.Y. |издательство=Dover Publications|год=2009|страниц=2 volumes|isbn=9780486471877}}</ref>. Известно, что ''p-''группы имеют нетривиальный [[Центр группы|центр]] и, следовательно, не могут быть простыми (кроме группы с ''p'' элементами); если группа конечна, более того, все нормальные подгруппы пересекают центр нетривиальным образом.

Примером таких групп является [[Циклическая группа|циклическая]] группа [[Группа (математика)#Мультипликативная запись|умножения]] по [[Сравнение по модулю|модулю]] простого числа<ref>{{Книга|автор=Сагалович Ю.Л.|заглавие=Введение в алгебраические коды|ссылка=http://iitp.ru/upload/content/790/algebcodes.pdf|ответственный=|издание=|место=|издательство=|год=2011|страницы=|страниц=302|isbn=|isbn2=}}</ref>.

Все группы порядка p являются [[Циклическая группа|циклическими]] и поэтому [[Абелева группа|абелевыми]]; также абелева каждая группа порядка ''p'' <sup>2</sup>. Кроме того, любая конечная абелева группа [[Изоморфные группы|изоморфна]] прямому произведению конечного числа циклических р-групп.

В [[Теорема Коши (теория групп)|теореме Коши]] утверждается, что если [[Порядок группы|порядок]] [[Конечная группа|конечной]] [[Группа (математика)|группы]] G делится на [[простое число]] p, то G содержит элементы [[Порядок элемента|порядка]] p. Эта теорема обобщается [[Теоремы Силова|теоремами Силова]]<ref name=":11"/>.

=== Криптосистема с открытым ключом ===
{{Основная статья|Криптосистема с открытым ключом}}
Некоторые алгоритмы криптографии с открытым ключом, такие как [[RSA]] и [[Протокол Диффи — Хеллмана|обмен ключами Диффи-Хеллмана]], основаны на больших простых числах (обычно 1024—2048 бит). RSA полагается на предположение, что намного проще (то есть более эффективно) выполнять умножение двух (больших) чисел ''x'' и ''y,'' чем вычислять [[Взаимно простые числа|взаимно простые]] ''x'' и ''y'', если известно только их произведение <math>x\cdot y</math> . [[Протокол Диффи — Хеллмана|Обмен ключами Диффи-Хеллмана]] основан на том, что существуют эффективные алгоритмы [[Возведение в степень по модулю|возведения в степень по модулю]], а обратная операция — [[Дискретное логарифмирование|дискретного логарифмирования]] считается сложной<ref>{{Книга|автор=Ferguson, Niels.|заглавие=Practical cryptography|ссылка=https://www.worldcat.org/oclc/51568066|место=New York|издательство=Wiley|год=2003|страниц=xx, 410 pages|isbn=0471223573}}</ref><ref>{{Статья|автор=W. Diffie, M. Hellman|заглавие=New directions in cryptography|ссылка=http://ieeexplore.ieee.org/document/1055638/|издание=IEEE Transactions on Information Theory|год=November 1976|том=22|выпуск=6|страницы=644—654|issn=0018-9448|doi=10.1109/tit.1976.1055638}}</ref>.

==== RSA ====
Трудность [[Факторизация целых чисел|факторизации]] больших чисел привела к разработке первого эффективного метода [[Криптосистема с открытым ключом|криптографии с открытым ключом]] — [[RSA]].{{Sfn|Bakhtiari, Maarof|2012|p=175}} В этой криптографической системе, человек, который должен получить зашифрованное сообщение, генерирует ключ: выбираются два различных [[Случайное простое число|случайных простых числа]] <math>p</math> и <math>q</math> заданного размера (обычно используются, 1024- или 2048-[[бит]]ные числа). Далее вычисляется их произведение <math>n = p * q</math>, называемое ''модулем''. Вычисляется значение [[Функция Эйлера|функции Эйлера]] от числа <math>n</math>: <math>\phi(n) = (p - 1)(q - 1)</math>. Выбирается целое число <math>e</math> (<math>1 < e < \phi(n)</math>), [[Взаимно простые числа|взаимно простое]] со значением функции <math>\phi(n)</math>. Обычно в качестве <math>e</math> берут небольшие простые числа (например, простые [[числа Ферма]]). Число <math>e</math> называется ''открытой экспонентой'' ([[Английский язык|англ.]] ''public exponent''). Вычисляется число <math>d</math>, называемое секретной экспонентой, [[Мультипликативная функция|мультипликативно]] обратное к числу e по модулю <math>\phi(n)</math>. Пара <math>\{e, n\}</math> публикуется в качестве ''открытого ключа RSA'' ([[Английский язык|англ.]] ''RSA public key''). Пара <math>\{d, n\}</math> играет роль ''закрытого ключа RSA'' ([[Английский язык|англ.]] ''RSA private key'') и держится в секрете<ref name=":4" />.

Теоретически можно получить закрытый ключ из общедоступной информации: в настоящее время для этого требуется факторизация числа <math>n</math>, что делает передачу защищенного сообщения безопасной, если простые числа удовлетворяют определённым условиям и являются «достаточно большими». Пока не известно, существуют ли эффективные методы для расшифровки сообщения, не связанные с прямой атакой на факторизацию <math>n</math>, но было показано, что плохой выбор открытого ключа может сделать систему более уязвимой для таких атак.{{Source-ref|Q27210308|pages=|volume=|issue=}}

В 1991 году [[RSA Security]] опубликовала список [[Полупростое число|полупростых]] чисел, предлагая денежные призы за разложение некоторых из них на множители, с целью подтверждения безопасности метода и поощрения исследования в этой области: инициатива называлась [[Challenge RSA Factoring]].<ref name=":5">RSA Laboratories, [http://www.rsa.com/rsalabs/node.asp?id=2092 The RSA Factoring Challenge] {{webarchive|url=https://web.archive.org/web/20130507091636/http://www.rsa.com/rsalabs/node.asp?id=2092|data=7 мая 2013}}. Опубликовано 18 мая 2007.</ref> На протяжении многих лет некоторые из этих чисел были разложены, а для других проблема факторизации все ещё остается открытой; однако конкурс был завершен в 2007 году<ref name=":5" />.

== Формулы для нахождения простых чисел ==
В разное время предпринимались попытки указать выражение, значениями которого при разных значениях входящих в него переменных были бы простые числа{{sfn|Энциклопедический словарь юного математика|1985}}.
Л. Эйлер указал многочлен <math>\textstyle n^2-n+41,</math> принимающий простые значения при {{s|{{mvar|n}} {{=}} 0, 1, 2, …, 40}}. Однако при {{s|{{mvar|n}} {{=}} 41}} значение многочлена является составным числом. Можно доказать, что не существует многочлена от одной переменной {{mvar|n}}, который принимает простые значения при всех целых {{mvar|n}}{{sfn|Энциклопедический словарь юного математика|1985}}.
П. Ферма предположил, что все [[Числа Ферма|числа вида {{s|{{power|2|2|{{mvar|k}}}} + 1}}]] простые; однако Эйлер опроверг эту гипотезу, доказав, что число {{s|{{power|2|2|5}} + 1 {{=}} {{num|4294967297}}}} — составное{{sfn|Энциклопедический словарь юного математика|1985}}.

Тем не менее, существуют многочлены, множество положительных значений которых при неотрицательных значениях переменных совпадает с множеством простых чисел. Одним из примеров является многочлен
: <math>\begin{align}
\bigl(k+2\bigr) \bigl\{1 
  & - \bigl[wz + h + j - q\bigr]^2 - \bigl[(gk + 2g + k + 1)(h + j) + h - z\bigr]^2 - \bigl[2n + p + q + z - e\bigr]^2 \\
  & - \bigl[16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2\bigr]^2 - \bigl[e^3(e + 2)(a + 1)^2 + 1 - o^2\bigr]^2 - \bigl[(a^2 - 1)y^2 + 1 - x^2\bigr]^2 \\
  & - \bigl[16r^2y^4(a^2 - 1) + 1 - u^2\bigr]^2 - \bigl[((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2\bigr]^2 - \bigl[n + l + v - y\bigr]^2 \\
  & - \bigl[(a^2 - 1)l^2 + 1 - m^2\bigr]^2 - \bigl[ai + k + 1 - l - i\bigr]^2 - \bigl[p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m\bigr]^2 \\
  & - \bigl[q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x\bigr]^2 - \bigl[z + pl(a - p) + t(2ap - p^2 - 1) - pm\bigr]^2\bigr\}
\end{align}</math>
содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа — 5 при 42 переменных; наименьшее число переменных — 10 при степени около 1,6·10<sup>45</sup><ref>{{статья
|заглавие=Diophantine representation of the set of prime numbers
|издание=[[American Mathematical Monthly|Amer. Math. Mon.]]
|том=83
|номер=6
|страницы=449—464
|ссылка=http://mathdl.maa.org/images/upload_library/22/Ford/JonesSatoWadaWiens.pdf
|archiveurl=https://web.archive.org/web/20100331232439/http://mathdl.maa.org/images/upload_library/22/Ford/JonesSatoWadaWiens.pdf
|archivedate=2010-03-31
|deadlink=404
|язык=en
|тип=journal
|автор=Jones J. P.,
Sato D., Wada H., Wiens D.
|год=1976}}</ref><ref>Yuri Matiyasevich, [http://www.inf.unisi.ch/guest-lectures/matiyas/Lugano_public1_print.pdf Diophantine Equations in the XX Century]{{Недоступная ссылка|date=Май 2019 |bot=InternetArchiveBot }}</ref>. Этот результат является частным случаем [[Десятая проблема Гильберта|доказанной]] [[Матиясевич, Юрий Владимирович|Юрием Матиясевичем]] диофантовости любого [[Перечислимое множество|перечислимого множества]].

Интересно, что приведённый выше многочлен, который порождает простые числа, сам разлагается на множители. Заметим, что второй множитель этого многочлена (в фигурных скобках) имеет форму: единица минус сумма квадратов. Таким образом, многочлен может принимать положительные значения (при положительных <math>k</math>) только если, каждый из этих квадратов (то есть каждый многочлен в квадратных скобках) равен нулю. В этом случае выражение в фигурных скобках будет равно 1<ref>[http://primes.utm.edu/glossary/page.php?sort=MatijasevicPoly Matijasevic’s polynomial]. The Prime Glossary.</ref>.

== Открытые вопросы ==
{{main|Открытые проблемы в теории чисел}}

[[Файл:Dp txt2.png|thumb|Распределение простых чисел ''p''<sub>''n''</sub> = ''f'' (Δ''s''<sub>''n''</sub>); Δ''s''<sub>''n''</sub> = ''p''<sub>''n''+1</sub>² — ''p''<sub>''n''</sub>². Δ''p''<sub>''n''</sub> = ''p''<sub>''n''+1</sub> — ''p''<sub>''n''</sub>; Δ''p''<sub>''n''</sub> = 2, 4, 6, … .]]

До сих пор существует много [[гипотеза|открытых вопросов]] относительно простых чисел, наиболее известные из которых были перечислены [[Ландау, Эдмунд|Эдмундом Ландау]] на Пятом [[Международный математический конгресс|Международном математическом конгрессе]]<ref>{{MathWorld3|Landau's Problems}}</ref>:

# [[Проблема Гольдбаха]] (''первая проблема Ландау''): верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел?
# ''Вторая проблема Ландау'': бесконечно ли множество [[простые близнецы|«простых близнецов»]] — пар простых чисел, разность между которыми равна 2{{sfn|Энциклопедический словарь юного математика|1985}}?(в 2013 году математик [[Чжан Итан]] из университета Нью-Гэмпшира<ref>[http://habrahabr.ru/post/180259/ Неизвестный математик совершил прорыв в теории простых чисел-близнецов]</ref><ref>[http://golem.ph.utexas.edu/category/2013/05/bounded_gaps_between_primes.html Bounded Gaps Between Primes]</ref> доказал, что существует бесконечно большое количество пар простых чисел, расстояние между которыми не превышает 70 миллионов. Позже, [[Мейнард, Джеймс|Джеймс Мэйнард]] улучшил результат до 600. В 2014 году проект {{iw|Polymath|||Polymath Project}} под руководством [[Тао, Теренс|Теренса Тао]] несколько улучшили последний метод, получив оценку в 246.)
# ''Гипотеза [[Лежандр, Адриен Мари|Лежандра]]'' (''третья проблема Ландау''): верно ли, что для всякого натурального числа {{mvar|n}} между {{power|{{mvar|n}}|2}} и {{power|({{mvar|n}} + 1)|2}} всегда найдётся простое число<ref>{{mathworld|urlname=LegendresConjecture|title=Гитотеза Лежандра}}</ref>?
# ''Четвёртая проблема Ландау'': бесконечно ли множество простых чисел вида {{power|{{mvar|n}}|2}} + 1, где {{mvar|n}} — натуральное число{{sfn|Энциклопедический словарь юного математика|1985}}?

Открытой проблемой является также существование бесконечного количества простых чисел во многих целочисленных последовательностях, включая [[числа Мерсенна]]{{sfn|Энциклопедический словарь юного математика|1985}}, [[числа Фибоначчи]], [[числа Ферма]] и др.

== Вариации и обобщения ==

=== Неприводимые и простые элементы ===
{{main|Неприводимый элемент|Простой элемент}}
В начале статьи было дано определение простого числа: натуральное число называется простым, если у него ровно два делителя — единица и само число. Аналогичное понятие можно ввести и в других алгебраических структурах; чаще всего рассматривается [[Коммутативное кольцо|коммутативные кольца]] без [[Делитель нуля|делителей нуля]] ([[Область целостности|области целостности]])<ref>Обобщение на произвольные [[Полугруппа|полугруппы]] см. в книге Куроша.</ref>{{sfn |Ван дер Варден|2004|с=75}}. У таких колец, однако, могут быть [[Обратимый элемент|делители единицы]], образующие [[Группа (математика)|мультипликативную группу]]. Например, в кольце [[Целое число|целых чисел]] существуют два делителя единицы: <math>+1</math> и <math>-1.</math> Поэтому все целые числа, кроме делителей единицы, имеют не два, а по меньшей мере четыре делителя; например, у числа 7 делителями являются <math>1; 7; -1; -7.</math> Это означает, что обобщение понятия простого числа должно опираться на иные его свойства.

Аналогом простого числа для области целостности является [[неприводимый элемент]]. который определяется следующим образом{{sfn |Курош|1973|с=82—83|name=KUR82}}.
{{рамка}}
Ненулевой элемент <math>p</math> области целостности называется ''неприводимым'' (иногда ''неразложимым''), если он не является делителем единицы и из равенства <math>p=ab</math> следует, что <math>a</math> или <math>b</math> является делителем единицы.
|}
Для целых чисел это определение означает, что неприводимыми элементами являются простые натуральные числа, а также противоположные им.

Из определения следует, что множество делителей неприводимого элемента <math>p</math> состоит из двух частей: все делители единицы и произведения <math>p</math> на все делители единицы (эти произведения называются ''ассоциированными'' с <math>p</math> злементами). То есть количество делителей неприводимого <math>p,</math> если оно конечно, вдвое больше количества делителей единицы в кольце.

Важное значение имеет аналог [[Основная теорема арифметики|основной теоремы арифметики]], который в обобщённом виде формулируется следующим образом{{sfn |Ленг|1967|с=89}}:
{{рамка}}
Кольцо называется [[Факториальное кольцо|факториальным]], если в нём каждый ненулевой элемент, не являющийся делителем единицы, может быть представлен в виде произведения неприводимых элементов, причём это представление единственно с точностью до перестановки сомножителей и их ассоциированности (умножения на делители единицы).
|}
Не всякая область целостности факториальна, см. [[Основная теорема арифметики#Неединственность разложения в кольце|контрпример]]. [[Евклидово кольцо]] всегда факториально{{sfn |Ван дер Варден|2004|с=77—78}}.

Существует другое, более узкое обобщение понятия простого числа, называемое [[Простой элемент|простым элементом]]<ref name=KUR82/>.
{{рамка}}
Ненулевой элемент <math>p</math> области целостности называется ''простым'', если он не является делителем единицы и произведение <math>ab</math> может делиться на <math>p</math> лишь в том случае, когда хотя бы один из элементов <math>a</math> или <math>b</math> делится на <math>p</math>.
|}
Простой элемент всегда неприводим. В самом деле, если элемент <math>p</math> простой и <math>p=ab,</math> то по определению простого элемента один из сомножителей, пусть это будет <math>a,</math> делится на <math>p,</math> то есть <math>a=pq.</math> Тогда <math>p=ab=pqb</math> или, сокращая на <math>p</math> (в области целостности сокращение ненулевого множителя всегда возможно): <math>1=qb,</math> то есть <math>b</math> является делителем единицы. {{ЧТД}}

Обратное, вообще говоря, неверно, неприводимый элемент может не быть простым, если кольцо не является факториальным. Пример<ref>''William W. Adams, Larry Joel Goldstein'' (1976), Introduction to Number Theory, p. 250, Prentice-Hall, Inc., {{ISBN|0-13-491282-9}}</ref>: рассмотрим кольцо чисел вида <math>a+b\sqrt{5}i,</math> где <math>a,b</math> — целые числа. Число 3 в нём неприводимо, так как у него только 4 делителя: <math>3, 1, -3, -1</math>. Однако оно не является простым элементом, в чём убеждает равенство:
:<math>\left(2 + \sqrt{5}i\right)\left(2 - \sqrt{5}i\right)=9</math>
Число 3 делит правую часть равенства, но не делит ни одного из сомножителей. Можно из этого факта сделать вывод, что рассмотренное кольцо не факториально; и в самом деле, равенство <math>6 = 2\cdot 3 = (1 - i \sqrt{5}) (1 + i \sqrt{5})</math> показывает, что разложение на неприводимые множители в этом кольце не однозначно.

=== Примеры ===
Кольцо [[Целое число|целых чисел]] факториально. В нём, как уже упоминалось выше, два делителя единицы.

==== Гауссовы целые числа ====
Кольцо [[Гауссовы целые числа|гауссовых чисел]] состоит из [[Комплексное число|комплексных чисел]] вида <math>a+bi,</math> где <math>a,b</math> — целые числа. Делителей единицы четыре: <math>1; -1; i; -i.</math> Это кольцо факториально, неприводимыми элементами являются часть обычных простых чисел и «простые гауссовы» (например, <math>1+i</math>). См. [[Гауссовы целые числа#Критерий Гаусса|критерий простоты гауссова числа]].

Пример разложения для числа 2, которое в кольце гауссовых чисел не является простым: <math>2=(1+i)(1-i)=i(1-i) (1-i)</math> — неединственность разложения здесь кажущаяся, поскольку <math>1-i</math> ассоциирована с <math>1+i</math>, согласно равенству: <math>1-i=(-i)(1+i).</math>

==== Целые числа Эйзенштейна ====
Кольцо [[Целые числа Эйзенштейна|целых чисел Эйзенштейна]] <math>\Z[\omega]</math> состоит из комплексных чисел следующего вида<ref name=":14">[http://mathworld.wolfram.com/EisensteinInteger.html Eisenstein Integer--from MathWorld]</ref>:

: <math>z = a + b\omega,</math> где <math>a,b</math> — целые числа, <math>\omega = \frac{1}{2}(-1 + i\sqrt 3) = e^{2\pi i/3}</math> ([[Корни из единицы|кубический корень из единицы]]),

В этом кольце шесть делителей единицы: (±1, ±ω, ±ω<sup>2</sup>), оно евклидово и поэтому факториально. Неприводимые элементы (они же простые элементы) кольца называются простыми числами Эйзенштейна.

'''Критерий простоты''': целое число Эйзенштейна <math>z = a + b\omega</math> является простым числом Эйзенштейна тогда и только тогда, когда выполняется одно из следующих взаимоисключающих условий:
# <math>z</math> ассоциировано с натуральным простым числом вида <math>3n-1.</math>
# <math>|z|^2 = a^2 - ab + b^2</math> (норма <math>z</math>) является натуральным простым вида <math>3n</math> или <math>3n+1</math>.
Отсюда следует, что норма любого целого числа Эйзенштейна является либо простым натуральным числом, либо квадратом простого натурального числа<ref name=":14" />.

Числа, ассоциированные или комплексно-сопряжённые с простыми числами Эйзенштейна, также являются простыми числами Эйзенштейна.

==== Кольцо многочленов ====
Большое значение в алгебре имеет [[кольцо многочленов]] <math>K[x]</math>, образованное [[многочлен]]ами с коэффициентами из некоторого кольца <math>K.</math> Делителями единицы являются здесь ненулевые константы (как многочлены нулевой степени). Кольцо многочленов евклидово и поэтому факториально. Если в качестве <math>K</math> взять поле [[Вещественное число|вещественных чисел]], то неприводимыми будут все многочлены 1-й степени и те многочлены 2-й степени, у которых [[дискриминант]] отрицателен.

== См. также ==
* [[Незаконное простое число]]
* [[Суперпростое число]]
* [[Полупростое число]]
* [[Примориал]]
* [[Простые числа, отличающиеся на шесть]]
* [[Случайное простое число]]
* [[Составное число]]
* [[Список простых чисел]]
* [[Уникальное простое]]

== Примечания ==
{{примечания|30em}}

== Литература ==
* {{книга |автор=[[Ван дер Варден, Бартель Леендерт|Ван дер Варден]]. |ref=Ван дер Варден
  |заглавие=Алгебра. Определения, теоремы, формулы
  |место=СПб. |издательство=Лань |год=2004 |страниц=624 |isbn=5-8114-0552-9 }}
* {{книга |автор=Василенко О. Н. |заглавие=Теоретико-числовые алгоритмы в криптографии |место=М. |издательство=[[МЦНМО]] |год=2003 |страниц=328 |isbn=5-94057-103-4 |ссылка=http://www.ict.edu.ru/ft/002416/book.pdf }} {{Wayback|url=http://www.ict.edu.ru/ft/002416/book.pdf |date=20070127053816 }}
* {{source|Q21789820|ref=Винберг}}
* {{статья |автор=Гальперин Г. |заглавие=Просто о простых числах |издание=[[Квант (журнал)|Квант]] |номер=4 |year=1987 |страницы=9—14,38 |ссылка=http://kvant.mccme.ru/1987/04/prosto_o_prostyh_chislah.htm}}
* {{книга |автор = Генри С. Уоррен, мл. |заглавие = Алгоритмические трюки для программистов |часть = Глава 16. Формулы для простых чисел |оригинал = Hacker's Delight|ссылка = |isbn = 0-201-91465-4|страниц = 288|год = 2007|место =  М.|издательство = «Вильямс»}}
* {{статья |ссылка=http://www.nkj.ru/archive/articles/17984/ |автор=Карпушина Н. |заглавие=Палиндромы и «перевёртыши» среди простых чисел |издание=[[Наука и жизнь]] |номер=5 |год=2010 |язык=ru }}
* {{книга |автор=[[Кордемский, Борис Анастасьевич|Кордемский Б. А.]] |заглавие=Математическая смекалка |место=М. |издательство=ГИФМЛ |год=1958 |страниц=576 |ссылка=http://ilib.mccme.ru/djvu/klassik/smekalka.htm}}
* {{Книга|автор=Кормен Т., Лейзер Ч.|часть=Глава 33.8. Проверка чисел на простоту|заглавие=Алгоритмы. Построение и анализ|ссылка=http://www.proklondike.com/books/thalg/kormen_leiser_algorith.html|место=М.|издательство=МЦНМО|год=2002| страницы=765—772|isbn=5-900916-37-5}}
* {{книга |автор= [[Крэндалл, Ричард|Крэндалл Р.]], [[Померанс, Карл|Померанс К.]] |часть= |ссылка часть= |заглавие=Простые числа. Криптографические и вычислительные аспекты |оригинал=Prime Numbers: A Computational Perspective |ссылка= |викитека= |ответственный= |издание= |место=М. |издательство=[[Эдиториал УРСС|УРСС]], Либроком |год=2011 |том= |страницы= |страниц=664 |серия= |isbn=978-5-397-02060-2 |тираж=}}
* {{книга |автор=Курош А. Г. .|заглавие=Лекции по общей алгебре |издание=2-е изд. |место= |издательство=Наука
  |год=1973 |ref=Курош}}
* {{книга |автор=Ленг С. |заглавие=Алгебра |место=М. |издательство=Мир |год=1967 |ref=Ленг}}
* {{статья |автор=[[Матиясевич, Юрий Владимирович|Матиясевич Ю.]]. |заглавие=Формулы для простых чисел |издание=[[Квант (журнал)|Квант]] |год=1975 |номер=5 |страницы=5—13 |ссылка=http://kvant.mccme.ru/1975/05/formuly_dlya_prostyh_chisel.htm}}
* {{книга |автор=[[Нестеренко, Юрий Валентинович|Нестеренко Ю. В.]] |часть=[http://nature.web.ru/db/msg.html?mid=1157083&uri=node28.html Алгоритмические проблемы теории чисел] |заглавие=Введение в криптографию |ответственный=Под редакцией В. В. Ященко |год=2001 |издательство=Питер |isbn=5-318-00443-1 |страниц=288 |ссылка=http://nature.web.ru/db/msg.html?mid=1157083&uri=book.html}}
* {{книга |ответственный = Сост. А. П. Савин |заглавие = Энциклопедический словарь юного математика |место = М. |издательство = [[Педагогика (издательство)|Педагогика]] |год = 1985 |страниц = 352 |часть = Простое число |страницы * {{статья |автор=Цагер Д. |заглавие=Первые 50 миллионов простых чисел |издание=[[Успехи математических наук]] |том=39 |номер=6(240) |год=1984 |страницы=175—190 |ссылка=http://mi.mathnet.ru/umn2506 |язык=ru |издательство=[[Математический институт имени В. А. Стеклова РАН|Российская академия наук]] }}
* {{книга|автор=Черёмушкин А. В.|заглавие=Лекции по арифметическим алгоритмам в криптографии|место=М.|издательство=[[МЦНМО]]|год=2002 |страниц=104|isbn=5-94057-060-7 |ссылка=http://www.ict.edu.ru/ft/002419/cherem.pdf|тираж=2000|archiveurl=https://web.archive.org/web/20130531134702/http://www.ict.edu.ru/ft/002419/cherem.pdf|archivedate=2013-05-31|url=http://www.ict.edu.ru/ft/002419/cherem.pdf}}.
= 262—263 |ref = Энциклопедический словарь юного математика}}
* {{книга |автор = Энрике Грасиан |заглавие = Простые числа. Долгая дорога к бесконечности |серия = Мир математики |том = 3 |издательство = Де Агостини |страниц = 148 |год = 2014 |isbn = 978-5-9774-0682-6 |isbn2 = 978-5-9774-0637-6}}
* {{source|Q27209155|ref=Bakhtiari, Maarof|ref-year=2012}}
* {{Книга|автор=Crandall R., Pomerance C.|часть=Глава 3. «Recognizing Primes and Composites». Глава 4. «Primality Proving»|страницы=117—224|заглавие=Prime Numbers: A Computational Perspective|ссылка=http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf|издательство=Springer|год=2005|isbn=0-387-25282-7}}

== Ссылки ==
* ''Кноп К.'' [https://web.archive.org/web/20080319163127/http://www.geocities.com/CapeCanaveral/4344/211.html В погоне за простотой].
* [http://primes.utm.edu/ The Prime Pages]{{ref-en}} — база данных наибольших известных простых чисел {{ref-en}}.
* [http://www.polprimos.com Геометрия простых и совершенных чисел] {{ref-es}}.
* [http://www.jasondavies.com/primos/ Скрипт визуализации]

{{Библиоинформация}}
{{Числа}}
{{Числа по характеристикам делимости}}

[[Категория:Теория чисел]]
[[Категория:Целочисленные последовательности]]
[[Категория:Теория простых чисел|*]]
[[Категория:Делимость и остатки]]