Оптимизированный тест Люка-Лемера для сверхбольших чисел Мерсенна

Тип разработки: 
Программа
Регистрационный номер в ФАП: 
PR19008
Дата регистрации в ФАП: 
2019-12-30
Тематическая направленность: 
Теория чисел
Разработчики программы (базы данных): 
Аннотация: 

Назначение - программа предназначена для проверки сверхбольших чисел Мерсенна на принадлежность их к простым числам.
Область применения - теория чисел, тестирование производительности вычислительных систем.

Используемый алгоритм - Используется алгоритм теста Люка-Лемера, в котором сверхбольшие числа представлены в виде динамических линейных массивов в двоичной системе счисления. Арифметические операции над числами выполняются по алгоритмам длинной арифметики. Поиск очередного самого большого простого числа Мерсенна вида 2^PM - 1 , где РM, в свою очередь, простое число, принимающее значения более 57 млн, является весьма трудоемкой задачей. В соответствии с тестом Люка-Лемера выполняется (PM -2) итераций цикла, на каждой из которых определяется целочисленный остаток от деления на число Мерсенна. Эта операция и определяет в основном трудоемкость теста. Только при представлении чисел в двоичной системе счисления представляется возможность упростить эту операцию до одной элементарной операции сложения.

В программе реализован разработанный авторами алгоритм вычисления целочисленного остатка при делении на сверхбольшое чисто Мерсенна в двоичной системе счисления. Целочисленный остаток в двоичной системе счисления определяется как сумма двух частей в записи делимого. Первая часть записи от разряда единиц (нулевой разряд) до разряда с номером (PM - 1), где PM - показатель степени числа Мерсенна. Вторая часть записи от разряда с номером PM и до старшего разряда в записи делимого. Использование данного алгоритма позволяет существенно снизить трудоемкость теста Люка-Лемера и время работы программы. Дополнительно к ранее зарегистрированному алгоритму "Тест Люка-Лемера для сверхбольших чисел Мерсенна" в два раза сокращено количество итераций вложенных циклов при вычислении квадрата целочисленного остаттка с предыдущей итерации теста. При возведении числа в квадрат в двоичной системе счисления сочетание цифр множимого и множителя с одинаковыми номерами разрядов встречаются однократно и в итог сносится 1, а с разными - дважды и в итог сносится 2. Учет этого обстоятельства во фрагменте программы позволил в два раза снизтить общую трудоемкость теста. 
Функциональные возможности - Функциональные возможности могут быть ограничены размером свободной динамической памяти ЭВМ. Размер используемых в программе двух динамических линейных массивов равен значению степени PM числа Мерсенна, которое в современных вычислениях принимает значение более 57 млн. В программе предусматривается проверка достаточности оперативной памяти для текущих вычислений.
Инструментальные средства создания - Microsoft  Visual Studio 2010, Visual C++.

Версия регистрируемой программы (базы данных): 
исходный код на С++
Использованные при разработке материалы: 
№2017615919 от 26 мая 2017 г., авторы Гончаренко В.Е. и Тихонов А.А.
Регистрационный номер в Роспатенте: 
№2017615919 от 26 мая 2017 г., авторы Гончаренко В.Е. и Тихонов А.А.
Признак доступности программы (базы данных): 
полностью свободный доступ
Требования к аппаратным и программным средствам: 

Совместимые с IBM PC

Контактная информация: 
V_E_G_A@mail.ru
ВложениеРазмер
test_mersenn.doc33.5 КБ