Метод высоковероятностного определения простых многоразрядных чисел на основе векторно-модульного умножения

Abstract

Проблема принадлежности заданного натурального числа к классу простых или составных чисел является актуальной не только в математике, но и в компьютерных науках. Отличить простое число от составного, а также разложить последнее на простые множители, является одной из важнейших задач арифметики. Поиск больших простых чисел, например, необходим для обеспечения надежности систем шифрования информации с открытым ключом. Безопасность последних базируется на утверждении, что операция умножения двух больших простых чисел является односторонней функцией. В данной статье разработан высоковероятностный метод проверки на простоту многоразрядных чисел, который, в отличие от известных, характеризуется меньшей вычислительной сложностью и сложностью реализации алгоритма. Представлены структурная схема и блок-схема алгоритма для реализации предложенного метода. Исследованы случаи исключений из принятого условия, количество которых свидетельствует о высокой вероятности обнаружения простого числа.