Как проверить что число простое

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

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

Содержание

Введение [ править | править код ]

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

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

1. Ввод: натуральное число N <displaystyle N>
2. Решение (поиск случайного простого числа P)

1. P ← <displaystyle Pgets >Функция генерации произвольного натурального числа на отрезке [ N , 2 N ] <displaystyle [N,2N]>
2. Если P <displaystyle P>составное, то

1. P ← P + 1 <displaystyle Pleftarrow ,P+1>
2. Если P = 2 N <displaystyle P=2N>то

1. P ← N <displaystyle Pleftarrow ,N>

Возврат « P <displaystyle P>— случайное простое»

Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее равномерно. Для простых случайных чисел эти условия выполняются.

Известно (теорема Евклида), что множество простых чисел бесконечно. Теорема Дирихле (1837) гласит, что если НОД ( a , n ) = 1 <displaystyle (a,n)=1> , то существует бесконечно много простых чисел, сравнимых с a <displaystyle a> по модулю n <displaystyle n> . Другими словами, простые числа распределены равномерно в классах вычетов по m o d n <displaystyle modn> в соответствии с функцией Эйлера [1] φ ( n ) <displaystyle varphi (n)> при любом значении n <displaystyle n> . Однако, если простые числа распределены равномерно, но их существует очень небольшое количество, поиск может оказаться невозможным на практике. Чтобы решить эту вторую проблему, воспользуемся теоремой о распределении простых чисел (1896), согласно которой количество простых чисел в интервале [ 2 , n ] <displaystyle [2,n]> растет с увеличением n <displaystyle n> как n / l o g ( n ) <displaystyle n/log(n)> . Это число стремится к бесконечности довольно быстро, из чего можно сделать заключение, что даже при больших значениях n <displaystyle n> существует достаточно высокая вероятность ( 1 / l n ( n ) <displaystyle 1/ln(n)> ) нахождения простого числа наугад. Из этого можно заключить, что описанный выше алгоритм может дать ответ за полиномиальное время, если существует полиномиальный алгоритм, позволяющий убедиться в простоте сколь угодно большого числа n <displaystyle n> , что приводит к проблеме простоты.

Исторические сведения [ править | править код ]

Самые первые упоминания о простых числах известны у Евклида (3 в. до н. э.). При этом первый алгоритм нахождения простых чисел был изобретен Эратосфеном (2 в. до н. э.) и известен сейчас под названием решето Эратосфена. Его суть в последовательном исключении из списка целых чисел от 1 <displaystyle 1> до n <displaystyle n> чисел, кратных 2 , 3 , 5 <displaystyle 2,3,5> и другим уже найденным «решетом» простым числам [2] . Значительно позже арабский математик ибн ал-Банна предложил делать перебор целых чисел, не до n <displaystyle n> , а до n <displaystyle <sqrt >> , что позволило уменьшить количество операций. Недостаток этого метода заключается в том, что вместо проверки заданного числа n <displaystyle n> на простоту он предлагает последовательный перебор [3] всех целых чисел до n <displaystyle <sqrt >> , и поэтому является малоэффективным и требует значительных вычислительных мощностей.

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

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

В XVII веке французский математик Марен Мерсенн занимался исследованием чисел вида [4] 2 n − 1 <displaystyle 2^-1> , позднее названных в его честь числами Мерсенна. Мерсенн обнаружил, что из первых 257 чисел Мерсенна только 11 являются простыми (при n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257). При этом, им было сделано несколько ошибок ( 2 n − 1 <displaystyle 2^-1> не является простым при р = 67 или 257, и является при р = 61, 89 и 107). Поиск простых среди чисел Мерсенна достаточно прост благодаря тесту Люка-Лемера, позволяющему относительно быстро находить решение. Именно поэтому числа Мерсенна являются самыми большими среди ныне известных простых чисел. В переписке Мерсенна и Ферма были высказаны ещё несколько идей относительно простых чисел [4] .

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

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

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

Истинные тесты простоты [ править | править код ]

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Истинные тесты результатом вычислений всегда выдают факт простоты либо составности числа, вероятностный тест дает ответ о составности числа либо его несоставности с некоторой вероятностью [2] [4] ϵ <displaystyle epsilon > . Если сказать проще, то вероятностный алгоритм говорит, что число скорее всего не является составным, однако в итоге оно может оказаться как простым, так и составным. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми [1] . Одним из примеров таких чисел являются числа Кармайкла [3] . Также можно назвать числа Эйлера-Якоби для теста Соловея-Штрассена и псевдопростые числа Люка.

Одним из примеров истинных тестов простоты является тест Люка-Лемера для чисел Мерсенна. Очевидный недостаток этого теста заключается в его применимости только к ряду чисел определённого вида. Среди других примеров можно привести основанные на малой теореме Ферма

Вероятностные тесты простоты [ править | править код ]

К этой категории относятся:

Тесты простоты в криптографии [ править | править код ]

В настоящее время простые числа широко применяются в области защиты информации. Прежде всего, это вызвано изобретением метода шифрования с открытым ключом, который используется при шифровании информации и в алгоритмах электронной цифровой подписи. На данный момент по стандартам размер простых чисел, используемых при формировании цифровой подписи с использованием эллиптических кривых, составляет в соответствии с ГОСТ Р 34.10-2012 не менее 254 бит. Для столь больших чисел вопрос определения простоты числа является крайне сложным. Простые методы, такие, как метод перебора, непригодны для использования из-за того, что требуют чрезвычайно много вычислительных ресурсов и большого времени работы [6] .

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

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

Простые числа – это числа, которые делятся только на себя и на 1; все остальные числа называются составными числами. Существует множество способов определения того, является ли число простым. Некоторые способы являются относительно простыми, но они не подходят для больших чисел. Другие способы, применимые для больших чисел, фактически представляют собой вероятностные алгоритмы, которые иногда ошибочно характеризуют число как простое или составное.

Метод 1 Перебор делителей

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

1. 1 Пусть n – проверяемое число. Согласно этому методу вы должны разделить число n на все возможные целые делители. При больших значениях n, например, n = 101, проверка каждого делителя займет много времени. Но существуют способы уменьшить количество делителей, которые нужно проверить.
2. 2 Определите, является ли число n четным. Любое четное число делится на 2. Если число n – четное, то можно сразу заявить, что оно не является простым (то есть является составным числом). Для быстрого определения четности числа обратите внимание на его последнюю цифру. Если последняя цифра 2, 4, 6, 8,0, то число является четным и не является простым.
3. Единственное исключение из этого правила – число 2. Так как оно делится нацело только на себя и на 1, то число 2 – простое число. Таким образом, число 2 является единственным четным простым числом.
4. 3 Разделите n на каждое число от 2 до n-1. Так как делитель меньше делимого, то проверка всех делителей меньших n и больших 2 должна показать, является ли n простым числом. Вы начинаете с числа большего 2, потому что четные числа (которые кратны 2) не являются простыми числами. Это далеко не самый эффективный способ тестирования чисел на простоту, но здесь существует несколько методов оптимизации проверки.
5. Например, проверим число 11. В этом случае разделим (нацело) 11 на 3, 4, 5, 6, 7, 8, 9, 10. Так как ни одно из этих чисел не делит (нацело) 11, то число 11 – простое число.
6. 4 Чтобы сэкономить время, проверьте делители до округленного значения квадратного корня (n). Проверка всех делителей от 2 до n-1 может занять много времени. Например, если вы хотите проверить число 103, то вам придется протестировать следующие делители: 3, 4, 5, 6, 7. и так далее вплоть до 102! Но этого можно избежать – проверьте только делители от 2 до округленного значения квадратного корня (n).
7. Объяснение этого принципа. Рассмотрим множители 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2, 100 × 1. Обратите внимание, что после пары множителей 10 × 10 все пары множителей повторяются (только множители в этих парах переставлены местами). Поэтому вы можете игнорировать делители числа n большие, чем квадратный корень (n).
8. Например, проверим n = 37. Не нужно тестировать все делители от 3 до 36. Вместо этого проверьте делители между 2 и округленным значением квадратного корня (37).
9. Квадратный корень (37) = 6,08. Округлите это число до 7.
10. 37 не делится на 3, 4, 5, 6, 7, поэтому оно – простое.
11. 5 Для дальнейшей экономии времени тестируйте только простые делители. По определению любое составное число может быть выражено как произведение двух или более простых чисел. Поэтому деление числа n на составной делитель – лишняя операция, повторяющая многократное деление числа n на простые делители. Таким образом, вы можете еще больше сузить тестируемый ряд делителей.
12. Это означает, что все четные делители и все делители, кратные простым числам, могут быть опущены.
13. Например, проверим число 103. Квадратный корень из 103 округляется до 11. Простые делители от 2 до 11 это 3, 5, 7, 11. Делители 4, 6, 8, 9, 10 можно опустить (9 кратно 3, а все остальные делители – четные числа). Таким образом, вы уменьшили ряд тестируемых делителей до четырех чисел.
14. Делители 3, 5, 7, 11 не делят (нацело) число 103, поэтому оно – простое.

Метод 2 Тест Ферма

В 1640 году французский математик Пьер Ферма впервые сформулировал теорему (малая теорема Ферма), которая используется при определении простоты числа. Фактически, тест Ферма служит для определения составных чисел, а не простых. Этот тест с уверенностью определяет, является ли число составным, или определяет, что число «скорее всего» простое. Тест Ферма полезен в случаях, когда перебор делителей непрактичен и когда доступен список чисел, являющихся исключениями из теоремы.

1. 1 Пусть n – проверяемое число. Как отмечалось выше, иногда тест ложно идентифицирует составные числа как простые. Поэтому необходимо проверить ответ (способ проверки ответа описан ниже).
2. 2 Выберите любое целое число «а» от 2 до n-1 (включительно).
3. Например, проверим на простоту число 100. Допустим, а = 3.
4. 3 Вычислите an (mod n). Вычисление этого выражения потребует некоторых знаний из модульной арифметики. В модульной арифметике при достижении определенного значения, называемого модулем, отсчет чисел начинается с нуля. Представьте это как часы: час после полудня – это 1:00, а не 13:00, то есть время после полудня отсчитывается с нуля. Модуль обозначается как mod n. Таким образом, вычислите a n (mod n).
5. Одним из способов вычисления будет вычислить a n , а затем разделить результат на n, а в качестве ответа записать остаток деления. В этом случае рекомендуется использовать специализированные калькуляторы с функцией модуля , так как они мгновенно вычисляют остаток при делении больших чисел.
6. В нашем примере, при делении 3 100 /100 получается остаток 1. Таким образом, 3 100 (mod 100) = 1.
7. 4 Если у вас нет специализированного калькулятора, при вычислении остатка вручную используйте экспоненциальную запись числа.
8. В нашем примере вручную вычислите 3 100 (mod 100). 3 100 = 515377520732011331036461129765621272702107522001 – огромное число, с которым трудно работать. Вместо того, чтобы работать с 48-значным числом, представьте 3 100 как (((((((3 2 )*3) 2 ) 2 ) 2 )*3) 2 ) 2 . Напомним, что при возведении степени в степень показатели перемножаются: ((x y ) z = x yz ).
9. Теперь определите остаток. В (((((((3 2 )*3) 2 ) 2 ) 2 )*3) 2 ) 2 начните решение с внутренних скобок и каждый раз результат делите на 100. При получении остатка используйте его в дальнейших расчетах (а не в качестве ответа).
10. (((((((9)*3) 2 ) 2 ) 2 )*3) 2 ) 2 – 9/100 – остатка нет.
11. ((((((27) 2 ) 2 ) 2 )*3) 2 ) 2 – 27/100 – остатка нет.
12. (((((729) 2 ) 2 )*3) 2 ) 2 – 729/100 = 7(ост.29). Остаток 29. Продолжите вычисления с числом 29.
13. ((((29 2 =841) 2 )*3) 2 ) 2 – 841/100 = 8(ост.41). Остаток 41. Продолжите вычисления с числом 41.
14. (((41 2 = 1681)*3) 2 ) 2 – 1681/100 = 16(ост.81). Остаток 81. Продолжите вычисления с числом 81.
15. ((81*3 = 243) 2 ) 2 – 243/100 = 2(ост. 43). Остаток 43. Продолжите вычисления с числом 43.
16. (43 2 = 1849) 2 – 1849/100 = 18(ост.49). Остаток 49. Продолжите вычисления с числом 49.
17. 49 2 = 2401 – 2401/100 = 24(ост.1). Конечный остаток 1. Таким образом, 3 100 (mod 100) = 1 (такой же результат был получен при вычислении на калькуляторе).
18. 5 Проверьте равенство:an (mod n) = a (mod n). Если оно не соблюдено, то n – составное число. Если оно соблюдено, то n, скорее всего, простое число (но не обязательно). Повторите тест с разными значениями «а», чтобы удостовериться в правильности ответа. Но есть составные числа, удовлетворяющие условию Ферма при любых значениях «а». Они называются числами Кармайкла (самое малое из них – число 561).
19. В нашем примере 3 100 (mod 100) = 1, а 100 (mod 100 ) = 0. Таким образом, 1 ≠ 0 и 100 – составное число.
20. 6 Используйте числа Кармайкла в качестве гарантии правильности ответа. Числа Кармайкла имеют вид (6k + 1)(12k + 1)(18k + 1) для целых значений k, когда каждый делитель является простым. Вы можете найти полный список чисел Кармайкла в интернете.

Метод 3 Тест Миллера-Рабина

Тест Миллера-Рабина эффективно определяет, является ли число составным (и лучше обрабатывает исключения, такие как числа Кармайкла).

1. 1 Пусть n – нечетное число, которое нужно протестировать на простоту.
2. 2 Запишите n-1 в виде 2 s × d, где d – нечетное число. Если n – простое, то оно должно быть нечетным. Поэтому n-1 – четное. Так как n-1 – четное число, то оно может быть представлено в виде произведения числа 2 в некоторой степени на нечетное число. Например, 4 = 2 2 × 1, 80 = 2 4 × 5 и так далее.
3. Например, определите простоту числа n = 321. 321 – 1 = 320, а 320 = 2 6 × 5. То есть s=6 и d=5.
4. Например, возьмем более сложное число n = 371. 371 – 1 = 370, а 370 = 2 1 × 185. То есть d=185, что значительно усложнит вычисления.
5. 3 Возьмите любое число «а» между 2 и n-1.
6. В нашем примере для n = 321 выберите а = 100.
7. 4 Вычислите ad (mod n). Если ad = 1 или -1 (mod n), то число n проходит тест Миллера-Рабина и, скорее всего, является простым. Однако этот тест, как и тест Ферма, не может определить простоту числа с абсолютной уверенностью.
8. В нашем примере для n = 321: a d (mod n) = 100 5 (mod 321). 100 5 = 10,000,000,000 (mod 321) = 313. Для нахождения остатка 100 5 /321 используйте специализированный калькулятор или расчет вручную (описанный выше).
9. Так как результат не равен 1 или -1, вы не можете утверждать, что n – простое число.
10. 5 Если результат не равен 1 или -1, вычислите a 2d , a 4d , ... и так далее до a 2 s-1 d . Если один из результатов равен 1 или -1 (mod n), то число n проходит тест Миллера- Рабина и, скорее всего, является простым. Если n проходит тест, проверьте ответ (смотрите следующий шаг). Если n не проходит любой из этих тестов, то n – составное число.
11. Напомним, что в нашем примере а=100, s=6, d=5. Продолжите проверку следующим образом:
12. 100 2d = 10 = 1 × 10 20 .
13. 1 × 10 20 (mod 321) = 64. 64 ≠ 1 или -1. Продолжите вычисления.
14. 100 4d = 20 = 1 × 10 40 .
15. 1 × 10 40 (mod 321) = 244. 244 ≠ 1 или -1.
16. Здесь вы можете закончить вычисления. s – 1 = 6 – 1 = 5. Вы достигли предельного значения 4d = 2 2 . Так как ни один из расчетов не дал 1 или -1, вы можете с уверенностью заявить, что n = 321 – составное число.
17. 6 Если n проходит тест Миллера- Рабина, повторите тест с разными значениями «а», чтобы удостовериться в правильности ответа. Если n – простое число, оно пройдет тест с любым значением «а». Если n – составное число, не менее трех четвертей значений «а» не пройдут тест. Поэтому тест Миллера- Рабина является более надежным, чем тест Ферма, в котором составные числа Кармайкла проходят тест при любом значении «а».

Условие задачи 2.30

Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.

Для начала напомню, что такое простые числа.

Простое число – это натуральное число, которое имеет ровно два различных натуральных делителя – единицу и самого себя.

То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.

Например, простыми числами являются 2, 3, 5 и т.п.

А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.

Если вы подзабыли, что такое натуральное число, то см. здесь.

А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения – это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.

Как определить простое число в Паскале

Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.

ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).

Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.

В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.

А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.

Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).

Саму функцию здесь приводить не буду – посмотрите её в примерах программ.