§ 7.4. Тестирование простоты и системы символьных вычислений

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

Рациональное зерно в таком использовании теста Миллера прорастает из теоремы Рабина. Пусть нечетное составное число. Основание между выберем случайным образом. Из теоремы Рабина следует, что вероятность неопределенного результата при применении теста Миллера к и не превосходит

Так что правдоподобно предположение: число в этом случае будет составным с вероятностью 1/4. Если теперь выбрать к различный оснований, то вероятность станет равной 1/4. Поэтому, беря все больше и больше оснований, мы можем сделать вероятность сколь угодно малой.

Эти рассуждения приводят к вероятностному тесту Ра-бина на простоту. Поскольку он вероятностный, нам нужно решить, насколько малой должна быть вероятность ошибки. Предположим, нам нужно, чтобы вероятность ошибки не превосходила и пусть k — такое натуральное число, для которого Тогда тест Рабина выбирает к оснований и применяет тест Миллера по каждому из них. Из вышеприведенных рассуждений вытекает, что в случае неопределенного ответа на тест Миллера по всем этим основаниям вероятность того, что проверяемое число все же окажется составным, будет меньше или равна 1/4, т.е. меньше требуемого Как же выбираются основания? Конечно, удобнее было бы брать основания поменьше, иначе вычисления, необходимые для теста Миллера, будут занимать слишком много времени. Как правило, выбирают первые к положительных простых чисел.

Естественно, мы хотим быть абсолютно уверены в том, что числа, прошедшие тест, будут простыми. Для этого необходимо выбрать очень маленьким. Например, пусть Так как 1/440 — величина порядка нам нужно выбрать 40 оснований, чтобы вероятность ошибки была меньше Допустим, что в качестве оснований выбрали 40 первых простых чисел. К сожалению, есть число Кармайкла (из 397 знаков), для которого тест Миллера дает неопределенный ответ, если в качестве оснований берутся простые числа, не превосходящие 300 (см. [5]). А так как существует ровно 62 таких простых числа, тест, проверяя упомянутое число Кармайкла по всем основаниям, которые мы выберем, будет выдавать неопределенный ответ!

Посмотрим как выполняется тест Рабина в одной широко известной системе символьных вычислений. Конечно, каждая программа использует ей одной свойственную стратегию. Например, Maple V.2 проверяет простоту в три этапа. Сначала

подбираются простые делители тестируемого числа, не превосходящие 103. Если таких делителей не обнаружено, то программа применяет тест Миллера по основаниям 2,3,5,7 и 11. А в последнюю очередь проверяется, что данное число не относится ни к одному из следующих семейств:

или

Причиной необходимости последнего этапа служит информация о том, что в этих семействах найдено довольно много строго псевдопростых чисел по тем основаниям, которые используются программой (см. [38]). Тем не менее, составное число

определяется Мар1еом как простое. Его наименьший простой делитель равен 286472803. В более поздних версиях тест на простоту был модифицирован, так что теперь это число правильно идентифицируется как составное.

Axiom 1.1 применяет другую стратегию: подбирает количество оснований в зависимости от числа, которое собирается тестировать. Было показано, что тест, используемый Axiom 1.1, правильно обнаруживает простоту чисел, если они меньше, чем 341550071728321 (см. [26]). Для чисел, выходящих за эту границу, Axiom 1.1 в качестве оснований для теста Миллера использует 10 наименьших простых чисел. Подобно Maple, эта программа делает дополнительные проверки для чисел, считающихся особенно неприятными. И этот тест не совершенен; он дает сбой на составном числе из 56 знаков.

Сначала можно подумать, что стратегии, выбранные для этих программ, дадут «совершенные» тесты, стоит только подобрать подходящие основания. Но печальная истина в том,

что это невозможно сделать даже теоретически. Одно из следствий, вытекающих из работы Альфорда, Гранвилля и Померанца над числами Кармайкла, состоит в следующем:

«Для любого конечного набора оснований найдется бесконечно много чисел Кармайкла, строго псевдопростых по всем этим основаниям.»

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

Подробности о тестировании простых чисел этими программами, а также примеры, на которых они дают сбой, можно найти в [5]. В главе 11 мы будем изучать тесты, которые позволят нам с уверенностью определять простоту чисел. Но если быть до конца откровенным, они не такие простые и эффективные, как тест Миллера.

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)