Тест Люка-Лемера для сверхбольших чисел Мерсенна

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

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

Область применения - Теория чисел, тестирование производительности вычислительных систем.
 

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

В программе реализован разработанный авторами алгоритм вычисления целочисленного остатка при делении на сверхбольшое чисто Мерсенна в двоичной системе счисления.  Целочисленный остаток в двоичной системе счисления определяется как сумма двух частей в записи делимого. Первая часть записи от разряда единиц (нулевой разряд) до разряда с номером (PM - 1), где PM - показатель степени числа Мерсенна. Вторая часть записи от разряда с номером PM и до старшего разряда в записи делимого. Использование данного алгоритма позволяет существенно снизить трудоемкость теста Люка-Лемера и время работы программы.

Алгоритм описан в статье Гончаренко В.Е. "Оптимизация вычислений целочисленного остатка в тесте Люка-Лемера для сверхбольших чисел Мерсенна" в сборнике статей Международной научно-практической конференции "Теоретические и практические вопросы науки XXI века", 2014 г., г. Уфа, Ч2.

Функциональные возможности - Функциональные возможности могут быть ограничены размером свободной динамической памяти ЭВМ. Размер используемых в программе двух динамических линейных массивов равен значению степени PM числа Мерсенна, которое в современных вычислениях принимает значение более 57 млн. В программе предусматривается проверка достаточности оперативной памяти для текущих вычислений.

Инструментальные средства создания - Microsoft  Visual Studio 2010, Visual C++.

Во Вложении прикреплен файл исходного кода программы на языке C++.

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

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

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