простое число

Число, делящееся только на 1 или само на себя

Составные числа можно расположить в прямоугольники , а простые числа — нет.

Простое число (или простое число ) — это натуральное число больше 1, которое не является произведением двух меньших натуральных чисел. Натуральное число больше 1, которое не является простым, называется составным числом . Например, число 5 является простым, потому что единственные способы записи его в виде произведения, 1 × 5 или 5 × 1 , включают в себя само число 5. Однако число 4 является составным, поскольку оно представляет собой произведение (2 × 2), в котором оба числа меньше 4. Простые числа занимают центральное место в теории чисел из-за фундаментальной теоремы арифметики : каждое натуральное число, большее 1, либо само является простым, либо можно факторизовать как произведение простых чисел, уникальное в пределах их порядка.

Свойство быть простым называется простотой . Простой, но медленный метод проверки простоты заданного числа , называемый пробным делением , проверяет, является ли оно кратным любому целому числу от 2 до . Более быстрые алгоритмы включают тест на простоту Миллера-Рабина , который работает быстро, но имеет небольшую вероятность ошибки, и тест на простоту AKS , который всегда дает правильный ответ за полиномиальное время , но слишком медленный, чтобы быть практичным. Особенно быстрые методы доступны для чисел специальных форм, например чисел Мерсенна . По состоянию на декабрь 2018 года самым большим известным простым числом является простое число Мерсенна с 24 862 048 десятичными цифрами . ^[1] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$^{[обновлять]}

Простых чисел бесконечно много , как показал Евклид около 300 г. до н.э. Ни одна известная простая формула не отделяет простые числа от составных чисел. Однако распределение простых чисел внутри натуральных чисел в целом можно смоделировать статистически. Первым результатом в этом направлении является теорема о простых числах , доказанная в конце XIX века, которая гласит, что вероятность того , что случайно выбранное большое число окажется простым, обратно пропорциональна количеству его цифр, то есть его логарифму .

Некоторые исторические вопросы, касающиеся простых чисел, до сих пор не решены. К ним относятся гипотеза Гольдбаха о том, что каждое четное целое число, большее 2, можно выразить как сумму двух простых чисел, и гипотеза о простых числах-близнецах , согласно которой существует бесконечно много пар простых чисел, отличающихся на два. Такие вопросы стимулировали развитие различных разделов теории чисел, сосредоточив внимание на аналитических или алгебраических аспектах чисел. Простые числа используются в нескольких процедурах в информационных технологиях , таких как криптография с открытым ключом , которая основана на сложности разложения больших чисел на их простые множители. В абстрактной алгебре объекты, которые ведут себя обобщенно, как простые числа, включают простые элементы и простые идеалы .

Определение и примеры

Натуральное число (1, 2, 3, 4, 5, 6 и т. д.) называется простым числом (или простым числом ), если оно больше 1 и не может быть записано в виде произведения двух меньших натуральных чисел. Числа больше 1, которые не являются простыми, называются составными числами . ^[2] Другими словами, является простым, если элементы не могут быть разделены на более мелкие группы одинакового размера, состоящие из более чем одного элемента, ^[3] или если невозможно расположить точки в прямоугольной сетке шириной более одной точки. и высотой более одной точки. ^[4] Например, среди чисел от 1 до 6 числа 2, 3 и 5 являются простыми числами, ^[5] поскольку не существует других чисел, которые делят их поровну (без остатка). 1 не является простым, поскольку это специально исключено из определения. 4 = 2 × 2 и 6 = 2 × 3 являются составными. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Демонстрация с помощью палочек Кюизенера того, что 7 — простое число, потому что ни одно из 2, 3, 4, 5 или 6 не делит его поровну.

Делители натурального числа – это натуральные числа, которые делятся без остатка. Каждое натуральное число имеет в качестве делителя и 1, и само себя. Если у него есть какой-либо другой делитель, он не может быть простым. Это приводит к эквивалентному определению простых чисел: это числа, имеющие ровно два положительных делителя . Эти двое — 1 и само число. Поскольку число 1 само по себе имеет только один делитель, по этому определению оно не является простым. ^[6] Еще один способ выразить то же самое: число является простым, если оно больше единицы и ни одно из чисел не делится без остатка. ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2,3,\dots ,n-1}$ ${\displaystyle n}$

Первые 25 простых чисел (все простые числа меньше 100): ^[8]

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 ( последовательность A000040 в OEIS ).

Никакое четное число больше 2 не является простым, поскольку любое такое число можно выразить как произведение . Следовательно, каждое простое число, кроме 2, является нечетным числом и называется нечетным простым числом . ^[9] Аналогично, при записи в обычной десятичной системе все простые числа больше 5 оканчиваются на 1, 3, 7 или 9. Все числа, оканчивающиеся другими цифрами, являются составными: десятичные числа, оканчивающиеся на 0, 2, 4, 6 или 8 — четные, а десятичные числа, оканчивающиеся на 0 или 5, делятся на 5. ^[10] ${\displaystyle n}$ ${\displaystyle 2\times n/2}$

Множество всех простых чисел иногда обозначается ( жирной заглавной буквой P ) ^[11] или ( жирной заглавной буквой P на доске). ^[12] ${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbb {P} }$

История

Математический папирус Ринда

Математический папирус Ринда , датируемый примерно 1550 годом до нашей эры, содержит египетские дроби различных форм для простых и составных чисел. ^[13] Однако самые ранние сохранившиеся записи об изучении простых чисел исходят от древнегреческих математиков , которые называли их протос арифмос ( πρῶτος ἀριθμὸς ). « Начала » Евклида (ок. 300 г. до н. э.) доказывают бесконечность простых чисел и фундаментальную теорему арифметики , а также показывают, как построить совершенное число из простого числа Мерсенна . ^[14] Другое греческое изобретение, « Решето Эратосфена », до сих пор используется для составления списков простых чисел. ^{[15] [16]}

Около 1000 года нашей эры исламский математик Ибн аль-Хайсам (Альхазен) нашел теорему Вильсона , характеризующую простые числа как числа , которые делятся нацело . Он также предположил, что все даже совершенные числа происходят из конструкции Евклида с использованием простых чисел Мерсенна, но не смог это доказать. ^[17] Другой исламский математик, Ибн аль-Банна аль-Марракуши , заметил, что решето Эратосфена можно ускорить, рассматривая только простые делители до квадратного корня из верхнего предела. ^[16] Фибоначчи принёс инновации исламской математики в Европу. Его книга Liber Abaci (1202 г.) была первой, в которой описано пробное деление для проверки простоты, снова с использованием делителей только до квадратного корня. ^[16] ${\displaystyle n}$ ${\displaystyle (n-1)!+1}$

В 1640 году Пьер де Ферма сформулировал (без доказательства) малую теорему Ферма (позже доказанную Лейбницем и Эйлером ). ^[18] Ферма также исследовал простоту чисел Ферма , ^[19] и Марин Мерсенн изучали простые числа Мерсенна , простые числа формы с самим собой простым числом. ^[20] Кристиан Гольдбах в письме Эйлеру в 1742 году сформулировал гипотезу Гольдбаха о том, что каждое четное число является суммой двух простых чисел. ^[21] Эйлер доказал гипотезу Альхазена (теперь теорему Евклида-Эйлера ) о том, что все четные совершенные числа могут быть построены из простых чисел Мерсенна. ^[14] Он представил методы математического анализа в этой области в своих доказательствах бесконечности простых чисел и расхождения суммы обратных чисел простых чисел . ^[22] В начале 19 века Лежандр и Гаусс предположили, что при стремлении к бесконечности число простых чисел до асимптотично к , где – натуральный логарифм . Более слабым следствием такой высокой плотности простых чисел был постулат Бертрана о том, что для каждого существует простое число между и , доказанный в 1852 году Пафнутием Чебышевым . ^[23] Идеи Бернхарда Римана в его статье 1859 года о дзета-функции набросали схему доказательства гипотезы Лежандра и Гаусса. Хотя тесно связанная с ней гипотеза Римана остается недоказанной, схема Римана была завершена в 1896 году Адамаром и де ла Валле Пуссеном , и результат теперь известен как теорема о простых числах . ^[24] Другим важным результатом 19-го века была теорема Дирихле об арифметических прогрессиях , согласно которой некоторые арифметические прогрессии содержат бесконечное количество простых чисел. ^[25] ${\displaystyle 2^{2^{n}}+1}$ ${\displaystyle 2^{p}-1}$ ${\displaystyle p}$ ${\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x/\log x}$ ${\displaystyle \log x}$ ${\displaystyle x}$ ${\displaystyle n>1}$ ${\displaystyle n}$ ${\displaystyle 2n}$

Многие математики работали над тестами на простоту чисел, больших, чем те, для которых практически применимо пробное деление. Методы, которые ограничены конкретными числовыми формами, включают тест Пепина для чисел Ферма (1877 г.), ^[26] теорему Прота (ок. 1878 г.), ^[27] тест простоты Лукаса -Лемера (возник в 1856 г.) и обобщенный тест простоты Люка . ^[16]

С 1951 года все самые большие известные простые числа были найдены с помощью этих тестов на компьютерах . ^[a] Поиск все больших простых чисел вызвал интерес за пределами математических кругов благодаря Великому поиску простых чисел Мерсенна в Интернете и другим проектам распределенных вычислений . ^{[8] [29]} Идея о том, что простые числа имеют мало применений за пределами чистой математики ^[b], была разрушена в 1970-х годах, когда были изобретены криптография с открытым ключом и криптосистема RSA , в основе которых лежали простые числа. ^[32]

Возросшая практическая значимость компьютеризированного тестирования простоты и факторизации привела к разработке улучшенных методов, способных обрабатывать большое количество неограниченных форм. ^{[15] [33] [34]} Математическая теория простых чисел также продвинулась вперед благодаря теореме Грина-Тао (2004 г.) о том, что существуют сколь угодно длинные арифметические прогрессии простых чисел, и доказательству Итан Чжана в 2013 г., что их существует бесконечно много. простые лакуны ограниченного размера. ^[35]

Первичность одного

Большинство ранних греков даже не считали 1 числом, ^{[36] [37]} , поэтому они не могли принять во внимание его простоту. Некоторые ученые греческой и более поздней римской традиции, в том числе Никомах , Ямвлих , Боэций и Кассиодор , также считали простые числа подразделением нечетных чисел, поэтому они также не считали 2 простым. Однако Евклид и большинство других греческих математиков считали 2 простым числом. Средневековые исламские математики во многом следовали грекам, считая, что единица не является числом. ^[36] В Средние века и эпоху Возрождения математики начали рассматривать 1 как число, а некоторые из них включали его в качестве первого простого числа. ^[38] В середине 18 века Кристиан Гольдбах в своей переписке с Леонардом Эйлером указал 1 как простое число ; однако сам Эйлер не считал 1 простым числом. ^[39] В 19 веке многие математики все еще считали 1 простым числом, ^[40] и списки простых чисел, включающих 1, продолжали публиковаться даже в 1956 году . ^{[41] [42]}

Если бы определение простого числа было изменено, чтобы называть 1 простым, многие утверждения, связанные с простыми числами, пришлось бы переформулировать более неудобно. Например, фундаментальную теорему арифметики необходимо будет перефразировать в терминах факторизации в простые числа, большие 1, потому что каждое число будет иметь несколько факторизаций с любым количеством копий 1. ^[40] Точно так же решето Эратосфена не будет работать. правильно, если бы он обрабатывал 1 как простое число, потому что это исключило бы все кратные 1 (то есть все другие числа) и вывело бы только одно число 1. ^[42] Некоторые другие, более технические свойства простых чисел также не справедливы для число 1: например, формулы для функции Эйлера или для функции суммы делителей для простых чисел отличаются от формул для 1. ^[43] К началу 20-го века математики начали соглашаться с тем, что 1 не следует указывать как число 1. простое, а скорее в своей особой категории как « единица ». ^[40]

Элементарные свойства

Уникальная факторизация

Запись числа в виде произведения простых чисел называется факторизацией числа на простые множители. Например:

${\displaystyle {\begin{aligned}34866&=2\times 3\times 3\times 13\times 149\\&=2\times 3^{2}\times 13\times 149.\end{aligned}}}$

Члены произведения называются простыми факторами . Один и тот же простой множитель может встречаться более одного раза; в этом примере есть две копии простого множителя . Когда простое число встречается несколько раз, возведение в степень можно использовать для группировки нескольких копий одного и того же простого числа: например, во втором способе записи произведения, приведенного выше, обозначает квадрат или вторую степень. из ${\displaystyle 3.}$ ${\displaystyle 3^{2}}$ ${\displaystyle 3.}$

Центральное значение простых чисел для теории чисел и математики в целом вытекает из фундаментальной теоремы арифметики . ^[44] Эта теорема утверждает, что каждое целое число больше 1 можно записать как произведение одного или нескольких простых чисел. Более того, это произведение уникально в том смысле, что любые две факторизации одного и того же числа будут иметь одинаковое количество копий одних и тех же простых чисел, хотя их порядок может различаться. ^[45] Итак, хотя существует много разных способов найти факторизацию с использованием алгоритма факторизации целых чисел , все они должны давать один и тот же результат. Таким образом, простые числа можно считать «основными строительными блоками» натуральных чисел. ^[46]

Некоторые доказательства уникальности простых факторизаций основаны на лемме Евклида : If — простое число, делящее произведение целых чисел , а затем делящее или делящее (или и то, и другое). ^[47] И наоборот, если число обладает свойством, что при делении произведения оно всегда делит хотя бы один множитель произведения, то оно должно быть простым. ^[48] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle ab}$ ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle p}$

Бесконечность

Существует бесконечно много простых чисел. Другой способ сказать это состоит в том, что последовательность

2, 3, 5, 7, 11, 13,...

простых чисел никогда не заканчивается. Это утверждение называется теоремой Евклида в честь древнегреческого математика Евклида , поскольку ему приписывается первое известное доказательство этого утверждения. Известно еще множество доказательств бесконечности простых чисел, включая аналитическое доказательство Эйлера , доказательство Гольдбаха , основанное на числах Ферма , ^{[49] доказательство} Фюрстенберга с использованием общей топологии , ^[50] и элегантное доказательство Куммера . ^[51]

Доказательство Евклида ^[52] показывает, что всякий конечный список простых чисел неполный. Основная идея состоит в том, чтобы перемножить простые числа в любом заданном списке и сложить. Если список состоит из простых чисел, это дает число ${\displaystyle 1.}$ ${\displaystyle p_{1},p_{2},\ldots ,p_{n},}$

${\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}$

По основной теореме имеет простую факторизацию ${\displaystyle N}$

${\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}$

с одним или несколькими простыми делителями. делится без остатка на каждый из этих множителей, но имеет остаток, равный единице, при делении на любое из простых чисел в данном списке, поэтому ни один из простых множителей не может находиться в данном списке. Поскольку не существует конечного списка всех простых чисел, простых чисел должно быть бесконечно много. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

Числа, образованные прибавлением единицы к произведению наименьших простых чисел, называются числами Евклида . ^[53] Первые пять из них простые, а шестой,

${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$

является составным числом.

Формулы для простых чисел

Не существует известной эффективной формулы для простых чисел. Например, не существует непостоянного полинома , даже от нескольких переменных, который принимает только простые значения. ^[54] Однако существует множество выражений, которые кодируют все простые числа или только простые числа. Одна из возможных формул основана на теореме Вильсона и генерирует число 2 много раз, а все остальные простые числа — ровно один раз. ^[55] Существует также набор диофантовых уравнений с девятью переменными и одним параметром, обладающий следующим свойством: параметр является простым тогда и только тогда, когда полученная система уравнений имеет решение над натуральными числами. Это можно использовать для получения единственной формулы, у которой все положительные значения являются простыми. ^[54]

Другие примеры формул, порождающих простые числа, взяты из теоремы Миллса и теоремы Райта . Они утверждают, что существуют действительные константы и такие, что ${\displaystyle A>1}$ ${\displaystyle \mu }$

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$

являются простыми для любого натурального числа в первой формуле и любого числа показателей степени во второй формуле. ^[56] Здесь представлена ​​функция пола , наибольшее целое число, меньшее или равное рассматриваемому числу. Однако они бесполезны для генерации простых чисел, поскольку простые числа должны быть сгенерированы первыми, чтобы вычислить значения или ^[54] ${\displaystyle n}$ ${\displaystyle \lfloor {}\cdot {}\rfloor }$ ${\displaystyle A}$ ${\displaystyle \mu .}$

Открытые вопросы

Было высказано множество гипотез, касающихся простых чисел. Многие из этих гипотез, часто имея элементарную формулировку, десятилетиями выдерживали проверку: все четыре проблемы Ландау 1912 года до сих пор не решены. ^[57] Одной из них является гипотеза Гольдбаха , которая утверждает, что каждое четное целое число больше 2 можно записать в виде суммы двух простых чисел. ^[58] По состоянию на 2014 год эта гипотеза была проверена для всех чисел до ^[59] . Были доказаны более слабые утверждения, чем это, например, теорема Виноградова гласит, что каждое достаточно большое нечетное целое число можно записать в виде суммы трех простых чисел. ^[60] Теорема Чена гласит, что каждое достаточно большое четное число можно выразить как сумму простого и полупростого числа ( произведение двух простых чисел). ^[61] Кроме того, любое четное целое число больше 10 можно записать как сумму шести простых чисел. ^[62] Раздел теории чисел, изучающий подобные вопросы, называется аддитивной теорией чисел . ^[63] ${\displaystyle n}$^[update] ${\displaystyle n=4\cdot 10^{18}.}$

Другой тип проблем касается пробелов в простых числах , различий между последовательными простыми числами. Существование сколь угодно больших пробелов в простых числах можно увидеть, заметив, что последовательность состоит из составных чисел для любого натурального числа ^[64] . Однако большие пробелы в простых числах возникают гораздо раньше, чем показывает этот аргумент. ^[65] Например, первый пробел в простых числах длиной 8 находится между простыми числами 89 и 97, ^[66] намного меньше, чем Предполагается, что существует бесконечно много простых чисел-близнецов , пар простых чисел с разницей 2; это гипотеза о простых числах-близнецах . В более общем плане гипотеза Полиньяка утверждает, что для каждого положительного целого числа существует бесконечно много пар последовательных простых чисел, которые различаются согласно ^[67] гипотезе Андрики , ^[67] гипотезе Брокара , ^[68] гипотезе Лежандра , ^[69] и гипотезе Оппермана ^{[68] —} все они предполагают что самые большие промежутки между простыми числами от до должны быть не более чем приблизительно результатом, который, как известно, следует из гипотезы Римана, в то время как гораздо более сильная гипотеза Крамера устанавливает самый большой размер промежутка в ^[67] . Пробелы между простыми числами могут быть обобщены на простые -кортежи , закономерности различий между более чем двумя простыми числами. Их бесконечность и плотность являются предметом первой гипотезы Харди-Литтлвуда , которая может быть мотивирована эвристикой , согласно которой простые числа ведут себя аналогично случайной последовательности чисел с плотностью, заданной теоремой о простых числах. ^[70] ${\displaystyle n!+2,n!+3,\dots ,n!+n}$ ${\displaystyle n-1}$ ${\displaystyle n.}$ ${\displaystyle 8!=40320.}$ ${\displaystyle k,}$ ${\displaystyle 2k.}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}},}$ ${\displaystyle O((\log n)^{2}).}$ ${\displaystyle k}$

Аналитические свойства

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

Эта область исследований началась с Леонарда Эйлера и его первого крупного результата — решения Базельской проблемы . Задача заключалась в определении значения бесконечной суммы , которую сегодня можно признать значением дзета -функции Римана . Эта функция тесно связана с простыми числами и с одной из наиболее значительных нерешённых проблем математики — гипотезой Римана . Эйлер это показал . ^[71] Обратная величина этого числа, , представляет собой предельную вероятность того, что два случайных числа, выбранных равномерно из большого диапазона, являются относительно простыми (не имеют общих факторов). ^[72] ${\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,}$ ${\displaystyle \zeta (2)}$ ${\displaystyle \zeta (2)=\pi ^{2}/6}$ ${\displaystyle 6/\pi ^{2}}$

Распределение простых чисел в целом, например вопрос, сколько простых чисел меньше заданного большого порога, описывается теоремой о простых числах , но эффективная формула для -го простого числа ${\displaystyle n}$ неизвестна. Теорема Дирихле об арифметических прогрессиях в своей основной форме утверждает, что линейные многочлены

${\displaystyle p(n)=a+bn}$

с относительно простыми целыми числами и принимают бесконечное количество простых значений. Более сильные формы теоремы утверждают, что сумма обратных величин этих простых значений расходится и что разные линейные многочлены с одним и тем же имеют примерно одинаковые пропорции простых чисел. Хотя были сформулированы гипотезы о пропорциях простых чисел в многочленах более высокой степени, они остаются недоказанными, и неизвестно, существует ли квадратичный многочлен, который (для целых аргументов) является простым бесконечно часто. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$

Аналитическое доказательство теоремы Евклида

Доказательство Эйлера о том, что простых чисел бесконечно много, рассматривает суммы обратных простых чисел:

${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}$

Эйлер показал, что для любого произвольного действительного числа существует простое число, для которого эта сумма больше . ^[73] Это показывает, что существует бесконечно много простых чисел, потому что, если бы было конечное число простых чисел, сумма достигла бы своего максимального значения в самом большом простом числе, а не превысила бы каждое . Скорость роста этой суммы точнее описывается второй теоремой Мертенса . ^[74] Для сравнения: сумма ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle x}$

${\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}$

не растет до бесконечности, а уходит в бесконечность (см. Базельскую задачу ). В этом смысле простые числа встречаются чаще, чем квадраты натуральных чисел, хотя оба множества бесконечны. ^[75] Теорема Брюна утверждает, что сумма обратных чисел-близнецов , ${\displaystyle n}$

${\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}$

конечно. Из-за теоремы Брюна невозможно использовать метод Эйлера для решения гипотезы о простых числах-близнецах , согласно которой существует бесконечно много простых чисел-близнецов. ^[75]

Количество простых чисел ниже заданной границы

Относительная ошибка и логарифмический интеграл как приближения к функции подсчета простых чисел . Обе относительные ошибки с ростом уменьшаются до нуля , но для логарифмического интеграла сходимость к нулю происходит гораздо быстрее. ${\displaystyle {\tfrac {n}{\log n}}}$ ${\displaystyle \operatorname {Li} (n)}$ ${\displaystyle n}$

Функция подсчета простых чисел определяется как количество простых чисел, не превышающее . ^[76] Например, , поскольку существует пять простых чисел, меньших или равных 11. Такие методы, как алгоритм Мейселя – Лемера, могут вычислить точные значения быстрее, чем можно было бы перечислить каждое простое число до . ^[77] Теорема о простых числах утверждает, что асимптотика к , которая обозначается как ${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle \pi (11)=5}$ ${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle \pi (n)}$ ${\displaystyle n/\log n}$

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

и означает, что отношение к правой дроби приближается к 1 при стремлении к бесконечности. ^[78] Это означает, что вероятность того, что случайно выбранное число меньше простого, (приблизительно) обратно пропорциональна количеству цифр в . ^[79] Это также означает, что th простое число пропорционально ^[80] и, следовательно, что средний размер простого пробела пропорционален . ^[65] Более точную оценку дает смещенный логарифмический интеграл ^[78] ${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n\log n}$ ${\displaystyle \log n}$ ${\displaystyle \pi (n)}$

${\displaystyle \pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

Арифметические прогрессии

Арифметическая прогрессия — это конечная или бесконечная последовательность чисел, в которой все последовательные числа в этой последовательности имеют одинаковую разницу. ^[81] Эта разница называется модулем прогрессии. ^[82] Например,

3, 12, 21, 30, 39, ...,

— бесконечная арифметическая прогрессия с модулем 9. В арифметической прогрессии все числа имеют одинаковый остаток при делении на модуль; в этом примере остаток равен 3. Поскольку и модуль 9, и остаток 3 кратны 3, то же самое относится и к каждому элементу последовательности. Следовательно, эта прогрессия содержит только одно простое число — саму 3. В общем, бесконечная прогрессия

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

может иметь более одного простого числа только тогда, когда его остаток и модуль относительно просты. Если они относительно простые, теорема Дирихле об арифметических прогрессиях утверждает, что прогрессия содержит бесконечно много простых чисел. ^[83] ${\displaystyle a}$ ${\displaystyle q}$

Простые числа в арифметической прогрессии по модулю 9. В каждом ряду тонкой горизонтальной полосы показана одна из девяти возможных прогрессий по модулю 9, простые числа отмечены красным. Прогрессии чисел 0, 3 или 6 по модулю 9 содержат не более одного простого числа (числа 3); Остальные прогрессии чисел, такие как 2, 4, 5, 7 и 8 по модулю 9, имеют бесконечное количество простых чисел с одинаковым количеством простых чисел в каждой прогрессии.

Теорема Грина–Тао показывает, что существуют конечные арифметические прогрессии произвольной длины, состоящие только из простых чисел. ^{[35] [84]}

Простые значения квадратичных многочленов

Спираль Улама . Простые числа (красные) группируются на некоторых диагоналях, а не на других. Простые значения показаны синим цветом. ${\displaystyle 4n^{2}-2n+41}$

Эйлер заметил, что функция

${\displaystyle n^{2}-n+41}$

дает простые числа для , хотя среди его более поздних значений появляются составные числа. ^{[85] [86]} Поиск объяснения этого явления привел к глубокой алгебраической теории чисел Хегнера и проблеме числа классов . ^[87] Гипотеза Харди-Литтлвуда F предсказывает плотность простых чисел среди значений квадратичных многочленов с целыми коэффициентами в терминах логарифмического интеграла и полиномиальных коэффициентов. Доказано, что ни один квадратичный многочлен не принимает бесконечное количество простых значений. ^[88] ${\displaystyle 1\leq n\leq 40}$

Спираль Улама располагает натуральные числа в двумерной сетке, спиралевидно образуя концентрические квадраты, окружающие начало координат, с выделенными простыми числами. Визуально кажется, что простые числа группируются на определенных диагоналях, а не на других, что позволяет предположить, что некоторые квадратичные многочлены принимают простые значения чаще, чем другие. ^[88]

Дзета-функция и гипотеза Римана

График абсолютных значений дзета-функции, показывающий некоторые ее особенности.

Одним из самых известных нерешенных вопросов математики, датируемым 1859 годом и одной из задач Премии тысячелетия , является гипотеза Римана , которая спрашивает, где расположены нули дзета -функции Римана . Эта функция является аналитической функцией комплексных чисел . Для комплексных чисел с действительной частью больше единицы оно равно как бесконечной сумме всех целых чисел, так и бесконечному произведению простых чисел. ${\displaystyle \zeta (s)}$ ${\displaystyle s}$

${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}$

Это равенство суммы и произведения, открытое Эйлером, называется эйлеровым произведением . ^[89] Произведение Эйлера может быть получено из фундаментальной теоремы арифметики и показывает тесную связь между дзета-функцией и простыми числами. ^[90] Это приводит к другому доказательству того, что существует бесконечно много простых чисел: если бы их было только конечное число, то равенство суммы и произведения также было бы действительным при , но сумма расходилась бы (это гармонический ряд ), а произведение быть конечным, противоречие. ^[91] ${\displaystyle s=1}$ ${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }$

Гипотеза Римана утверждает, что все нули дзета-функции являются либо отрицательными четными числами, либо комплексными числами с действительной частью, равной 1/2. ^[92] Первоначальное доказательство теоремы о простых числах было основано на слабой форме этой гипотезы, согласно которой не существует нулей с вещественной частью, равной 1, ^{[93] [94]} , хотя были найдены и другие, более элементарные доказательства. ^[95] Функция подсчета простых чисел может быть выражена явной формулой Римана как сумма, в которой каждый член происходит от одного из нулей дзета-функции; главным членом этой суммы является логарифмический интеграл, а остальные члены заставляют сумму колебаться выше и ниже основного члена. ^[96] В этом смысле нули определяют, насколько регулярно распределяются простые числа. Если гипотеза Римана верна, эти флуктуации будут небольшими, и асимптотическое распределение простых чисел, заданное теоремой о простых числах, также будет выполняться на гораздо более коротких интервалах (длиной около квадратного корня для интервалов около числа ). ^[94] ${\displaystyle x}$ ${\displaystyle x}$

Абстрактная алгебра

Модульная арифметика и конечные поля

Модульная арифметика модифицирует обычную арифметику, используя только числа для натурального числа, называемого модулем. Любое другое натуральное число можно отобразить в эту систему, заменив его остатком после деления на . ^[97] Модульные суммы, разности и произведения вычисляются путем выполнения той же замены остатком результата обычной суммы, разности или произведения целых чисел. ^[98] Равенство целых чисел соответствует конгруэнтности в модульной арифметике: и конгруэнтны (записано mod ), когда они имеют одинаковый остаток после деления на . ^[99] Однако в этой системе чисел деление на все ненулевые числа возможно тогда и только тогда, когда модуль является простым. Например, если в качестве модуля используется простое число, возможно деление на: , поскольку очистка знаменателей путем умножения обеих частей на дает действительную формулу . Однако при сложном модуле деление на невозможно. Не существует правильного решения : очистка знаменателей путем умножения на приводит к тому, что левая часть становится либо , либо . В терминологии абстрактной алгебры способность осуществлять деление означает, что модулярная арифметика по модулю простого числа образует поле или, точнее, конечное поле , в то время как другие модули дают только кольцо , но не поле. ^[100] ${\displaystyle \{0,1,2,\dots ,n-1\}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\equiv y}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 7}$ ${\displaystyle 3}$ ${\displaystyle 2/3\equiv 3{\bmod {7}}}$ ${\displaystyle 3}$ ${\displaystyle 2\equiv 9{\bmod {7}}}$ ${\displaystyle 6}$ ${\displaystyle 3}$ ${\displaystyle 2/3\equiv x{\bmod {6}}}$ ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle 0}$ ${\displaystyle 3}$

Несколько теорем о простых числах можно сформулировать с помощью модульной арифметики. Например, маленькая теорема Ферма утверждает, что если (mod ), то (mod ). ^[101] Суммируя это по всем вариантам, получаем уравнение ${\displaystyle a\not \equiv 0}$ ${\displaystyle p}$ ${\displaystyle a^{p-1}\equiv 1}$ ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}$

действителен всякий раз, когда является простым. Гипотеза Джуги утверждает, что это уравнение также является достаточным условием для того, чтобы оно было простым. ^[102] Теорема Вильсона утверждает, что целое число является простым тогда и только тогда, когда факториал конгруэнтен mod . Для составного числа это невозможно, поскольку один из его делителей делит и n , и это невозможно. ^[103] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p>1}$ ${\displaystyle (p-1)!}$ ${\displaystyle -1}$ ${\displaystyle p}$ ${\displaystyle \;n=r\cdot s\;}$ ${\displaystyle (n-1)!}$ ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$

p -адические числа

-адический порядок целого числа — это количество копий в простой факторизации . Эту же концепцию можно распространить на целые числа на рациональные числа, определив -адический порядок дроби равным . Тогда -адическое абсолютное значение любого рационального числа определяется как . Умножение целого числа на его -адическое абсолютное значение отменяет факторы при его факторизации, оставляя только другие простые числа. Точно так же, как расстояние между двумя действительными числами можно измерить по абсолютному значению их расстояния, расстояние между двумя рациональными числами можно измерить по их -адическому расстоянию, -адическому абсолютному значению их разности. В этом определении расстояния два числа находятся близко друг к другу (они имеют небольшое расстояние), когда их разница делится на большую степень . Точно так же, как действительные числа могут быть образованы из рациональных чисел и их расстояний, путем добавления дополнительных предельных значений для формирования полного поля , рациональные числа с -адическим расстоянием могут быть расширены до другого полного поля, -адического поля . цифры . ^{[104] [105]} ${\displaystyle p}$ ${\displaystyle \nu _{p}(n)}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle m/n}$ ${\displaystyle \nu _{p}(m)-\nu _{p}(n)}$ ${\displaystyle p}$ ${\displaystyle |q|_{p}}$ ${\displaystyle q}$ ${\displaystyle |q|_{p}=p^{-\nu _{p}(q)}}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

Выведенную из них картину порядка, абсолютного значения и полного поля можно обобщить на поля алгебраических чисел и их оценки (некоторые отображения мультипликативной группы поля в полностью упорядоченную аддитивную группу , называемую также порядками), абсолютные значения ( некоторые мультипликативные отображения поля в действительные числа, называемые также нормами), ^[104] и места (расширения до полных полей , в которых данное поле представляет собой плотное множество , называемые также пополнениями). ^[106] Например , распространение рациональных чисел на действительные числа представляет собой место, в котором расстояние между числами является обычным абсолютным значением их разности. Соответствующим отображением в аддитивной группе будет логарифм абсолютной величины, хотя это не отвечает всем требованиям оценки. Согласно теореме Островского , с точностью до естественного понятия эквивалентности, действительные числа и -адические числа с их порядками и абсолютными значениями являются единственными оценками, абсолютными значениями и местами рациональных чисел. ^[104] Локально -глобальный принцип позволяет решать некоторые проблемы, связанные с рациональными числами, путем объединения решений из каждого места, что еще раз подчеркивает важность простых чисел для теории чисел. ^[107] ${\displaystyle p}$

Простые элементы в кольцах

Простые числа Гаусса с нормой менее 500

Коммутативное кольцо — это алгебраическая структура , в которой определены сложение, вычитание и умножение. Целые числа представляют собой кольцо, а простые числа в целых числах были обобщены на кольца двумя разными способами: простые элементы и неприводимые элементы . Элемент кольца называется простым, если он ненулевой, не имеет мультипликативного обратного (то есть не является единицей ) и удовлетворяет следующему требованию: всякий раз, когда делит произведение двух элементов , он также делит хотя бы один из или . Элемент является несократимым, если он не является ни единицей, ни произведением двух других неединичных элементов. В кольце целых чисел простые и неприводимые элементы образуют один и тот же набор: ${\displaystyle p}$ ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle xy}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.}$

В произвольном кольце все простые элементы неприводимы. Обратное утверждение не справедливо в общем случае, но справедливо для уникальных областей факторизации . ^[108]

Фундаментальная теорема арифметики продолжает выполняться (по определению) в уникальных областях факторизации. Примером такой области являются гауссовы целые числа , кольцо комплексных чисел вида где обозначает мнимую единицу и и являются произвольными целыми числами. Его простые элементы известны как простые числа Гаусса . Не каждое число, которое является простым среди целых чисел, остается простым в гауссовских целых числах; например, число 2 можно записать как произведение двух простых чисел Гаусса и . Рациональные простые числа (простые элементы в целых числах), конгруэнтные 3 по модулю 4, являются гауссовскими простыми числами, а рациональные простые числа, конгруэнтные 1 по модулю 4, таковыми не являются. ^[109] Это следствие теоремы Ферма о суммах двух квадратов , которая утверждает, что нечетное простое число выражается как сумма двух квадратов , и, следовательно, факторизуется как , именно тогда, когда 1 по модулю 4. ^[110] ${\displaystyle \mathbb {Z} [i]}$ ${\displaystyle a+bi}$ ${\displaystyle i}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 1+i}$ ${\displaystyle 1-i}$ ${\displaystyle p}$ ${\displaystyle p=x^{2}+y^{2}}$ ${\displaystyle p=(x+iy)(x-iy)}$ ${\displaystyle p}$

Главные идеалы

Не каждое кольцо является уникальной областью факторизации. Например, в кольце чисел (для целых чисел и ) число имеет две факторизации , где ни один из четырех множителей не может быть уменьшен дальше, поэтому оно не имеет уникальной факторизации. Чтобы распространить уникальную факторизацию на более широкий класс колец, понятие числа можно заменить понятием идеала , подмножества элементов кольца, которое содержит все суммы пар его элементов и все произведения его элементов. элементы с кольцевыми элементами. Первичные идеалы , которые обобщают простые элементы в том смысле, что главный идеал, порожденный простым элементом, является простым идеалом, являются важным инструментом и объектом изучения в коммутативной алгебре , теории алгебраических чисел и алгебраической геометрии . Простыми идеалами кольца целых чисел являются идеалы (0), (2), (3), (5), (7), (11), ... Основная теорема арифметики обобщается на теорему Ласкера – Нётер . , которое выражает каждый идеал в нётеровом коммутативном кольце как пересечение первичных идеалов , которые являются соответствующими обобщениями простых степеней . ^[111] ${\displaystyle a+b{\sqrt {-5}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 21}$ ${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$

Спектр кольца — это геометрическое пространство, точки которого являются простыми идеалами кольца. ^[112] Арифметическая геометрия также извлекает выгоду из этого понятия, и многие концепции существуют как в геометрии, так и в теории чисел. Например, факторизация или ветвление простых идеалов при их переносе в поле расширения — основная проблема алгебраической теории чисел — имеет некоторое сходство с ветвлением в геометрии . Эти концепции могут даже помочь в решении теоретико-числовых вопросов, касающихся исключительно целых чисел. Например, простые идеалы в кольце целых полей квадратичных чисел могут использоваться при доказательстве квадратичной взаимности - утверждения, которое касается существования квадратных корней по модулю целых простых чисел. ^[113] Ранние попытки доказать Великую теорему Ферма привели к введению Куммером регулярных простых чисел , целых простых чисел, связанных с невозможностью однозначной факторизации в круговых целых числах . ^[114] Вопрос о том, сколько целых простых чисел входит в произведение нескольких простых идеалов в поле алгебраических чисел, решается теоремой плотности Чеботарёва , которая (применительно к круговым целым числам) имеет теорему Дирихле о простых числах в арифметических прогрессиях как особый случай. ^[115]

Теория групп

В теории конечных групп из теорем Силова следует , что если степень простого числа делит порядок группы , то в группе есть подгруппа порядка . По теореме Лагранжа любая группа простого порядка является циклической группой , а по теореме Бернсайда любая группа, порядок которой делится только на два простых числа, разрешима . ^[116] ${\displaystyle p^{n}}$ ${\displaystyle p^{n}}$

Вычислительные методы

Малая шестерня в этой сельскохозяйственной технике имеет 13 зубьев, простое число, а средняя — 21, относительно простое число — 13.

Долгое время теория чисел в целом и изучение простых чисел в частности рассматривались как канонический пример чистой математики, не имеющий никаких приложений за пределами математики ^[b] , кроме использования зубьев шестерен с простыми номерами для распределения износа. равномерно. ^[117] В частности, теоретики чисел, такие как британский математик Г.Х. Харди, гордились тем, что выполняли работу, которая не имела абсолютно никакого военного значения. ^[118]

Это представление о чистоте теории чисел было разрушено в 1970-х годах, когда было публично объявлено, что простые числа могут использоваться в качестве основы для создания алгоритмов криптографии с открытым ключом . ^[32] Эти приложения привели к значительному изучению алгоритмов вычислений с простыми числами и, в частности, проверки на простоту , методов определения того, является ли данное число простым. Самая простая процедура проверки простоты — пробное деление — слишком медленная, чтобы быть полезной для больших чисел. Одна группа современных тестов на простоту применима к произвольным числам, тогда как более эффективные тесты доступны для чисел специальных типов. Большинство тестов на простоту лишь показывают, является ли их аргумент простым или нет. Подпрограммы, которые также предоставляют простой множитель составных аргументов (или все его простые множители), называются алгоритмами факторизации . Простые числа также используются при вычислении контрольных сумм , хеш-таблиц и генераторов псевдослучайных чисел .

Пробное подразделение

Самый простой метод проверки простоты данного целого числа называется пробным делением . Этот метод осуществляет деление на каждое целое число от 2 до квадратного корня из . Любое такое целочисленное деление на равномерно считается составным; в противном случае оно является простым. Целые числа, превышающие квадратный корень, проверять не нужно, поскольку всякий раз , когда один из двух множителей и меньше или равен квадратному корню из . Другая оптимизация — проверять только простые числа в качестве факторов в этом диапазоне. ^[119] Например, чтобы проверить, является ли 37 простым, этот метод делит его на простые числа в диапазоне от 2 до , то есть 2, 3 и 5. Каждое деление дает ненулевой остаток, поэтому 37 действительно является простым. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n=a\cdot b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {37}}}$

Хотя этот метод прост в описании, он непрактичен для проверки простоты больших целых чисел, поскольку количество выполняемых им тестов растет экспоненциально в зависимости от количества цифр этих целых чисел. ^[120] Тем не менее, пробное деление по-прежнему используется с меньшим пределом, чем квадратный корень размера делителя, для быстрого обнаружения составных чисел с небольшими коэффициентами, прежде чем использовать более сложные методы для чисел, которые проходят этот фильтр. ^[121]

Сита

Решето Эратосфена начинается с неотмеченных цифр (серого цвета). Он неоднократно находит первое немаркированное число, помечает его как простое (темные цвета) и отмечает его квадрат и все последующие кратные как составные (светлые цвета). После маркировки чисел, кратных 2 (красный), 3 (зеленый), 5 (синий) и 7 (желтый), все простые числа до квадратного корня из размера таблицы были обработаны, а все оставшиеся неотмеченные числа (11, 13) и т. д.) отмечены штрихами (пурпурным).

До появления компьютеров обычно печатались математические таблицы , в которых перечислялись все простые числа или их факторизации до заданного предела. ^[122] Самый старый метод создания списка простых чисел называется решетом Эратосфена. ^[123] На анимации показан оптимизированный вариант этого метода. ^[124] Другой, более асимптотически эффективный метод просеивания для той же задачи — это решето Аткина . ^[125] В высшей математике теория решета применяет аналогичные методы к другим задачам. ^[126]

Тестирование на простоту против доказательства простоты

Некоторые из самых быстрых современных тестов на то, является ли произвольное заданное число простым, представляют собой вероятностные алгоритмы (или алгоритмы Монте-Карло ), что означает, что они имеют небольшой случайный шанс дать неправильный ответ. ^[127] Например, тест Соловея-Штрассена на простоту заданного числа выбирает число случайным образом от до и использует модульное возведение в степень , чтобы проверить, делится ли оно на . ^[c] Если да, то он отвечает «да», в противном случае — «нет». Если действительно простое число, оно всегда ответит «да», но если оно составное, то оно ответит «да» с вероятностью не более 1/2 и «нет» с вероятностью не менее 1/2. ^[128] Если этот тест повторяется несколько раз для одного и того же числа, вероятность того, что составное число сможет пройти тест каждый раз, не превышает . Поскольку это значение экспоненциально уменьшается с увеличением количества тестов, это обеспечивает высокую уверенность (хотя и не уверенность) в том, что число, прошедшее повторный тест, является простым. С другой стороны, если тест когда-либо провалится, то число, безусловно, будет составным. ^[129] Составное число, которое проходит такой тест, называется псевдопростым . ^[128] ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle 2}$ ${\displaystyle p-2}$ ${\displaystyle a^{(p-1)/2}\pm 1}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle 1/2^{n}}$

Напротив, некоторые другие алгоритмы гарантируют, что их ответ всегда будет правильным: простые числа всегда будут определяться как простые, а сложные числа всегда будут определяться как составные. Например, это справедливо для пробного деления. Алгоритмы с гарантированно правильным результатом включают как детерминированные (неслучайные) алгоритмы, такие как тест простоты AKS ^[130] , так и рандомизированные алгоритмы Лас-Вегаса , в которых случайный выбор, сделанный алгоритмом, не влияет на его окончательный ответ, например, некоторые варианты доказательства простоты эллиптических кривых . ^[127] Когда метод эллиптической кривой приходит к выводу, что число является простым, он предоставляет сертификат простоты , который можно быстро проверить. ^[131] Тест на простоту эллиптической кривой является самым быстрым на практике из гарантированно правильных тестов на простоту, но его анализ во время выполнения основан на эвристических аргументах , а не на строгих доказательствах. Тест простоты AKS имеет математически доказанную временную сложность, но на практике он медленнее, чем проверка простоты эллиптической кривой. ^[132] Эти методы можно использовать для генерации больших случайных простых чисел путем генерации и проверки случайных чисел до тех пор, пока не будет найдено простое число; при этом более быстрый вероятностный тест может быстро исключить большинство составных чисел, прежде чем будет использован гарантированно правильный алгоритм для проверки того, что оставшиеся числа являются простыми. ^[д]

В следующей таблице перечислены некоторые из этих тестов. Время их работы выражается в количестве проверяемых алгоритмов, а для вероятностных алгоритмов — в количестве выполненных тестов. Более того, — сколь угодно малое положительное число, а log — логарифм по неопределенному основанию. Большое обозначение O означает, что каждую временную границу следует умножить на постоянный коэффициент , чтобы преобразовать ее из безразмерных единиц в единицы времени; этот фактор зависит от деталей реализации, таких как тип компьютера, используемого для запуска алгоритма, но не от входных параметров и . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon }$ ${\displaystyle n}$ ${\displaystyle k}$

Алгоритмы специального назначения и самое большое известное простое число

В дополнение к вышеупомянутым тестам, применимым к любому натуральному числу, некоторые числа специального вида можно проверить на простоту быстрее. Например, тест на простоту Лукаса-Лемера может детерминированно определить, является ли число Мерсенна (на единицу меньше степени двойки ) простым, за то же время, что и одна итерация теста Миллера-Рабина. ^[137] Вот почему с 1992 года (по состоянию на декабрь 2018 года ^[update]) самым большим известным простым числом всегда было простое число Мерсенна. ^[138] Предполагается, что существует бесконечно много простых чисел Мерсенна. ^[139]

В следующей таблице приведены самые большие известные простые числа различных типов. Некоторые из этих простых чисел были найдены с помощью распределенных вычислений . В 2009 году проект Great Internet Mersenne Prime Search был награжден премией в размере 100 000 долларов США за первое обнаружение простого числа, содержащего не менее 10 миллионов цифр. ^[140] Фонд Electronic Frontier Foundation также предлагает 150 000 и 250 000 долларов США за простые числа, содержащие не менее 100 миллионов цифр и 1 миллиард цифр соответственно. ^[141]

Целочисленная факторизация

Для составного целого числа задача получения одного (или всех) простых множителей называется факторизацией . Это значительно сложнее, чем проверка на простоту, ^[148] и, хотя известно множество алгоритмов факторизации, они медленнее, чем самые быстрые методы проверки на простоту. Пробное деление и ро-алгоритм Полларда можно использовать для нахождения очень малых коэффициентов , ^[121] , а факторизация эллиптической кривой может быть эффективной, когда коэффициенты имеют умеренный размер. ^[149] Методы, подходящие для произвольно больших чисел, которые не зависят от размера его факторов, включают квадратичное решето и решето общего числового поля . Как и при тестировании на простоту, существуют также алгоритмы факторизации, которые требуют, чтобы их входные данные имели специальную форму, включая решето специального числового поля . ^[150] По состоянию на декабрь 2019 года самое большое число, которое, как известно, было факторизовано с помощью алгоритма общего назначения, - это RSA-240 , которое имеет 240 десятичных цифр (795 бит) и является произведением двух больших простых чисел. ^[151] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$^[update]

Алгоритм Шора может факторизовать любое целое число за полиномиальное число шагов на квантовом компьютере . ^[152] Однако современные технологии позволяют использовать этот алгоритм только для очень небольших чисел. По состоянию на октябрь 2012 года ^[update]наибольшее число, учтенное квантовым компьютером с помощью алгоритма Шора, составляет 21. ^[153]

Другие вычислительные приложения

Некоторые алгоритмы криптографии с открытым ключом , такие как RSA и обмен ключами Диффи-Хеллмана , основаны на больших простых числах ( обычно 2048- битные простые числа). ^[154] RSA опирается на предположение, что гораздо проще (то есть более эффективно) выполнить умножение двух (больших) чисел и чем вычислить и (предполагается взаимно простым ), если известно только произведение . ^[32] Обмен ключами Диффи-Хеллмана основан на том факте, что существуют эффективные алгоритмы модульного возведения в степень (вычисления ), в то время как обратная операция ( дискретный логарифм ) считается сложной проблемой. ^[155] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xy}$ ${\displaystyle a^{b}{\bmod {c}}}$

Простые числа часто используются для хеш-таблиц . Например, оригинальный метод Картера и Вегмана для универсального хеширования был основан на вычислении хеш-функций путем выбора случайных линейных функций по модулю больших простых чисел. Картер и Вегман обобщили этот метод на -независимое хеширование , используя полиномы более высокой степени, опять же по модулю больших простых чисел. ^[156] Как и в хеш-функции, простые числа используются для размера хеш-таблицы в хеш-таблицах на основе квадратичного зондирования , чтобы гарантировать, что пробная последовательность покрывает всю таблицу. ^[157] ${\displaystyle k}$

Некоторые методы контрольной суммы основаны на математике простых чисел. Например, контрольные суммы, используемые в международных стандартных книжных номерах, определяются путем взятия оставшейся части числа по модулю 11, простого числа. Поскольку 11 — простое число, этот метод может обнаруживать как однозначные ошибки, так и перестановки соседних цифр. ^[158] Другой метод контрольной суммы, Adler-32 , использует арифметику по модулю 65521, наибольшее простое число меньше . ^[159] Простые числа также используются в генераторах псевдослучайных чисел , включая линейные конгруэнтные генераторы ^[160] и « Твистер Мерсенна» . ^[161] ${\displaystyle 2^{16}}$

Другие приложения

Простые числа имеют центральное значение для теории чисел, но также имеют множество приложений в других областях математики, включая абстрактную алгебру и элементарную геометрию. Например, можно разместить простые числа точек в двумерной сетке так, чтобы никакие три точки не находились на линии , или чтобы каждый треугольник, образованный тремя точками, имел большую площадь . ^[162] Другим примером является критерий Эйзенштейна , тест на то, является ли многочлен неприводимым , основанный на делимости его коэффициентов на простое число и его квадрат. ^[163]

Связная сумма двух простых узлов

Понятие простого числа настолько важно, что в разных разделах математики оно по-разному обобщалось. Обычно слово «простое» указывает на минимальность или неразложимость в соответствующем смысле. Например, простое поле данного поля — это его наименьшее подполе, содержащее как 0, так и 1. Это либо поле рациональных чисел, либо конечное поле с простым числом элементов, откуда и происходит название. ^[164] Часто при использовании слова «простой» подразумевается второе, дополнительное значение, а именно, что любой объект может быть, по существу, однозначно разложен на его простые компоненты. Например, в теории узлов простой узел — это узел , который неразложим в том смысле, что его нельзя записать как связную сумму двух нетривиальных узлов. Любой узел можно однозначно выразить как связную сумму простых узлов. ^[165] Еще одним примером такого типа является простое разложение трехмерных многообразий . ^[166]

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

Конструируемые многоугольники и разбиения многоугольников

Построение правильного пятиугольника с помощью линейки и циркуля. Это возможно только потому, что 5 — простое число Ферма .

Простые числа Ферма - это простые числа вида

${\displaystyle F_{k}=2^{2^{k}}+1,}$

с неотрицательным целым числом . ^[167] Они названы в честь Пьера Ферма , который предположил, что все такие числа являются простыми. Первые пять из этих чисел – 3, 5, 17, 257 и 65 537 – являются простыми, [ ^168] но составными, как и все остальные числа Ферма, проверенные по состоянию на 2017 год. ^[169] Правильный -угольник — это можно построить с помощью линейки и циркуля тогда и только тогда, когда нечетные простые множители (если таковые имеются) являются различными простыми числами Ферма. ^[168] Аналогично, правильный -угольник может быть построен с использованием линейки, циркуля и трисектора угла тогда и только тогда, когда простые множители представляют собой любое количество копий 2 или 3 вместе с (возможно, пустым) набором различных простых чисел Пьерпона. , простые числа формы . ^[170] ${\displaystyle k}$ ${\displaystyle F_{5}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{a}3^{b}+1}$

Можно разбить любой выпуклый многоугольник на меньшие выпуклые многоугольники равной площади и равного периметра, когда – степень простого числа , но для других значений это неизвестно . ^[171] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Квантовая механика

Начиная с работ Хью Монтгомери и Фримена Дайсона в 1970-х годах, математики и физики предположили, что нули дзета-функции Римана связаны с энергетическими уровнями квантовых систем . ^{[172] [173]} Простые числа также играют важную роль в квантовой информатике благодаря математическим структурам, таким как взаимно несмещенные основания и симметричные информационно полные меры с положительным операторным значением . ^{[174] [175]}

Биология

Эволюционная стратегия, используемая цикадами рода Magicicada , использует простые числа. ^[176] Эти насекомые проводят большую часть своей жизни в виде личинок под землей. Они только окукливаются, а затем выходят из своих нор через 7, 13 или 17 лет, после чего летают, размножаются, а затем умирают максимум через несколько недель. Биологи предполагают, что продолжительность цикла размножения с простыми числами возникла для того, чтобы не дать хищникам синхронизироваться с этими циклами. ^{[177] [178]} Напротив, предполагается, что многолетние периоды между цветением бамбуковых растений представляют собой гладкие числа , имеющие только небольшие простые числа в своих факторизациях. ^[179]

Искусство и литература

Простые числа оказали влияние на многих художников и писателей. Французский композитор Оливье Мессиан использовал простые числа для создания метрической музыки посредством «природных явлений». В таких работах, как «Нативите сеньора » (1935) и «Четыре этюда ритма» (1949–50), он одновременно использует мотивы, длина которых определяется разными простыми числами, для создания непредсказуемых ритмов: простые числа 41, 43, 47 и 53 появляются в третий этюд «Ритмические стихи». По словам Мессиана, этот способ сочинения был «вдохновлен движениями природы, движениями свободной и неравной продолжительности». ^[180]

В своем научно-фантастическом романе «Контакт» ученый Карл Саган предположил, что факторизация простых чисел может использоваться как средство установления двумерных плоскостей изображения при общении с инопланетянами. Эту идею он впервые неофициально разработал вместе с американским астрономом Фрэнком Дрейком в 1975 году. ^{[181] В} романе Марка Хэддона «Загадочное ночное происшествие с собакой» рассказчик упорядочивает части истории последовательными простыми числами, чтобы передать психическое состояние главного героя, математически одаренного подростка с синдромом Аспергера . синдром . ^[182] Простые числа используются как метафора одиночества и изоляции в романе Паоло Джордано « Одиночество простых чисел» , в котором они изображаются как «аутсайдеры» среди целых чисел. ^[183]

Примечания

1. 44-значное простое число, найденное в 1951 году Эме Феррье с помощью механического калькулятора, остается самым большим простым числом, которое не было найдено с помощью электронных компьютеров. ^[28]
2. Например, Бейлер пишет, что теоретик чисел Эрнст Куммер любил свои идеальные числа , тесно связанные с простыми числами, «потому что они не запятнали себя какими-либо практическими приложениями», ^[30] , а Кац пишет, что Эдмунд Ландау , известный своими работами о распределении простых чисел «ненавидел практические применения математики» и по этой причине избегал таких предметов, как геометрия , которые уже показали себя полезными. ^[31]
3. В этом тесте термин отрицательный, если является квадратом по модулю заданного (предполагаемого) простого числа , и положительный в противном случае. В более общем смысле, для непростых значений термин представляет собой (отрицаемый) символ Якоби , который можно вычислить с использованием квадратичной взаимности . ${\displaystyle \pm 1}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \pm 1}$
4. Действительно, большая часть анализа доказательства простоты эллиптических кривых основана на предположении, что входные данные алгоритма уже прошли вероятностный тест. ^[131]
5. Первичная функция , обозначаемая , дает произведение простых чисел до , а первичное простое число является простым числом одной из форм . ^[145] ${\displaystyle n}$ ${\displaystyle n\#}$ ${\displaystyle n}$ ${\displaystyle n\#\pm 1}$

Рекомендации

1. «Проект GIMPS обнаружил самое большое известное простое число: 282 589 933-1» . Мерсенн Рисерч, Инк . 21 декабря 2018 года . Проверено 21 декабря 2018 г.
2. Гардинер, Энтони (1997). Справочник по математическим олимпиадам: введение в решение задач на основе первых 32 британских математических олимпиад 1965–1996 годов . Издательство Оксфордского университета. п. 26. ISBN 978-0-19-850105-3.
3. Хендерсон, Энн (2014). Дислексия, дискалькулия и математика: практическое руководство (2-е изд.). Рутледж. п. 62. ИСБН 978-1-136-63662-2.
4. Адлер, Ирвинг (1960). Гигантская золотая книга по математике: исследование мира чисел и пространства . Золотая Пресса. п. 16. ОСЛК  6975809.
5. Лефф, Лоуренс С. (2000). Рабочая тетрадь по математике для SAT I. Образовательная серия Бэррона. п. 360. ИСБН 978-0-7641-0768-9.
6. Дадли, Андервуд (1978). «Раздел 2: Уникальная факторизация». Элементарная теория чисел (2-е изд.). WH Freeman and Co. p. 10. ISBN 978-0-7167-0076-0.
7. Серпинский, Вацлав (1988). Элементарная теория чисел. Математическая библиотека Северной Голландии. Том. 31 (2-е изд.). Эльзевир. п. 113. ИСБН 978-0-08-096019-7.
8. Циглер, Гюнтер М. (2004). «Великие гонки на рекорды простых чисел». Уведомления Американского математического общества . 51 (4): 414–416. МР  2039814.
9. Стиллвелл, Джон (1997). Числа и геометрия. Тексты для бакалавриата по математике. Спрингер. п. 9. ISBN 978-0-387-98289-2.
10. Серпинский, Вацлав (1964). Подборка задач теории чисел . Нью-Йорк: Макмиллан. п. 40. МР  0170843.
11. Натансон, Мелвин Б. (2000). «Обозначения и соглашения». Элементарные методы теории чисел . Тексты для аспирантов по математике. Том. 195. Спрингер. ISBN 978-0-387-22738-2. МР  1732941.
12. Фатикони, Теодор Г. (2012). Математика бесконечности: Путеводитель по великим идеям. Чистая и прикладная математика: серия текстов, монографий и трактатов Wiley. Том. 111 (2-е изд.). Джон Уайли и сыновья. п. 44. ИСБН 978-1-118-24382-4.
13. Брюинз, Эверт Мари, обзор в Mathematical Reviews of Gillings, RJ (1974). «Лицевая сторона Математического папируса Ринда. Как его приготовил древнеегипетский писец?». Архив истории точных наук . 12 (4): 291–298. дои : 10.1007/BF01307175. MR  0497458. S2CID  121046003.
14. Стиллвелл, Джон (2010). Математика и ее история. Тексты для студентов по математике (3-е изд.). Спрингер. п. 40. ISBN 978-1-4419-6052-8.
15. Померанс, Карл (декабрь 1982 г.). «В поисках простых чисел». Научный американец . 247 (6): 136–147. Бибкод : 1982SciAm.247f.136P. doi : 10.1038/scientificamerican1282-136. JSTOR  24966751.
16. Моллин, Ричард А. (2002). «Краткая история факторинга и тестирования простоты до нашей эры (до компьютеров)». Журнал «Математика» . 75 (1): 18–29. дои : 10.2307/3219180. JSTOR  3219180. МР  2107288.
17. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. «Абу Али аль-Хасан ибн аль-Хайсам». MacTutor Архив истории математики . Университет Сент-Эндрюс .
18. Сандифер 2007, 8. Маленькая теорема Ферма (ноябрь 2003 г.), стр. 45
19. Сандифер, К. Эдвард (2014). Как Эйлер сделал еще больше. Математическая ассоциация Америки. п. 42. ИСБН 978-0-88385-584-3.
20. Коши, Томас (2002). Элементарная теория чисел с приложениями. Академическая пресса. п. 369. ИСБН 978-0-12-421171-1.
21. Юань, Ван (2002). Гипотеза Гольдбаха. Серия по чистой математике. Том. 4 (2-е изд.). Всемирная научная. п. 21. ISBN 978-981-4487-52-8.
22. Наркевич, Владислав (2000). «1.2 Сумма обратных простых чисел». Развитие теории простых чисел: от Евклида до Харди и Литтлвуда . Монографии Спрингера по математике. Спрингер. п. 11. ISBN 978-3-540-66289-1.
23. Чебычев, П. (1852). «Мемуар о премьерных именах» (PDF) . Журнал чистой и прикладной математики . Серия 1 (на французском языке): 366–390.. (Доказательство постулата: 371–382). См. также Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, стр. 15–33, 1854 г.
24. Апостол, Том М. (2000). «Столетняя история теоремы о простых числах». В Бамбе, РП; Думир, ВК; Ханс-Гилл, Р.Дж. (ред.). Теория чисел . Тенденции в математике. Базель: Биркхойзер. стр. 1–14. МР  1764793.
25. Апостол, Том М. (1976). «7. Теорема Дирихле о простых числах в арифметических прогрессиях». Введение в аналитическую теорию чисел . Нью-Йорк; Гейдельберг: Springer-Verlag. стр. 146–156. МР  0434929.
26. Шабер, Жан-Люк (2012). История алгоритмов: от камешка до микрочипа. Спрингер. п. 261. ИСБН 978-3-642-18192-4.
27. Розен, Кеннет Х. (2000). «Теорема 9.20. Тест Прота на простоту». Элементарная теория чисел и ее приложения (4-е изд.). Аддисон-Уэсли. п. 342. ИСБН 978-0-201-87073-2.
28. Купер, С. Барри; Ходжес, Эндрю (2016). Тьюринг «Прошлое и будущее». Издательство Кембриджского университета. стр. 37–38. ISBN 978-1-107-01083-3.
29. Розен 2000, с. 245.
30. Бейлер, Альберт Х. (1999) [1966]. Отдых в теории чисел: Королева математики развлекает. Дувр. п. 2. ISBN 978-0-486-21096-4. ОСЛК  444171535.
31. Кац, Шауль (2004). «Берлинские корни - воплощение сионизма: идеал чистой математики и начало Института математики Эйнштейна в Еврейском университете в Иерусалиме». Наука в контексте . 17 (1–2): 199–234. дои : 10.1017/S0269889704000092. MR  2089305. S2CID  145575536.
32. Kraft, Джеймс С.; Вашингтон, Лоуренс К. (2014). Элементарная теория чисел. Учебники по математике. ЦРК Пресс. п. 7. ISBN 978-1-4987-0269-0.
33. Бауэр, Крейг П. (2013). Тайная история: история криптологии. Дискретная математика и ее приложения. ЦРК Пресс. п. 468. ИСБН 978-1-4665-6186-1.
34. Клее, Виктор ; Вагон, Стэн (1991). Старые и новые нерешенные проблемы плоской геометрии и теории чисел. Математические изложения Дольчиани. Том. 11. Издательство Кембриджского университета. п. 224. ИСБН 978-0-88385-315-3.
35. Neale 2017, стр. 18, 47.
36. Колдуэлл, Крис К.; Реддик, Анджела; Сюн, Йенг; Келлер, Уилфрид (2012). «История первобытности одного: подборка источников». Журнал целочисленных последовательностей . 15 (9): Статья 12.9.8. МР  3005523.Подборку цитат из древнегреческих позиций о статусе 1 и 2 и о них см., в частности, на стр. 3–4. Об исламских математиках см. с. 6.
37. Таран, Леонардо (1981). Спевсипп Афинский: критическое исследование со сборником связанных текстов и комментариев. Philosophia Antiqua: Серия монографий по древней философии. Том. 39. Брилл. стр. 35–38. ISBN 978-90-04-06505-5.
38. Колдуэлл и др. 2012, стр. 7–13. См., в частности, записи о Стевине, Бранкере, Уоллисе и Престете.
39. Колдуэлл и др. 2012, с. 15.
40. Колдуэлл, Крис К.; Сюн, Йенг (2012). «Каково наименьшее простое число?» (PDF) . Журнал целочисленных последовательностей . 15 (9): Статья 12.9.7. МР  3005530.
41. Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Базель, Швейцария: Биркхойзер. п. 36. дои : 10.1007/978-1-4612-0251-6. ISBN 978-0-8176-3743-9. МР  1292250.
42. Конвей, Джон Хортон ; Гай, Ричард К. (1996). Книга чисел . Нью-Йорк: Коперник. стр. 129–130. дои : 10.1007/978-1-4612-4072-3. ISBN 978-0-387-97993-9. МР  1411676.
43. Подробности см. Серпинский 1988, с. 245. О сумме делителей см. Sandifer, C. Edward (2007). Как Эйлер это сделал. МАА Спектр. Математическая ассоциация Америки. п. 59. ИСБН 978-0-88385-563-8.
44. Смит, Карл Дж. (2011). Природа математики (12-е изд.). Cengage Обучение. п. 188. ИСБН 978-0-538-73758-6.
45. Дадли 1978, раздел 2, теорема 2, с. 16; Нил, Вики (2017). Устранение разрыва: стремление понять простые числа . Издательство Оксфордского университета. п. 107. ИСБН 978-0-19-109243-5.
46. дю Сотой, Маркус (2003). Музыка простых чисел: в поисках решения величайшей тайны математики . Харпер Коллинз. п. 23. ISBN 978-0-06-093558-0.
47. Дадли 1978, раздел 2, лемма 5, с. 15; Хиггинс, Питер М. (1998). Математика для любознательных. Издательство Оксфордского университета. стр. 77–78. ISBN 978-0-19-150050-3.
48. Ротман, Джозеф Дж. (2000). Первый курс абстрактной алгебры (2-е изд.). Прентис Холл. Задача 1.40, с. 56. ИСБН 978-0-13-011584-3.
49. Письмо Гольдбаха Эйлеру на латыни , июль 1730 г.
50. Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячник . 62 (5): 353. дои : 10.2307/2307043. JSTOR  2307043. МР  0068566.
51. Рибенбойм, Пауло (2004). Маленькая книга больших простых чисел. Берлин; Нью-Йорк: Springer-Verlag. п. 4. ISBN 978-0-387-20169-6.
52. Элементы Евклида , Книга IX, Предложение 20. См. Английский перевод доказательства Евклида Дэвидом Джойсом или Уильямсон, Джеймс (1782). Элементы Евклида с диссертациями. Оксфорд: Кларендон Пресс . п. 63. ОСЛК  642232959.
53. Варди, Илан (1991). Вычислительные развлечения в системе Mathematica . Аддисон-Уэсли. стр. 82–89. ISBN 978-0-201-52989-0.
54. Матиясевич, Юрий В. (1999). «Формулы простых чисел». Табачников , Серж (ред.). Квант Селекта: Алгебра и анализ . Том. II. Американское математическое общество . стр. 13–24. ISBN 978-0-8218-1915-9.
55. Маккиннон, Ник (июнь 1987 г.). «Формулы простых чисел». Математический вестник . 71 (456): 113–114. дои : 10.2307/3616496. JSTOR  3616496. S2CID  171537609.
56. Райт, EM (1951). «Функция, представляющая простое число». Американский математический ежемесячник . 58 (9): 616–618. дои : 10.2307/2306356. JSTOR  2306356.
57. Гай 2013, с. VII.
58. Гай 2013, гипотеза C1 Гольдбаха, стр. 105–107.
59. Оливейра и Силва, Томас; Херцог, Зигфрид; Парди, Сильвио (2014). «Эмпирическая проверка гипотезы четности Гольдбаха и вычисление пробелов в простых числах до 4 ⋅ 10 18 {\displaystyle 4\cdot 10^{18}}». Математика вычислений . 83 (288): 2033–2060. дои : 10.1090/S0025-5718-2013-02787-1 . МР  3194140.
60. Тао 2009, 3.1 Структура и случайность простых чисел, стр. 239–247. См. особенно п. 239.
61. Гай 2013, с. 159.
62. Рамаре, Оливье (1995). «О постоянной Шнирельмана». Annali della Scuola Normale Superiore di Pisa . 22 (4): 645–706. MR  1375315. Архивировано из оригинала 09 февраля 2022 г. Проверено 23 января 2018 г.
63. Рассиас, Майкл Т. (2017). Проблема Гольдбаха: избранные темы. Чам: Спрингер. п. VII. дои : 10.1007/978-3-319-57914-6. ISBN 978-3-319-57912-2. МР  3674356.
64. Коши 2002, Теорема 2.14, с. 109. Riesel 1994 приводит аналогичный аргумент, используя примориал вместо факториала.
65. Riesel 1994, «Большие промежутки между последовательными простыми числами», стр. 78–79.
66. Слоан, Нью-Джерси (ред.). «Последовательность A100964 (наименьшее простое число, которое начинается с промежутка между простыми числами не менее 2n)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
67. Ribenboim 2004, Промежутки между простыми числами, стр. 186–192.
68. Рибенбойм 2004, с. 183.
69. Чан, Джоэл (февраль 1996 г.). "ПРАЙМ-тайм!". Математические горизонты . 3 (3): 23–25. дои : 10.1080/10724117.1996.11974965. JSTOR  25678057.Обратите внимание, что Чан называет гипотезу Лежандра «постулатом Серпинского».
70. Рибенбойм 2004, Гипотеза о простых кортежах, стр. 201–202. ${\displaystyle k}$
71. Сандифер 2007, Глава 35, Оценка Базельской проблемы, стр. 205–208.
72. Огилви, CS ; Андерсон, Дж. Т. (1988). Экскурсии по теории чисел. Dover Publications Inc., стр. 29–35. ISBN 978-0-486-25778-5.
73. Апостол 1976, раздел 1.6, теорема 1.13.
74. Апостол 1976, раздел 4.8, теорема 4.12.
75. Миллер, Стивен Дж.; Таклоо-Бигхаш, Рамин (2006). Приглашение к современной теории чисел. Издательство Принстонского университета. стр. 43–44. ISBN 978-0-691-12060-7.
76. Крэндалл и Померанс 2005, стр. 6.
77. Crandall & Pomerance 2005, Раздел 3.7, Подсчет простых чисел, стр. 152–162.
78. Crandall & Pomerance 2005, с. 10.
79. дю Сотой, Маркус (2011). «Какова вероятность того, что ваш номер телефона простой?». Загадки чисел: математическая одиссея через повседневную жизнь . Пресса Святого Мартина. стр. 50–52. ISBN 978-0-230-12028-0.
80. Апостол 1976, раздел 4.6, теорема 4.7.
81. Гельфанд, ИМ ; Шен, Александр (2003). Алгебра. Спрингер. п. 37. ИСБН 978-0-8176-3677-7.
82. Моллин, Ричард А. (1997). Фундаментальная теория чисел с приложениями. Дискретная математика и ее приложения. ЦРК Пресс. п. 76. ИСБН 978-0-8493-3987-5.
83. Crandall & Pomerance 2005, Теорема 1.1.5, стр. 12.
84. Грин, Бен ; Тао, Теренс (2008). «Простые числа содержат сколь угодно длинные арифметические прогрессии». Анналы математики . 167 (2): 481–547. arXiv : math.NT/0404188 . дои : 10.4007/анналы.2008.167.481. S2CID  1883951.
85. Хуа, Л.К. (2009) [1965]. Аддитивная теория простых чисел . Переводы математических монографий. Том. 13. Провиденс, Род-Айленд: Американское математическое общество. стр. 176–177. ISBN 978-0-8218-4942-2. МР  0194404. OCLC  824812353.
86. Последовательность этих простых чисел, начинающаяся с , указана Лавой, Паоло Пьетро; Бальзаротти, Джорджо (2010). «Глава 33. Формула удачи». 103 математических любопытства: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea (на итальянском языке). Ulrico Hoepli Editore SpA с. 133. ИСБН ${\displaystyle n=1}$ ${\displaystyle n=0}$ 978-88-203-5804-4.
87. Чемберленд, Марк (2015). «Числа Хигнера». Однозначные числа: во славу маленьких чисел . Издательство Принстонского университета. стр. 213–215. ISBN 978-1-4008-6569-7.
88. Гай, Ричард (2013). «А1 Простые значения квадратичных функций». Нерешенные проблемы теории чисел . Задачи по математике (3-е изд.). Спрингер. стр. 7–10. ISBN 978-0-387-26677-0.
89. Паттерсон, SJ (1988). Введение в теорию дзета-функции Римана. Кембриджские исследования по высшей математике. Том. 14. Издательство Кембриджского университета, Кембридж. п. 1. дои : 10.1017/CBO9780511623707. ISBN 978-0-521-33535-5. МР  0933558.
90. Борвейн, Питер ; Чой, Стивен; Руни, Брендан; Вайратмюллер, Андреа (2008). Гипотеза Римана: ресурс как для любителей, так и для виртуозов. Книги CMS по математике/Ouvrages de Mathématiques de la SMC. Нью-Йорк: Спрингер. стр. 10–11. дои : 10.1007/978-0-387-72126-2. ISBN 978-0-387-72125-5. МР  2463715.
91. Сандифер 2007, стр. 191–193.
92. Борвейн и др. 2008, Гипотеза 2.7 (гипотеза Римана), с. 15.
93. Паттерсон 1988, с. 7.
94. Борвейн и др. 2008, с. 18.
95. Натансон 2000, Глава 9, Теорема о простых числах, стр. 289–324.
96. Загер, Дон (1977). «Первые 50 миллионов простых чисел». Математический интеллект . 1 (С2): 7–19. дои : 10.1007/bf03351556. S2CID  37866599.См. особенно стр. 14–16.
97. Крафт и Вашингтон (2014), Предложение 5.3, с. 96.
98. Шахриари, Шахриар (2017). Алгебра в действии: курс групп, колец и полей. Чистые и прикладные тексты для студентов. Том. 27. Американское математическое общество. стр. 20–21. ISBN 978-1-4704-2849-5.
99. Дадли 1978, Теорема 3, с. 28.
100. Шахриари 2017, стр. 27–28.
101. Рибенбойм 2004, Маленькая теорема Ферма и примитивные корни по простому модулю, стр. 17–21.
102. Рибенбойм 2004, Собственность Джуги, стр. 21–22.
103. Рибенбойм 2004, Теорема Вильсона, с. 21.
104. Чилдресс, Нэнси (2009). Теория поля классов. Университеттекст. Спрингер, Нью-Йорк. стр. 8–11. дои : 10.1007/978-0-387-72490-4. ISBN 978-0-387-72489-8. МР  2462595.См. также стр. 64.
105. Эриксон, Марти; Ваззана, Энтони; Гарт, Дэвид (2016). Введение в теорию чисел. Учебники по математике (2-е изд.). Бока-Ратон, Флорида: CRC Press. п. 200. ИСБН 978-1-4987-1749-6. МР  3468748.
106. Вейль, Андре (1995). Основная теория чисел . Классика по математике. Берлин: Springer-Verlag. п. 43. ИСБН 978-3-540-58655-5. МР  1344916.Однако обратите внимание, что некоторые авторы, такие как Чилдресс (2009), вместо этого используют слово «место» для обозначения класса эквивалентности норм.
107. Кох, Х. (1997). Алгебраическая теория чисел. Берлин: Springer-Verlag. п. 136. CiteSeerX 10.1.1.309.8812 . дои : 10.1007/978-3-642-58095-6. ISBN  978-3-540-63003-6. МР  1474965.
108. Лауритцен, Нильс (2003). Конкретная абстрактная алгебра: от чисел к базам Грёбнера. Кембридж: Издательство Кембриджского университета. п. 127. дои : 10.1017/CBO9780511804229. ISBN 978-0-521-53410-9. МР  2014325.
109. Лауритцен 2003, следствие 3.5.14, с. 133; Лемма 3.5.18, с. 136.
110. Kraft & Washington 2014, Раздел 12.1, Суммы двух квадратов, стр. 297–301.
111. Эйзенбуд, Дэвид (1995). Коммутативная алгебра . Тексты для аспирантов по математике. Том. 150. Берлин; Нью-Йорк: Springer-Verlag. Раздел 3.3. дои : 10.1007/978-1-4612-5350-1. ISBN 978-0-387-94268-1. МР  1322960.
112. Шафаревич, Игорь Р. (2013). «Определение спецификации ⁡ A {\displaystyle \operatorname {Spec} A}». Основная алгебраическая геометрия 2: схемы и комплексные многообразия (3-е изд.). Спрингер, Гейдельберг. п. 5. дои : 10.1007/978-3-642-38010-5. ISBN 978-3-642-38009-9. МР  3100288.
113. Нойкирх, Юрген (1999). Алгебраическая теория чисел . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 322. Берлин: Springer-Verlag. Раздел I.8, с. 50. дои : 10.1007/978-3-662-03983-0. ISBN 978-3-540-65399-8. МР  1697859.
114. Нойкирх 1999, раздел I.7, с. 38
115. Стивенхаген, П.; Ленстра, Х.В. младший (1996). «Чеботарёв и его теорема плотности». Математический интеллект . 18 (2): 26–37. CiteSeerX 10.1.1.116.9409 . дои : 10.1007/BF03027290. MR  1395088. S2CID  14089091. 
116. Холл, Маршалл (2018). Теория групп. Дуврские книги по математике. Публикации Courier Dover. ISBN 978-0-486-81690-6.Теоремы Силова см. на с. 43; теорему Лагранжа см. на с. 12; теорему Бернсайда см. на стр. 143.
117. Брайант, Джон; Сангвин, Кристофер Дж. (2008). Насколько кругл ваш круг?: Где встречаются инженерия и математика . Издательство Принстонского университета. п. 178. ИСБН 978-0-691-13118-4.
118. Харди, Годфри Гарольд (2012) [1940]. Извинения математика . Издательство Кембриджского университета. п. 140. ИСБН 978-0-521-42706-7. OCLC  922010634. Никто еще не обнаружил какой-либо военной цели, которой могла бы служить теория чисел или теория относительности, и маловероятно, что кто-то сделает это в течение многих лет.
119. Гиблин, Питер (1993). Простые числа и программирование . Издательство Кембриджского университета. п. 39. ИСБН 978-0-521-40988-9.
120. Гиблин 1993, с. 54
121. Ризель 1994, с. 220.
122. Буллинк, Мартен (2010). «История таблиц факторов с примечаниями о рождении теории чисел 1657–1817». Revue d'Histoire des Mathématiques . 16 (2): 133–216.
123. Вагстафф, Сэмюэл С. младший (2013). Радость факторинга. Студенческая математическая библиотека. Том. 68. Американское математическое общество. п. 191. ИСБН 978-1-4704-1048-3.
124. Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Спрингер. п. 121. ИСБН 978-0-387-25282-7.
125. Фарах-Колтон, Мартин ; Цай, Мэн-Цунг (2015). «О сложности вычисления таблиц простых чисел». В Эльбассиони, Халед; Макино, Казухиса (ред.). Алгоритмы и вычисления: 26-й Международный симпозиум, ISAAC 2015, Нагоя, Япония, 9–11 декабря 2015 г., Труды . Конспекты лекций по информатике. Том. 9472. Спрингер. стр. 677–688. arXiv : 1504.05240 . дои : 10.1007/978-3-662-48971-0_57.
126. Гривз, Джордж (2013). Сита в теории чисел. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Том. 43. Спрингер. п. 1. ISBN 978-3-662-04658-6.
127. Хромкович, Юрай (2001). «5.5 Библиографические примечания». Алгоритмы решения сложных задач . Тексты по теоретической информатике. Серия EATCS. Шпрингер-Верлаг, Берлин. стр. 383–385. дои : 10.1007/978-3-662-04616-6. ISBN 978-3-540-66860-2. MR  1843669. S2CID  31159492.
128. Коблиц, Нил (1987). «Глава V. Простота и факторинг». Курс теории чисел и криптографии . Тексты для аспирантов по математике. Том. 114. Спрингер-Верлаг, Нью-Йорк. стр. 112–149. дои : 10.1007/978-1-4684-0310-7_5. ISBN 978-0-387-96576-5. МР  0910297.
129. Пепшик, Йозеф; Харджоно, Томас; Себерри, Дженнифер (2013). «2.3.9 Вероятностные расчеты». Основы компьютерной безопасности . Спрингер. стр. 51–52. ISBN 978-3-662-07324-7.
130. Тао, Теренс (2010). «1.11 Тест на простоту АКС». Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117. ISBN 978-0-8218-5280-4. МР  2780010.
131. Аткин, OL ; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. Бибкод : 1993MaCom..61...29A. дои : 10.1090/s0025-5718-1993-1199989-x . JSTOR  2152935. MR  1199989.
132. Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math/0502097 . Бибкод : 2007MaCom..76..493M. дои : 10.1090/S0025-5718-06-01890-4. МР  2261033. S2CID  133193.
133. Ленстра, HW младший ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. дои : 10.4171/JEMS/861. hdl : 21.11116/0000-0005-717D-0. МР  3941463. S2CID  127807021.
134. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. дои : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.
135. Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR  2006406. МР  0583518.
136. Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика . 12 (1): 97–108. дои : 10.1016/0304-3975(80)90007-9 . МР  0582244.
137. Тао, Теренс (2009). «1.7 Тест Лукаса-Лемера для простых чисел Мерсенна». Наследие Пуанкаре, страницы второго года математического блога. Часть I. Провиденс, Род-Айленд: Американское математическое общество. стр. 36–41. ISBN 978-0-8218-4883-8. МР  2523047.
138. Крафт и Вашингтон, 2014, с. 41.
139. Например, см. Guy 2013, Простые числа Мерсенна A3. Репуниты. Числа Ферма. Простые числа формы k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} . стр. 13–21.
140. «Рекордное простое число из 12 миллионов цифр приносит приз в 100 000 долларов» . Фонд электронных границ. 14 октября 2009 года . Проверено 4 января 2010 г.
141. "Награды EFF в области совместных вычислений" . Фонд электронных границ. 29 февраля 2008 г. Проверено 4 января 2010 г.
142. «Подпроект PrimeGrid «Семнадцать или крах»» (PDF) . Проверено 03 января 2017 г.
143. Колдуэлл, Крис К. «Двадцать лучших: самые большие известные простые числа». Главные страницы . Проверено 03 января 2017 г.
144. Колдуэлл, Крис К. «Двадцатка лучших: факториал». Главные страницы . Проверено 03 января 2017 г.
145. Рибенбойм 2004, с. 4.
146. Колдуэлл, Крис К. «Двадцатка лучших: первобытные». Главные страницы . Проверено 03 января 2017 г.
147. Колдуэлл, Крис К. «Двадцать лучших: простые числа-близнецы». Главные страницы . Проверено 03 января 2017 г.
148. Крафт и Вашингтон, 2014, с. 275.
149. Хоффштейн, Джеффри; Пайфер, Джилл ; Сильверман, Джозеф Х. (2014). Введение в математическую криптографию. Тексты для студентов по математике (2-е изд.). Спрингер. п. 329. ИСБН 978-1-4939-1711-2.
150. Померанс, Карл (1996). «Сказка о двух решетах». Уведомления Американского математического общества . 43 (12): 1473–1485. МР  1416721.
151. Эммануэль Томе, «795-битный факторинг и дискретные логарифмы», 2 декабря 2019 г.
152. Риффель, Элеонора Г .; Полак, Вольфганг Х. (2011). «Глава 8. Алгоритм Шора». Квантовые вычисления: краткое введение . МТИ Пресс. стр. 163–176. ISBN 978-0-262-01506-6.
153. Мартин-Лопес, Энрике; Лэнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием переработки кубитов». Природная фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Бибкод : 2012NaPho...6..773M. дои : 10.1038/nphoton.2012.259. S2CID  46546101.
154. Чиргвин, Ричард (9 октября 2016 г.). «Криптовалюте необходимо больше прозрачности, предупреждают исследователи». Регистр .
155. Hoffstein, Pipher & Silverman 2014, Раздел 2.3, Обмен ключами Диффи-Хеллмана, стр. 65–67.
156. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «11.3 Универсальное хеширование». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 232–236. ISBN 0-262-03293-7.По поводу -независимого хеширования см. задачу 11–4, с. 251. Благодарность Картеру и Вегману см. в примечаниях к главе, стр. 252. ${\displaystyle k}$
157. Гудрич, Майкл Т .; Тамассия, Роберто (2006). Структуры данных и алгоритмы в Java (4-е изд.). Джон Уайли и сыновья. ISBN 978-0-471-73884-8.См. «Квадратичное измерение», с. 382 и упражнение С–9.9, с. 415.
158. Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Ресурсы для классных комнат. Том. 18. Математическая ассоциация Америки. стр. 43–44. ISBN 978-0-88385-720-5.
159. Дойч, П. (1996). Спецификация формата сжатых данных ZLIB версии 3.3. Запрос комментариев . Том. 1950. Сетевая рабочая группа.
160. Кнут, Дональд Э. (1998). «3.2.1 Линейная конгруэнтная модель». Искусство компьютерного программирования, Том. 2: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. стр. 10–26. ISBN 978-0-201-89684-8.
161. Мацумото, Макото; Нисимура, Такудзи (1998). «Mersenne Twister: 623-мерный равнораспределенный равномерный генератор псевдослучайных чисел». ACM-транзакции по моделированию и компьютерному моделированию . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . дои : 10.1145/272991.272995. S2CID  3332028. 
162. Рот, К.Ф. (1951). «О проблеме Гейльбронна». Журнал Лондонского математического общества . Вторая серия. 26 (3): 198–204. doi : 10.1112/jlms/s1-26.3.198. МР  0041889.
163. Кокс, Дэвид А. (2011). «Почему Эйзенштейн доказал критерий Эйзенштейна и почему Шенеман открыл его первым» (PDF) . Американский математический ежемесячник . 118 (1): 3–31. CiteSeerX 10.1.1.398.3440 . doi : 10.4169/amer.math.monthly.118.01.003. S2CID  15978494. 
164. Ланг, Серж (2002). Алгебра . Тексты для аспирантов по математике. Том. 211. Берлин; Нью-Йорк: Springer-Verlag . дои : 10.1007/978-1-4613-0041-0. ISBN 978-0-387-95385-4. МР  1878556., раздел II.1, с. 90
165. Шуберт, Хорст (1949). «Die eindeutige Zerlegbarkeit eines Knotens in Primknoten». С.-Б Гейдельбергер Акад. Висс. Матем.-Нат. кл . 1949 (3): 57–104. МР  0031733.
166. Милнор, Дж. (1962). «Единственная теорема о разложении трехмерных многообразий». Американский журнал математики . 84 (1): 1–7. дои : 10.2307/2372800. JSTOR  2372800. МР  0142125.
167. Boklan & Conway (2017) также включают , который не имеет этой формы. ${\displaystyle 2^{0}+1=2}$
168. Кржижек, Михал; Лука, Флориан; Сомер, Лоуренс (2001). 17 лекций о числах Ферма: от теории чисел к геометрии. Книги CMS по математике. Том. 9. Нью-Йорк: Спрингер-Верлаг. стр. 1–2. дои : 10.1007/978-0-387-21850-2. ISBN 978-0-387-95332-8. МР  1866957.
169. Боклан, Кент Д.; Конвей, Джон Х. (январь 2017 г.). «Ожидайте не более одной миллиардной части нового простого числа Ферма ! ». Математический интеллект . 39 (1): 3–5. arXiv : 1605.01371 . дои : 10.1007/s00283-016-9644-3. S2CID  119165671.
170. Глисон, Эндрю М. (1988). «Трисекция угла, семиугольник и трискайдекагон». Американский математический ежемесячник . 95 (3): 185–194. дои : 10.2307/2323624. JSTOR  2323624. MR  0935432.
171. Циглер, Гюнтер М. (2015). «Пушки по воробьям». Информационный бюллетень Европейского математического общества (95): 25–31. МР  3330472.
172. Петерсон, Иварс (28 июня 1999 г.). «Возвращение Зеты». МАА Онлайн . Архивировано из оригинала 20 октября 2007 года . Проверено 14 марта 2008 г.
173. Хейс, Брайан (2003). «Информатика: спектр римания». Американский учёный . 91 (4): 296–300. дои : 10.1511/2003.26.3349. JSTOR  27858239. S2CID  16785858.
174. Бенгтссон, Ингемар; Жичковский, Кароль (2017). Геометрия квантовых состояний: введение в квантовую запутанность (второе изд.). Кембридж: Издательство Кембриджского университета . стр. 313–354. ISBN 978-1-107-02625-4. ОКЛК  967938939.
175. Чжу, Хуанцзюнь (2010). «SIC POVM и группы Клиффорда в простых измерениях». Физический журнал A: Математический и теоретический . 43 (30): 305305. arXiv : 1003.3591 . Бибкод : 2010JPhA...43D5305Z. дои : 10.1088/1751-8113/43/30/305305. S2CID  118363843.
176. Гоулс, Э.; Шульц, О.; Маркус, М. (2001). «Выбор простых чисел циклов в модели хищник-жертва». Сложность . 6 (4): 33–38. Бибкод : 2001Cmplx...6d..33G. дои : 10.1002/cplx.1040.
177. Кампос, Пауло РА; де Оливейра, Вивиан М.; Джиро, Роналду; Гальвао, Дуглас С. (2004). «Появление простых чисел как результат эволюционной стратегии». Письма о физических отзывах . 93 (9): 098107. arXiv : q-bio/0406017 . Бибкод : 2004PhRvL..93i8107C. doi : 10.1103/PhysRevLett.93.098107. PMID  15447148. S2CID  88332.
178. «Вторжение выводка». Экономист . 6 мая 2004 года . Проверено 26 ноября 2006 г.
179. Циммер, Карл (15 мая 2015 г.). «Бамбуковые математики». Феномены: Ткацкий станок. Национальная география . Проверено 22 февраля 2018 г.
180. Хилл, Питер Дженсен, изд. (1995). Спутник Мессиана. Портленд, Орегон: Amadeus Press. Бывший. 13.2 Messe de la Pentecôte 1 «Вход». ISBN 978-0-931340-95-6.
181. Померанс, Карл (2004). «Простые числа и поиск внеземного разума» (PDF) . В Хейсе, Дэвид Ф.; Росс, Питер (ред.). Математические приключения для школьников и любителей . МАА Спектр. Вашингтон, округ Колумбия: Математическая ассоциация Америки. стр. 3–6. ISBN 978-0-88385-548-5. МР  2085842.
182. GrrlScientist (16 сентября 2010 г.). «Загадочное ночное происшествие с собакой». Наука. Хранитель . Проверено 22 февраля 2010 г.
183. Шиллингер, Лизл (9 апреля 2010 г.). «Рассчитываем друг на друга». Воскресное книжное обозрение. Нью-Йорк Таймс .

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

• "Простое число". Энциклопедия математики . ЭМС Пресс . 2001 [1994].
• Колдуэлл, Крис, The Prime Pages на primes.utm.edu.
• Простые числа в программе «В наше время» на BBC
• Пакет Plus для учителей и студентов: простые числа из Plus, бесплатного онлайн-журнала по математике, выпускаемого в рамках проекта Millennium Mathematics Project в Кембриджском университете.

Генераторы и калькуляторы

• Калькулятор простых коэффициентов может факторизовать любое положительное целое число до 20 цифр.
• Быстрый онлайн-тест на простоту с факторизацией использует метод эллиптических кривых (до тысячных цифр, требуется Java).
• Огромная база данных простых чисел
• Простые числа до 1 триллиона. Архивировано 27 февраля 2021 г. в Wayback Machine.