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

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

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

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

Каждая пара в этой таблице описывает арифметическую профессию из показателей, для которых выполняется некоторое тождественное сравнение. Пусть, например, в таблице имеется пара (s, .t). Она была получена для некоторого простого числа q.

Ее наличие в таблице означает, что 5*2ⁿ +1 + 1 = 0 (mod q) для любых натуральных k.

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

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

Конечно, количество отбракованных чисел и время отбраковки зависят от размера таблицы t. Сначала давайте возьмем совсем небольшую таблицу.

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

Как видите, за 5 секунд удалось отбраковать более 72% чисел! Давайте попробуем увеличить таблицу.