Логотип Фонда Электронных Рубежей.
* * *
Единственный способ узнать наверняка — это разделить данное число на все предшествующие ему числа. Если оно не делится ни на одно из них, то оно является простым. Как мы видели в предыдущей главе, извлечение квадратного корня из числа может значительно сократить количество работы. Это хороший метод для небольших чисел и вычислений вручную. Например, мы хотим узнать, является ли число 101 простым или составным. Знание правил делимости может помочь нам избежать ненужной работы. Очевидно, что 101 не делится на 2, так как в противном случае его последняя цифра была бы четной или нулем. Не делится оно и на 3, так как сумма его цифр не делится на 3 (1 + 0 + 1 = 2). Также 101 не делится на 5, иначе оно оканчивалось бы на 0 или на 5. Мы также можем отбросить 4, 6 и 9, так как они кратны 2 или 3. Если мы попытаемся разделить 101 на 7, мы получим 14 и остаток 3. Значит, оно не делится и на 7. Следующее число, которое стоит проверить, — 11 (101, очевидно, не делится на 10). Деление на 11 дает 9 и остаток 2. Здесь мы можем остановиться и сказать, что 101 является простым числом, так как квадратный корень из 101 составляет примерно 10. Это означает, что наше число уже не будет делиться на любые другие оставшиеся числа, меньшие 101.
Этот метод называется перебором делителей и является самым простым и самым надежным. Проблема заключается в том, что он не оправдывает себя в случае очень больших чисел, даже если используется компьютер. Заметим, что для числа из 50 цифр потребуется проверка всех чисел длиной до 25 цифр, что более или менее соответствует корню из данного числа. Компьютеру, который способен выполнять миллиард операций деления в секунду, потребуется более 300 млн лет, чтобы закончить проверку, а к тому времени, вполне вероятно, человечество исчезнет с лица Земли!
Во всяком случае, этот метод работает достаточно хорошо для составного числа, если один из его делителей не является слишком большим. Следует иметь в виду, что для любого числа n вероятность того, что число 2 является одним из его делителей, составляет 50 %, а вероятность того, что делителем является число 3, составляет 33 % и так далее.
С другой стороны, скорость и объем памяти современных компьютеров значительно выросли, так что поиск простого числа в длинном списке иногда более эффективен, чем сложный процесс определения, является ли данное число простым.
В тестах простоты наиболее часто используется малая теорема Ферма. Напомним, что эта теорема гласит: «Если р — простое число, то не существует такого числа а у меньшего р (а и р взаимно просты), что ap-1—1 дает при делении на р отличный от нуля остаток».
Теорема имеет ограничения, поскольку, как мы видели, она дает необходимое, но не достаточное условие. Например, если взять р = 7, мы видим, что З6 — 1 делится на 7. Нет никакой гарантии, что 7 — простое число (мы-то знаем, что это простое число, потому что взяли для примера небольшие числа, но мы должны представить, что имеем дело с большими числами). Однако если взять р = 8, мы видим, что при делении З7 — 1 на 8 получается 273,25, а значит, остаток не ноль. Теперь мы уверены, что 8 — не простое число (не находя его делителей).
Мы знаем точно, что любое число, которое не проходит тест с данным основанием а у является составным.
С другой стороны, если число проходит тест и является простым, мы называем основание «ложным». И продолжаем тестирование. Вероятность обнаружения «ложных» чисел уменьшается на 1/2 с каждым тестом, так что вероятность того, что число является простым, продолжает расти.
Число р, которое, не являясь простым, проходит тест с основанием а, называется псевдопростым для этого основания. Можно дать более общее определение псевдопростого числа: число называется псевдопростым, если оно проходит тест простоты, но оказывается составным.
Дело обстоит сложнее для чисел, которые проходят тесты с любым основанием, но не являются простыми. Например, число 561 проходит тест простоты с любым основанием и все же является составным (561 = 3 х 11 х 17). Такие числа, открытые американским математиком Робертом Кармайклом (1879–1967), называются числами Кармайкла. Сегодня известно 2163 числа Кармайкла, и они находятся среди первых 25 млрд натуральных чисел. Все они имеют по крайней мере три простых делителя.