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

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

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

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

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

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

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

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

В делители натурального числа являются натуральные числа , которые делятся поровну. Каждое натуральное число имеет как 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] , или (в доске жирным шрифтом буквы П). ^[12]${\displaystyle \mathbf {P} }$${\displaystyle \mathbb {P} }$

История

Папирус Ахмес , от около 1550 г. до н.э., имеет египетские дроби разложение различных форм для простых и составных чисел. ^[13] Однако самые ранние сохранившиеся записи явного изучения простых чисел относятся к древнегреческой математике . Euclid «s элементов (с. 300 до н.э.) доказывает беспредельность простых чисел и основной теоремы арифметики , и показывает , как построить совершенное число от штрихом Mersenne . ^[14] Другое греческое изобретение, Сито Эратосфена , до сих пор используется для создания списков простых чисел.^{[15] [16]}

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

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

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

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

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

Первобытность одного

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

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

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

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

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

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

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

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

Некоторые доказательства единственности разложения на простые множители основаны на лемме Евклида : If - простое число и делит произведение целых чисел, а затем делит или делит (или и то, и другое). ^[46] И наоборот, если число обладает тем свойством, что при делении продукта оно всегда делит хотя бы один множитель продукта, тогда оно должно быть простым. ^[47]${\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, ...

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

Доказательство Евклида ^[51] показывает, что любой конечный список простых чисел неполон. Ключевая идея состоит в том, чтобы перемножить простые числа в любом заданном списке и сложить.Если список состоит из простых чисел, это дает число${\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}$

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

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

составное число.

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

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

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

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

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

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

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

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

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

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

Эта область исследований началась с Леонарда Эйлера и его первого крупного результата, решения проблемы Базеля . Проблема попросил значения бесконечной суммы , которая сегодня может быть признана в качестве значения по дзета - функции Римана . Эта функция тесно связана с простыми числами и одной из самых важных нерешенных проблем математики - гипотезой Римана . Эйлер это показал . ^[70] Обратное значение этого числа является предельной вероятностью того, что два случайных числа, выбранных одинаково из большого диапазона, являются относительно простыми (не имеют общих множителей). ^[71]${\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}}$

Распределение простых чисел в большом, например вопрос, сколько простых чисел меньше заданного большого порога, описывается теоремой о простых числах , но эффективная формула для -го простого числа n {\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}}.}$

Эйлер показал, что для любого произвольного действительного числа существует простое число, для которого эта сумма больше, чем . ^[72] Это показывает, что существует бесконечно много простых чисел, потому что, если бы было конечное число простых чисел, сумма достигла бы своего максимального значения при наибольшем простом числе, а не вырастала бы после каждого . Скорость роста этой суммы более точно описывается второй теоремой Мертенса . ^[73] Для сравнения, сумма${\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}}}}$

не возрастает до бесконечности, как до бесконечности (см. Базельскую задачу ). В этом смысле простые числа встречаются чаще, чем квадраты натуральных чисел, хотя оба набора бесконечны. ^[74] Теорема Бруна утверждает, что сумма обратных двойных простых чисел ,${\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 ,}$

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

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

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

Функция подсчета простых чисел определяется как количество простых чисел, не превышающих . ^[75] Например, поскольку существует пять простых чисел, меньших или равных 11. Такие методы, как алгоритм Мейселя – Лемера, могут вычислять точные значения быстрее, чем было бы возможно перечислить каждое простое число до . ^[76] Теорема о простых числах утверждает, что асимптотика к , который обозначается как${\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 при возрастании до бесконечности. ^[77] Это означает, что вероятность того, что случайно выбранное число меньше простого, (приблизительно) обратно пропорциональна количеству цифр в . ^[78] Это также означает, что ое простое число пропорционально ^[79] и, следовательно, средний размер промежутка между простыми числами пропорционален . ^[64] Более точная оценка дается с помощью логарифмического интеграла смещения ^[77]${\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}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Один из самых известных нерешенных вопросов в области математики, начиная с 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}}}.}$

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

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

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

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

Модульная арифметика изменяет обычную арифметику, используя только числа для натурального числа, называемого модулем. Любое другое натуральное число можно отобразить в этой системе, заменив его остатком после деления на . ^[96] Модульные суммы, разности и произведения рассчитываются путем такой же замены остатком результата обычной суммы, разницы или произведения целых чисел. ^[97] Равенство целых чисел соответствует конгруэнтности в модульной арифметике: и конгруэнтны (пишутся по модулю ), когда они имеют одинаковый остаток после деления на . ^[98] Однако в этой системе чисел деление${\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}$или, более конкретно, конечное поле , в то время как другие модули дают только кольцо, но не поле. ^[99]

Некоторые теоремы о простых числах можно сформулировать с помощью модульной арифметики. Например, маленькая теорема Ферма утверждает, что если (mod ), то (mod ). ^[100] Суммируя это по всем вариантам, получаем уравнение${\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}},}$

действительно, когда простое число. Гипотеза Джуги гласит, что это уравнение также является достаточным условием для простоты . ^[101] Теорема Вильсона гласит, что целое число является простым тогда и только тогда, когда факториал конгруэнтен mod . Для составного числа это не может быть выполнено, так как один из его факторов водоразделов и п и , и так невозможно. ^[102]${\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 -адические числа

-Адическая порядок целого числа есть число копий в первичном разложении . Та же концепция может быть расширена от целых до рациональных чисел, определив -адический порядок фракции быть . -Адическое абсолютное значение любого рационального числа затем определяются как . Умножение целого числа на его абсолютное значение -adic отменяет множители в его факторизации, оставляя только другие простые числа. Подобно тому, как расстояние между двумя действительными числами можно измерить абсолютным значением их расстояния, расстояние между двумя рациональными числами можно измерить их -адическим расстоянием, p {\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}$-адическое абсолютное значение их разницы. Для этого определения расстояния два числа находятся близко друг к другу (они имеют небольшое расстояние), когда их разница кратна большой степени . Точно так же, как действительные числа могут быть сформированы из рациональных чисел и их расстояний, путем добавления дополнительных предельных значений для формирования полного поля , рациональные числа с -адическим расстоянием могут быть расширены до другого полного поля, -адического числа . ^{[103] [104]}${\displaystyle p}$${\displaystyle p}$ p {\displaystyle p}

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

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

Коммутативное кольцо представляет собой алгебраическую структуру , где сложение, вычитание и умножение определены. Целые числа представляют собой кольцо, а простые числа в целых числах были обобщены на кольца двумя различными способами: простые элементы и неприводимые элементы . Элемент кольца называется простым, если он не равен нулю, не имеет обратного мультипликативного элемента (то есть не является единицей ) и удовлетворяет следующему требованию: всякий раз, когда делит произведение двух элементов кольца , он также делит по крайней мере один из или же${\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 \}\,.}$

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

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

Основные идеалы

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

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

Теория групп

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

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

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

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

Пробный отдел

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

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

Сита

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

Сравнение первичности тестирования и первичности доказательства

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

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

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

Тест	Разработано в	Тип	Продолжительность	Примечания	Рекомендации
Тест на простоту AKS	2002 г.	детерминированный	${\displaystyle O((\log n)^{6+\varepsilon })}$		[129] [132]
Доказательство простоты эллиптической кривой	1986 г.	Лас Вегас	${\displaystyle O((\log n)^{4+\varepsilon })}$ эвристически		[131]
Тест на простоту Baillie-PSW	1980 г.	Монте-Карло	${\displaystyle O((\log n)^{2+\varepsilon })}$		[133] [134]
Тест на простоту Миллера – Рабина	1980 г.	Монте-Карло	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	вероятность ошибки ${\displaystyle 4^{-k}}$	[135]
Тест на простоту Соловея – Штрассена	1977 г.	Монте-Карло	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	вероятность ошибки ${\displaystyle 2^{-k}}$	[135]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конструируемые полигоны и многоугольные разделы

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

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

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

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

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

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

Биология

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

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

Простые числа повлияли на многих художников и писателей. Французский композитор Оливье Мессиан использовал простые числа для создания аметрической музыки через «природные явления». В таких работах, как La Nativité du Seigneur (1935) и Quatre études de rythme (1949–50), он одновременно использует мотивы с длиной, заданной разными простыми числами, для создания непредсказуемых ритмов: простые числа 41, 43, 47 и 53 появляются в третий этюд "Neumes rythmiques". Согласно Мессиану, этот способ сочинения был «вдохновлен движениями природы, движениями свободной и неравной продолжительности». ^[179]

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

Примечания

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