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

Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число является простым, если оно отлично от и делится без остатка только на и на само .

Пример: число простое (делится на и на ), а не является простым, так как, помимо и , делится на  — имеет три натуральных делителя.

Изучением свойств простых чисел занимается теория чисел, а основная теорема арифметики устанавливает в ней их центральную роль: любое целое число, превышающее , либо является простым, либо может быть выражено произведением простых чисел, причём такое представление однозначно с точностью до порядка сомножителей. Единицу не относят к простым числам, так как иначе указанное разложение становится неоднозначным: .

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

Последовательность простых чисел начинается так:

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

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

Многие проблемы, касающиеся простых чисел, остаются открытыми.

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

Множество всех простых чисел обычно обозначают символами или

История Неизвестно, когда было определено понятие простого числа, однако первые свидетельства относят к верхнему палеолиту, что подтверждается костью Ишанго Préhistoire de la géométrie : le problème des sources (PDF). Site de l’IREM de La Réunion. Voir aussi « Les fables d’Ishango, ou l’irrésistible tentation de la mathématique-fiction» , analyse par O. Keller sur Bibnum.

В сохранившихся записях древнеегипетских математиков есть намёки на то, что у них были некоторые представления о простых числах: например, папирус Райнда, относящийся ко второму тысячелетию до нашей эры, содержит таблицу соотношений числа 2 к , представленных суммой трёх или четырёх египетских дробей с единицей в числителе и различных знаменателях. Разложения дробей, знаменатели которых имеют общий делитель, похожи, поэтому египтяне по крайней мере знали разницу между простыми и составными числами.

Самые ранние дошедшие до нас исследования простых чисел принадлежат математикам Древней Греции. Они изобрели решето Эратосфена — алгоритм последовательного нахождения всех простых чисел от 1 до . Опубликованные в приблизительно трёхсотом году до нашей эры «Начала» Евклида содержат важные теоремы о простых числах, включая бесконечность их множества, лемму Евклида и основную теорему арифметики.

Вплоть до XVII века существенных новых работ в области простых чисел не было. В 1640 году Пьер де Ферма сформулировал малую теорему Ферма, затем доказанную Лейбницем и Эйлером, и теорему о сумме двух квадратов, а также высказал предположение: все числа вида  являются простыми, и даже доказал это до . Но уже для следующего числа Ферма Эйлер доказал делимость на . Новые простые числа в последовательности Ферма не найдены до сих пор. В то же время французский монах Марен Мерсенн обнаружил, что последовательность , где  — простое, даёт также простое число (числа Мерсенна).

Работа Эйлера в теории чисел вместила немало сведений о простых. Он показал, что бесконечный числовой ряд  — расходящийся. В 1747 году он доказал, что чётные совершенные числа являются значениями последовательности , где сомножитель является числом Мерсенна. В его переписке с Гольдбахом последний изложил свою знаменитую гипотезу о представлении любого чётного числа, начиная с четырёх, суммой двух простых. Доказательство гипотезы пока не найдено.

С начала XIX века внимание многих математиков занимала проблема асимптотического распределения простых чисел. Лежандр и Гаусс независимо друг от друга высказали предположение: плотность простых чисел в среднем близка к величине, обратно пропорциональной натуральному логарифму.

Долгое время простые числа считались малоприменимыми за пределами чистой математики. Ситуация изменилась в 1970-е годы, после появления концепций криптографии с открытым ключом, в которых простые числа составили основу первых алгоритмов шифрования, таких как RSA.

Разложение натуральных чисел в произведение простых

Представление натурального числа в виде произведения простых называется разложением на простые, или факторизацией числа. На настоящий момент не известны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема RSA и некоторые другие. Факторизация с полиномиальной сложностью теоретически возможна на квантовом компьютере с помощью алгоритма Шора.

Основная теорема арифметики

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей, Section 2, Theorem 2. Таким образом, простые числа являются элементарными «строительными блоками» натуральных чисел. Например:

Как было показано в этом примере, один и тот же простой делитель может появляться несколько раз. Разложение:

числа на (конечное число) простых множителей , , … , называется разложением на простые множители числа . Основная теорема арифметики может быть перефразирована таким образом: любое разложение на простые числа будет тождественным с точностью до порядка делителей. На практике для большинства чисел есть много простых алгоритмов разложения на множители, все они дают один и тот же результат.

Простота единицы Большинство древних греков даже не считало числом, поэтому они не могли считать его простымСм, например, David E. Joyce’s комментарий на Начала (Евклид), Книга VII, определения 1 и 2 .. К Средним векам и эпохе Возрождения многие математики включали в качестве первого простого числаWhy is the number one not prime? (from the Prime Pages' list of frequently asked questions) by Chris K. Caldwell. . В середине XVIII века Христиан Гольдбах внёс в список в качестве первого простого числа в своей знаменитой переписке с Леонардом Эйлером; однако сам Эйлер не считал простым числомSee for instance: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160—188. Variae observationes circa series infinitas, Theorema 19, p.187. . В XIX веке многие математики по-прежнему считали число простым числом. Например, список простых чисел Деррика Нормана Лемера до числа, переизданный в 1956 году, начинался с в качестве первого простого числа. Говорят, что Анри Лебег является последним математиком, который назвал простым. К началу XX века математики стали приходить к консенсусу о том, что не является простым числом, а скорее формирует свою специальную категорию — «единицу».

Если считать простым числом, то основная теорема Евклида об арифметике (упомянутая выше) не будет выполняться, как было указано в начале статьи. Например, число может быть разложено как . Если бы являлась простым числом, эти два варианта считались бы разными факторизациями ; следовательно, утверждение этой теоремы пришлось бы изменить. Точно так же решето Эратосфена работало бы неправильно, если бы считалась простым: модифицированная версия решета, которая предполагает, что является простым числом, исключает все множители, кратные (то есть все остальные числа), и даёт на выходе только одно число — . Кроме того, простые числа имеют несколько свойств, которых нет у числа , такие как отношение числа к его соответствующему значению функции тождества Эйлера или суммы функции делителей"«Arguments for and against the primality of 1 »..

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

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают решето Эратосфена, решето Сундарама и решето Аткина.

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их является вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.

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

Тест простоты Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число, позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Задача теста простоты относится к классу сложности P, то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в 2002 году. Появление полиномиального алгоритма предсказывалось существованием полиномиальных сертификатов простоты и, как следствие, тем, что задача проверки числа на простоту принадлежала классам NP и co-NP одновременно.

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Результатом вычислений истинных тестов всегда является факт простоты либо составности числа. Вероятностный тест показывает, является ли число простым с некоторой вероятностью. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми. Одним из примеров таких чисел являются числа Кармайкла.

Одним из примеров истинных тестов простоты является тест Люка-Лемера для чисел Мерсенна. Очевидный недостаток этого теста заключается в его применимости только к числам определённого вида. Среди других примеров можно привести основанные на малой теореме Ферма Тест Пепина для чисел Ферма Теорема Прота для чисел Прота Тест Агравала — Каяла — Саксены, первый универсальный, полиномиальный, детерминированный и безусловный тест простоты. Тест Люка — Лемера — Ризеля А также: метод перебора делителей Теорема Вильсона Критерий Поклингтона Тест Миллера Тест Адлемана — Померанса — Румели, усовершенствованный Коэном и Ленстрой Тест простоты с использованием эллиптических кривых. К вероятностным тестам простоты относят: Тест Ферма Тест Миллера — Рабина Тест Соловея — Штрассена Тест Бейли — Померанца — Селфриджа — Уогстаффа

Большие простые числа Уже в течение многих столетий поиск «больших» простых чисел вызывает интерес математиков. В последние десятилетия эти исследования приобрели прикладное значение из-за применения таких чисел в ряде алгоритмов шифрования, таких как RSA.

В семнадцатом столетии Марен Мерсенн предположил, что числа вида простые (при n ≤ 257) только для n равных 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257. Проверка верности предположения была намного выше возможностей того времени. Только в XX веке было обнаружено, что гипотеза была ложной и, вероятно, сделана «слепо», поскольку Мерсенн не учел три случая (для n = 61, 89 и 107); кроме того, оказалось, что числа, соответствующие n = 67 и n = 257 — составные.