Иллюстрированный самоучитель по Mathematica 5

Простые числа вида k * 2 n +1

Сначала определим функцию, которая по заданному номеру п простого числа q находит t – решение сравнения 3*2ⁿ +1^0 (mod q) и 5 – показатель 2 по модулю q, если такое решение существует.

Теперь с помощью этой функции можно сгенерировать таблицу остатков и соответствующих им модулей.

Чтобы в таблице сначала шли меньшие модули s (они помогают отбраковать больше кандидатов), таблицу пришлось отсортировать, предварительно вычеркнув из нее элементы NULL, которые соответствуют тем простым модулям д, для которых сравнение 3*2ⁿ +1 = 0 (mod q) неразрешимо.

Каждая пара в этой таблице описывает арифметическую профессию из показателей, для которых выполняется некоторое тождественное сравнение. Пусть, например, в таблице имеется пара (s, t). Она была получена для некоторого простого числа q. Ее наличие в таблице означает, что 3*2ⁿ⁺¹ +1 = 0 (mod q) для любых натуральных k.

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

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

Заметьте, что программа отличается от аналогичной программы для чисел вида 5*2ⁿ + 1. Отличие связано с тем, что на этот раз перебор не ограничивается только нечетными показателями. Конечно, как и для чисел вида 5-2ⁿ + 1, количество отбракованных чисел и время отбраковки зависят от размера таблицы t. Сначала давайте сгенерируем совсем небольшую таблицу.

Теперь запускаем программу.