Загрузить PDF
Загрузить PDF
Простые числа — это числа, которые делятся только на себя и на 1. Все остальные числа называются составными числами. Есть множество способов определить, является ли число простым, и все они имеют свои преимущества и недостатки. С одной стороны, некоторые методы отличаются большой точностью, но они довольно сложны, если вы имеете дело с большими числами. С другой стороны, существуют намного более быстрые способы, но они могут привести к неправильным результатам. Выбор подходящего метода зависит от того, с насколько большими числами вы работаете.
Шаги
Примечание: во всех формулах n обозначает проверяемое число.
-
Перебор делителей. Достаточно поделить n на все простые числа от 2 до округленного значения( ).
-
Малая теорема Ферма. Предупреждение: иногда тест ложно идентифицирует составные числа как простые, даже для всех величин a.
- Выберем целое число a , такое что 2 ≤ a ≤ n - 1.
- Если a n (mod n) = a (mod n), то число, вероятно, простое. Если равенство не выполняется, число n является составным.
- Проверьте данное равенство для нескольких значений a , чтобы увеличить вероятность того, что проверяемое число действительно является простым.
-
Тест Миллера-Рабина. Предупреждение: иногда, хотя и редко, для нескольких значений a тест ложно идентифицирует составные числа как простые.
- Найдите величины s и d, такие чтобы .
- Выберите целое число a в интервале 2 ≤ a ≤ n - 1.
- Если a d = +1 (mod n) или -1 (mod n), то n, вероятно, является простым числом. В этом случае перейдите к результату теста. Если равенство не выполняется, перейдите к следующему шагу.
- Возведите ответ в квадрат ( ). Если получится -1 (mod n), то n, вероятно, простое число. В этом случае перейдите к результату теста. Если равенство не выполняется, повторите ( и так далее) до .
- Если на каком-то шаге после возведения в квадрат числа, отличного от (mod n), у вас получилось +1 (mod n), значит n является составным числом. Если (mod n), то n не является простым числом.
- Результат теста: если n прошло тест, повторите его для других значений a , чтобы повысить степень достоверности.
Реклама
-
Перебор делителей. По определению число n является простым лишь в том случае, если оно не делится без остатка на 2 и другие целые числа, кроме 1 и самого себя. Приведенная выше формула позволяет удалить ненужные шаги и сэкономить время: например, после проверки того, делится ли число на 3, нет необходимости проверять, делится ли оно на 9.
- Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.
-
Узнайте о модульной арифметике. Операция "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 является простым числом.
-
Для больших чисел используйте модульную арифметику. Если у вас под рукой нет калькулятора с функцией mod или калькулятор не рассчитан на операции с такими большими числами, используйте свойства степеней и модульную арифметику, чтобы облегчить вычисления. [5] X Источник информации Ниже приведен пример для mod 50:
- Перепишите выражение в более удобном виде: mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
- mod 50 = mod 50 mod 50) mod 50. Здесь мы учли свойство модульного умножения.
- mod 50 = 43.
- mod 50 mod 50) mod 50 = mod 50.
- mod 50.
- .
Реклама
-
Выберите два числа. Одно из чисел должно быть составным, а второе — как раз то, простоту которого вы хотите проверить.
- Число1 = 35
- Число2 = 97
-
Выберите два значения, которые больше нуля и соответственно меньше чисел Число1 и Число2. Эти значения не должны совпадать друг с другом.
- Значение1 = 1
- Значение2 = 2
-
Вычислите 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
- Вычислите MMI
-
Создайте таблицу для каждой 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
- Для MMI1
-
Вычислите (Значение1 * Число2 * MMI1 + Значение2 * Число1 * MMI2) % (Число1 * Число2)
- Ответ = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
- Ответ = (2619 + 4270) % 3395
- Ответ = 99
-
Проверьте, что Число1 не является простым
- Вычислите (Ответ – Значение1) % Число1
- 99 – 1 % 35 = 28
- Так как 28 больше 0, то 35 не является простым числом.
-
Проверьте, что Число2 является простым.
- Вычислите (Ответ – Значение2)% Число2
- 99 – 2 % 97 = 0
- Так как 0 равен 0, то 97 — скорее всего простое число.
-
Повторите шаги с 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).
Реклама - Если в шаге 7 получается 0:
Советы
- Простые числа от 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 Источник информации
- Хотя при работе с большими числами перебор делителей является трудоемким способом проверки, он довольно эффективен в случае малых чисел. Даже в случае больших чисел начинают с тестирования малых делителей, а затем переходят к более сложным методам проверки простоты чисел (если малые делители не найдены).
Реклама
Что вам понадобится
- Бумага, ручка или компьютер
Источники
- ↑ http://betterexplained.com/articles/fun-with-modular-arithmetic/
- ↑ http://mathworld.wolfram.com/FermatsLittleTheorem.html
- ↑ http://www.cs.cornell.edu/courses/cs4820/2010sp/handouts/MillerRabin.pdf
- ↑ https://books.google.com/books?id=QbVtCQAAQBAJ&dq=miller-rabin+1/4+false+positives
- ↑ https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation
- ↑ Online Encyclopedia of Integer Sequences, A000040
- Topcoder.com — источник с кодами и описанием изложенных выше методов
- Online Prime Number Checker — проверка чисел, содержащих до 5000 цифр
Об этой статье
Эту страницу просматривали 217 398 раз.
Реклама
