Как проверить, является ли число простым

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

Часть 1

Часть 1 из 3:

Тесты простоты

Загрузить PDF

Примечание: во всех формулах n обозначает проверяемое число.

Достаточно поделить n на все простые числа от 2 до округленного значения( ${\sqrt {n}}$ ).
2
Малая теорема Ферма. Предупреждение: иногда тест ложно идентифицирует составные числа как простые, даже для всех величин a.
- Выберем целое число a, такое что 2 ≤ a ≤ n - 1.
- Если aⁿ (mod n) = a (mod n), то число, вероятно, простое. Если равенство не выполняется, число n является составным.
- Проверьте данное равенство для нескольких значений a, чтобы увеличить вероятность того, что проверяемое число действительно является простым.
3
Тест Миллера-Рабина. Предупреждение: иногда, хотя и редко, для нескольких значений a тест ложно идентифицирует составные числа как простые.
- Найдите величины s и d, такие чтобы $n-1=2^{s}*d$ .
- Выберите целое число a в интервале 2 ≤ a ≤ n - 1.
- Если a^d = +1 (mod n) или -1 (mod n), то n, вероятно, является простым числом. В этом случае перейдите к результату теста. Если равенство не выполняется, перейдите к следующему шагу.
- Возведите ответ в квадрат ( $a^{2d}$ ). Если получится -1 (mod n), то n, вероятно, простое число. В этом случае перейдите к результату теста. Если равенство не выполняется, повторите ( $a^{4d}$ и так далее) до $a^{2^{s-1}d}$ .
- Если на каком-то шаге после возведения в квадрат числа, отличного от $\pm 1$ (mod n), у вас получилось +1 (mod n), значит n является составным числом. Если $a^{2^{s-1}d}\neq \pm 1$ (mod n), то n не является простым числом.
- Результат теста: если n прошло тест, повторите его для других значений a, чтобы повысить степень достоверности.
Реклама

Часть 2

Часть 2 из 3:

Как работают тесты простоты

Загрузить PDF

1
Перебор делителей. По определению число n является простым лишь в том случае, если оно не делится без остатка на 2 и другие целые числа, кроме 1 и самого себя. Приведенная выше формула позволяет удалить ненужные шаги и сэкономить время: например, после проверки того, делится ли число на 3, нет необходимости проверять, делится ли оно на 9.
- Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.
2
Узнайте о модульной арифметике. Операция "x mod y" (mod является сокращением латинского слова "modulo", то есть “модуль”) означает "поделить x на y и найти остаток".^{[1]XИсточник информации} Иными словами, в модульной арифметике по достижении определенной величины, которую называют модулем, числа вновь "превращаются" в ноль. Например, часы отсчитывают время с модулем 12: они показывают 10, 11 и 12 часов, а затем возвращаются к 1.
- Во многих калькуляторах есть клавиша mod. В конце данного раздела показано, как вручную вычислять эту функцию для больших чисел.
Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке "чисел Кармайкла" (составных чисел, которые удовлетворяют данному тесту) и "псевдопростых чисел Ферма" (эти числа соответствуют условиям теста лишь при некоторых значениях a).^{[2]XИсточник информации}
Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма.^{[3]XИсточник информации} Составное число не будет принято за простое, если провести расчеты для более ¼ значений a.^{[4]XИсточник информации} Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.
5
Для больших чисел используйте модульную арифметику. Если у вас под рукой нет калькулятора с функцией mod или калькулятор не рассчитан на операции с такими большими числами, используйте свойства степеней и модульную арифметику, чтобы облегчить вычисления.^{[5]XИсточник информации} Ниже приведен пример для $3^{50}$ $How.com.vn Русский: 3^{{50}}$ mod 50:
- Перепишите выражение в более удобном виде: $(3^{25}*3^{25})$ mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
- $(3^{25}*3^{25})$ mod 50 = $(3^{25}$ mod 50 $*3^{25}$ mod 50) mod 50. Здесь мы учли свойство модульного умножения.
- $3^{25}$ mod 50 = 43.
- $(3^{25}$ mod 50 $*3^{25}$ mod 50) mod 50 = $(43*43)$ mod 50.
- $=1849$ mod 50.
- $=49$ .
Реклама

Часть 3

Часть 3 из 3:

Использование китайской теоремы об остатках

Загрузить PDF

1
Выберите два числа. Одно из чисел должно быть составным, а второе — как раз то, простоту которого вы хотите проверить.
- Число1 = 35
- Число2 = 97
2
Выберите два значения, которые больше нуля и соответственно меньше чисел Число1 и Число2. Эти значения не должны совпадать друг с другом.
- Значение1 = 1
- Значение2 = 2
3
Вычислите MMI (математическую мультпликативную инверсию) для Числа1 и Числа2.
- Вычислите MMI
  - MMI1 = Число2 ^ -1 Mod Число1
  - MMI2 = Число1 ^ -1 Mod Число2
- Только для простых чисел (это даст число для составных чисел, но оно не будет его MMI):
  - MMI1 = (Число2 ^ (Число1-2)) % Число1
  - MMI2 = (Число1 ^ (Число2-2)) % Число2
- Например:
  - MMI1 = (97 ^ 33) % 35
  - MMI2 = (35 ^ 95) % 97
4
Создайте таблицу для каждой MMI вплоть до модулей log2:
- Для MMI1
  - F(1) = Число2 % Число1 = 97 % 35 = 27
  - F(2) = F(1) * F(1) % Число1 = 27 * 27 % 35 = 29
  - F(4) = F(2) * F(2) % Число1 = 29 * 29 % 35 = 1
  - F(8) = F(4) * F(4) % Число1 = 1 * 1 % 35 = 1
  - F(16) =F(8) * F(8) % Число1 = 1 * 1 % 35 = 1
  - F(32) =F(16) * F(16) % Число1 = 1 * 1 % 35 = 1
- Вычислите парные Число1 - 2
  - 35 -2 = 33 (10001) по основанию 2
  - MMI1 = F(33) = F(32) * F(1) mod 35
  - MMI1 = F(33) = 1 * 27 mod 35
  - MMI1 = 27
- Для MMI2
  - F(1) = Число1 % Число2 = 35 % 97 = 35
  - F(2) = F(1) * F(1) % Число2 = 35 * 35 mod 97 = 61
  - F(4) = F(2) * F(2) % Число2 = 61 * 61 mod 97 = 35
  - F(8) = F(4) * F(4) % Число2 = 35 * 35 mod 97 = 61
  - F(16) = F(8) * F(8) % Число2 = 61 * 61 mod 97 = 35
  - F(32) = F(16) * F(16) % Число2 = 35 * 35 mod 97 = 61
  - F(64) = F(32) * F(32) % Число2 = 61 * 61 mod 97 = 35
  - F(128) = F(64) * F(64) % Число2 = 35 * 35 mod 97 = 61
- Вычислите парные Число2 - 2
  - 97 – 2 = 95 = (1011111) по основанию 2
  - MMI2 = (((((F(64) * F(16) % 97) * F(8) % 97) * F(4) % 97) * F(2) % 97) * F(1) % 97)
  - MMI2 = (((((35 * 35) %97) * 61) % 97) * 35 % 97) * 61 % 97) * 35 % 97)
  - MMI2 = 61
5
Вычислите (Значение1 * Число2 * MMI1 + Значение2 * Число1 * MMI2) % (Число1 * Число2)
- Ответ = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
- Ответ = (2619 + 4270) % 3395
- Ответ = 99
6
Проверьте, что Число1 не является простым
- Вычислите (Ответ – Значение1) % Число1
- 99 – 1 % 35 = 28
- Так как 28 больше 0, то 35 не является простым числом.
7
Проверьте, что Число2 является простым.
- Вычислите (Ответ – Значение2)% Число2
- 99 – 2 % 97 = 0
- Так как 0 равен 0, то 97 — скорее всего простое число.
8
Повторите шаги с 1 по 7 по меньшей мере еще два раза.
- Если в шаге 7 получается 0:
  - Используйте другое Число1, если Число1 не является простым.
  - Используйте другое Число1, если Число1 является простым. В этом случае в шагах 6 и 7 должен получиться 0.
  - Используйте другие Значение1 и Значение2.
- Если в шаге 7 вы постоянно получаете 0, то с очень большой вероятностью Число2 является простым.
- Шаги с 1 по 7 могут привести к ошибке, если Число1 не является простым, а Число2 является делителем Числа1. Описанный метод работает во всех случаях, когда оба числа являются простыми.
- Причина, по которой необходимо повторять шаги с 1 по 7, заключается в том, что в некоторых случаях, даже если Число1 и Число 2 не являются простыми, в шаге 7 вы получите 0 (для одного или обоих чисел). Это случается редко. Выберите другое Число1 (составное), и если Число2 не является простым, тогда Число2 не будет равно нулю в шаге 7 (за исключением случая, когда Число1 является делителем Числа2 — здесь простые числа всегда будут равны нулю в шаге 7).
Реклама

Советы

Простые числа от 168 до 1000: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.^{[6]XИсточник информации}
Хотя при работе с большими числами перебор делителей является трудоемким способом проверки, он довольно эффективен в случае малых чисел. Даже в случае больших чисел начинают с тестирования малых делителей, а затем переходят к более сложным методам проверки простоты чисел (если малые делители не найдены).