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

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

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

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