Метод факторизации многоразрядных чисел на основе свойств квадратичности вычетов в системе остаточных классов

Abstract

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