85.234.1.39: /* Исторические сведения */ пунктуация

2026-01-27T12:29:26Z

Исторические сведения: пунктуация

Новая страница

Вопрос определения того, является ли [[натуральное число]] <math>N</math> [[простое число|простым]], известен как проблема простоты.

'''Тестом простоты''' (или проверкой простоты) называется [[алгоритм]], который, приняв на входе число <math>N</math>, позволяет либо не подтвердить предположение о том, является ли это число [[составное число|составным]], либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты.
Таким образом, тест простоты представляет собой только [[гипотеза|гипотезу]] о том, что если алгоритм не подтвердил предположение о составности числа <math>N</math>, то это число может являться простым с определённой [[вероятность]]ю. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое даёт математически подтверждённый результат.

== Введение ==
Проблемы [[Дискретная математика|дискретной математики]] являются одними из самых [[Вычислительная сложность|математически сложных]]. Одна из них — задача [[Факторизация|факторизации]], заключающаяся в поиске разложения числа на простые множители. Для её решения необходимо найти простые числа, что приводит к проблеме простоты.
Задача теста простоты относится к [[Класс P|классу сложности P]], то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в [[2002 год]]у. Существует аналогичное, однако недоказанное, утверждение для [[Факторизация целых чисел|задачи факторизации]].

Некоторые приложения математики с использованием факторизации требуют ряда очень больших простых чисел, выбранных случайным образом. Алгоритм их получения, основанный на [[Постулат Бертрана|постулате Бертрана]]:

{| class="standard" style="margin-left: 1em"
|--
|
'''Алгоритм:'''

# '''Ввод''': натуральное число <math>N</math>
# '''Решение''' (поиск случайного простого числа P)
## <math>P \gets </math> '''Функция''' генерации произвольного натурального числа на отрезке <math>[N,2N]</math>
## '''Если''' <math>P</math> составное, '''то'''
### <math>P \leftarrow\,P+1</math>
### '''Если''' <math>P=2N</math> '''то'''
#### <math>P \leftarrow\,N</math>
## '''Возврат''' «<math>P</math> — случайное простое»
|}
Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее [[Дискретное равномерное распределение|равномерно]]. Для простых случайных чисел эти условия выполняются.

Известно ([[Простое число#Бесконечность множества простых чисел|теорема Евклида]]), что множество простых чисел бесконечно. [[Теорема Дирихле о простых числах в арифметической прогрессии|Теорема Дирихле]] ([[1837 год|1837]]) гласит, что если [[Наибольший общий делитель|НОД]]<math>(a,n)=1</math>, то существует бесконечно много простых чисел, сравнимых с <math>a</math> [[Сравнимость по модулю|по модулю]] <math>n</math>. Другими словами, простые числа распределены равномерно в [[Класс вычетов|классах вычетов]] по <math>mod n</math> в соответствии с [[Функция Эйлера|функцией Эйлера]]<ref name=Cormen_Cr>{{Книга|автор=Кормен Т., Лейзер Ч.|заглавие=Алгоритмы. Построение и анализ|место=М.|издательство=МЦНМО|год=2002| страницы=765—772|страница=765}}
</ref> <math>\varphi(n)</math> при любом значении <math>n</math>.
Однако, если простые числа распределены равномерно, но их существует очень небольшое количество, поиск может оказаться невозможным на практике. Чтобы решить эту вторую проблему, воспользуемся [[Теорема о распределении простых чисел|теоремой о распределении простых чисел]] ([[1896 год|1896]]), согласно которой количество простых чисел в интервале <math>[2,n]</math> растёт с увеличением <math>n</math> как <math>n/log(n)</math>. Это число стремится к бесконечности довольно быстро, из чего можно сделать заключение, что даже при больших значениях <math>n</math> существует достаточно высокая вероятность (<math>1/ln(n)</math>) нахождения простого числа наугад.
Из этого можно заключить, что описанный выше алгоритм может дать ответ за полиномиальное время, если существует полиномиальный алгоритм, позволяющий убедиться в простоте сколь угодно большого числа <math>n</math>, что приводит к проблеме простоты.

== Исторические сведения ==
Самые первые упоминания о простых числах известны у [[Евклид]]а ([[III век до н. э.]]). При этом первый алгоритм нахождения простых чисел был изобретён [[Эратосфен]]ом ([[II век до н. э.]]) и известен сейчас под названием [[решето Эратосфена]]. Его суть в последовательном исключении из списка целых чисел от <math>1</math> до <math>n</math> чисел, кратных <math>2, 3, 5</math> и другим уже найденным «решетом» простым числам<ref name=Vasilenko_Cr>{{книга|автор=Василенко О. Н.|заглавие=Теоретико-числовые алгоритмы в криптографии|место=М.|издательство=МЦНМО|год=2003|страниц=328|страница=13}}</ref>. Значительно позже арабский математик [[ибн ал-Банна]] предложил делать перебор целых чисел не до <math>n</math>, а до <math>\sqrt{n}</math>, что позволило уменьшить количество операций.
Недостаток этого метода заключается в том, что вместо проверки заданного числа <math>n</math> на простоту он предлагает последовательный [[Полный перебор|перебор]]<ref name=Crandall_Cr>{{Книга|автор=Crandall R., Pomerance C.|заглавие=Prime Numbers: A Computational Perspective|издательство=Springer|год=2005|страница=118}}
</ref> всех целых чисел до <math>\sqrt{n}</math>, и поэтому является малоэффективным и требует значительных [[Вычислительные ресурсы|вычислительных мощностей]].

В начале [[XIII век]]а [[Леонардо Пизанский]], известный как Фибоначчи, предложил последовательность чисел (названную его именем), одно из свойств которой состоит в том, что <math>n</math>-ное [[число Фибоначчи]] <math>F_n</math> может быть простым только для простых <math>n</math>, за исключением <math>n=4</math>. Это свойство может быть использовано при проверке чисел Фибоначчи на простоту. Также он независимо от ибн ал-Банна предложил метод проверки чисел на простоту перебором. Этот алгоритм является истинным (или невероятностным), поскольку ответ получается всегда, однако чрезвычайно неэффективным.

Первым, кто использовал отношения между числами для определения простоты, был [[Катальди, Пьетро Антонио|Пьетро Антонио Катальди]] в своей работе о совершенных числах. [[Совершенные числа|Совершенными числами]] называются те, которые равны сумме своих собственных делителей. Первые семь совершенных чисел: 6, 28, 496, 8128, 33550336, 8589869056 и 137438691328. Катальди установил, что если число <math>n</math> — простое и число <math>2^n-1</math> — также простое, то число <math>2^{n-1}(2^n-1)</math> — совершенное.

В [[XVII век]]е французский математик [[Марен Мерсенн]] занимался исследованием чисел вида<ref name=KNT_Cr>{{книга|автор = [[Дональд Кнут]]|заглавие = Искусство программирования, том 2. Получисленные алгоритмы|место = {{М.}}|издательство = [[Вильямс (издательство)|«Вильямс»]]|год = 2007|страница = 428}}</ref> <math>2^n-1</math>, позднее названных в его честь [[Числа Мерсенна|числами Мерсенна]]. Мерсенн обнаружил, что из первых 257 чисел Мерсенна только 11 являются простыми (при n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257). При этом, им было сделано несколько ошибок (<math>2^n-1</math> не является простым при р = 67 или 257, и является при р = 61, 89 и 107).
Поиск простых среди чисел Мерсенна достаточно прост благодаря [[Тест Люка — Лемера|тесту Люка-Лемера]], позволяющему относительно быстро находить решение. Именно поэтому числа Мерсенна являются самыми большими среди ныне известных простых чисел. В переписке Мерсенна и [[Ферма, Пьер|Ферма]] были высказаны ещё несколько идей относительно простых чисел<ref name=KNT_Cr/>.

Так, Ферма обнаружил, что если целое число <math>a</math> не делится нацело на простое число <math>p</math>, то число <math>a^{p-1}-1</math> всегда делится на <math>p</math> ([[Малая теорема Ферма]]). Позднее теорема была [[Теорема Эйлера (теория чисел)|обобщена]] [[Эйлер, Леонард|Эйлером]]. На малой теореме Ферма основаны несколько тестов простоты.
Также Ферма предположил, что простыми являются числа вида <math>2^{2^{k}}+1</math> при всех натуральных <math>k</math>. Это действительно так при <math>k = 0,1,2,3,4</math>. [[Контрпример]] к этому утверждению был найден Эйлером — <math>2^{2^{5}}+1 = 4294967297 = 641\cdot 6700417</math>. Для проверки чисел Ферма на простоту существует эффективный [[тест Пепина]]. На сегодняшний день ни одного нового простого числа Ферма не было найдено.

В числе других ученых вопросами простоты чисел занимались Эйлер, [[Лежандр, Адриен Мари|Лежандр]], [[Гаусс, Карл Фридрих|Гаусс]]. Значительные результаты в решении проблемы простоты были получены французским математиком [[Люка, Франсуа Эдуард Анатоль|Эдуардом Люка]] в его работах о числах Ферма и Мерсенна . Именно данный им критерий простоты чисел Мерсенна ныне известен как тест Люка-Лемера.

В 2002 году был разработан детерминированный полиномиальный тест простоты, [[тест Агравала — Каяла — Саксены]]. Его появление предсказывалось существованием полиномиальных [[Сертификат простоты|сертификатов простоты]] и, как следствие, тем, что задача проверки числа на простоту принадлежала классам [[Класс NP|NP]] и [[Класс co-NP|co-NP]] одновременно.

== Истинные и вероятностные тесты простоты ==
Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Истинные тесты результатом вычислений всегда выдают факт простоты либо составности числа, вероятностный тест даёт ответ о составности числа либо его несоставности с некоторой вероятностью<ref name=Vasilenko_Cr /><ref name=KNT_Cr/> <math>\epsilon</math>. Если сказать проще, то вероятностный алгоритм говорит, что число скорее всего не является составным, однако в итоге оно может оказаться как простым, так и составным. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются [[Псевдопростое число|псевдопростыми]]<ref name=Cormen_Cr/>. Одним из примеров таких чисел являются [[числа Кармайкла]]<ref name=Crandall_Cr/>. Также можно назвать числа Эйлера-Якоби для теста Соловея-Штрассена и псевдопростые числа Люка.

Одним из примеров истинных тестов простоты является [[тест Люка-Лемера]] для [[Числа Мерсенна|чисел Мерсенна]]. Очевидный недостаток этого теста заключается в его применимости только к ряду чисел определённого вида.
Среди других примеров можно привести основанные на [[Малая теорема Ферма|малой теореме Ферма]]:
* [[Тест Пепина]] для [[Числа Ферма|чисел Ферма]].
* [[Теорема Прота]] для [[Число Прота|чисел Прота]].
* [[Тест Агравала — Каяла — Саксены]], первый полиномиальный тест простоты.
* [[Тест Люка — Лемера — Ризеля]].
А также:
* [[Перебор делителей|метод перебора делителей]].
* [[Теорема Вильсона]].
* [[Критерий Поклингтона]].
* [[Тест Миллера (теория чисел)|Тест Миллера]].
* [[Тест Адлемана — Померанса — Румели]], усовершенствованный<ref name=Nesterenko_Cr>{{книга |автор=Нестеренко Ю. В. |заглавие=Введение в криптографию | |год=2001 |издательство=Питер |страниц=288}}
</ref> {{нп5|Генри Коэн|Коэном||Henri Cohen (number theorist)}} и [[Ленстра, Арьен|Ленстрой]]
* [[Тест простоты с использованием эллиптических кривых]].

== Вероятностные тесты простоты ==
К этой категории относятся:
* [[Тест Ферма]].
* [[Тест Миллера — Рабина]].
* [[Тест Соловея — Штрассена]].
* [[Тест Бейли — Померанца — Селфриджа — Уогстаффа]].
* [[Метод простоты Фробениуса|Квадратичный тест Фробениуса]].

== Тесты простоты в [[Криптография|криптографии]] ==
В настоящее время простые числа широко применяются в области защиты информации. Прежде всего, это вызвано изобретением метода шифрования с открытым ключом, который используется при шифровании информации и в алгоритмах электронной [[Цифровая подпись|цифровой подписи]]. На данный момент по стандартам размер простых чисел, используемых при формировании цифровой подписи с использованием эллиптических кривых, составляет в соответствии с ГОСТ Р 34.10-2012 не менее 254 бит.
Для столь больших чисел вопрос определения простоты числа является крайне сложным. Простые методы, такие, как метод перебора, непригодны для использования из-за того, что требуют чрезвычайно много вычислительных ресурсов и большого времени работы<ref name=SHN_Cr>{{книга|автор=Б. Шнайер|заглавие= Прикладная криптография|страницы=296—300}}</ref>.

Также определение простоты числа необходимо при взломе информации, зашифрованной или подписанной с использованием алгоритма [[RSA]]. Для вскрытия такого сообщения необходимо уметь разлагать число на два простых сомножителя, что при больших размерах чисел является нетривиальной задачей.

С другой стороны, при генерации ключей для [[Криптосистема с открытым ключом|криптосистем с открытым ключом]], схем электронной подписи и т. п. используются большие псевдослучайные простые числа. Например, при использовании [[Диффи-Хеллман|протокола Диффи-Хеллмана]] необходимо иметь простое число, задающее [[конечное поле]]. Поэтому использование эффективного теста простоты позволяет повысить надёжность алгоритмов генерации таких ключей.

== См. также ==
* [[Криптография]]
* [[Решето Эратосфена]]
* [[Решето Сундарама]]

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

== Литература ==
* {{книга|автор=Василенко О. Н.|часть=Глава 1. Тестирование чисел на простоту и построение больших простых чисел|заглавие=Теоретико-числовые алгоритмы в криптографии|ссылка=http://www.ict.edu.ru/ft/002416/book.pdf|место=М.|издательство=МЦНМО|год=2003|страницы=12—56|страниц=328|isbn=5-94057-103-4|archive-url=https://web.archive.org/web/20070127053816/http://www.ict.edu.ru/ft/002416/book.pdf|archive-date=2007-01-27}}
* {{книга |автор=Нестеренко Ю. В. |часть=Глава 4.6. Как проверить большое число на простоту |заглавие=Введение в криптографию |ответственный=Под ред. В. В. Ященко |год=2001 |издательство=Питер |isbn=5-318-00443-1 |страниц=288 |ссылка=http://nature.web.ru/db/msg.html?mid=1157083&uri=book.html|ссылка часть=http://nature.web.ru/db/msg.html?mid=1157083&uri=node34.html |archive-url=https://web.archive.org/web/20080225102710/http://nature.web.ru/db/msg.html?mid=1157083&uri=book.html|archive-date=2008-02-25}}
* {{Книга:Шнайер Б.: Прикладная криптография|часть=Часть 3. Криптографические алгоритмы. Глава 11. Математические основы. 11.5. Генерация простых чисел|страницы=296—300}}
* {{Книга|автор=Кормен Т., Лейзер Ч.|часть=Глава 33.8. Проверка чисел на простоту|заглавие=Алгоритмы. Построение и анализ|ссылка=http://www.proklondike.com/books/thalg/kormen_leiser_algorith.html|место=М.|издательство=МЦНМО|год=2002| страницы=765—772|isbn=5-900916-37-5}}
* {{Книга|автор=Crandall R., Pomerance C.|часть=Глава 3. «Recognizing Primes and Composites». Глава 4. «Primality Proving»|страницы=117—224|заглавие=Prime Numbers: A Computational Perspective|ссылка=http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf|издательство=Springer|год=2005|isbn=0-387-25282-7}}
* {{книга|автор = [[Дональд Кнут]] |часть=Глава 4.5.4. Разложение на простые множители |заглавие = Искусство программирования, том 2. Получисленные алгоритмы |оригинал = The Art of Computer Programming, vol. 2. Seminumerical Algorithms |ссылка = |издание = 3-е изд |место = {{М.}} |издательство = [[Вильямс (издательство)|«Вильямс»]] |год = 2007 |страницы = 832 |isbn = 0-201-89684-2}}

{{Перевести|es|Test de primalidad}}

{{Теоретико-числовые алгоритмы}}
{{Алгоритмы теории чисел}}

[[Категория:Тесты простоты| ]]

Тест простоты - История изменений

85.234.1.39: /* Исторические сведения */ пунктуация