Небольшая криптографическая бибилиотека для факторизации целых чисел
- Факторизация целых чисел (100 бит) в разумные пределы времени.
- Некоторые побочные алгоритмы, такие как:
- Обычный и расширенный алгоритм Евклида.
- Быстрое возведение в степень по модулю.
- Вычисление символа Лежандра.
- Вероятностный тест Миллера-Рабина.
- Решение СЛАУ в GF(2).
Использует алгоритм квадратичного решета:
- 1 этап - создание факторной базы. Это такие простые числа, которые образуют квадратичный вычет по модулю n (факторизуемое число), и не превышают заданную границу B.
- 2 этап - просеивание или получение B-гладких чисел. B-гладкие число это такое число, у которого все простые делители не превосходят заданную границу B. Используется неэффективное решение, которое не может работать параллельно в нескольких потоках.
- 3 этап - решение СЛАУ в GF(2). Также используется неэффективное решение методом Гаусса.
- 4 этап - нахождение нетривиальных делителей среди решений СЛАУ.
- С++20
- CMake 3.16
- Библиотека длинной арифметики. Желательно Boost.
Библиотека поставляется в виде заголовков, тем самым, достаточно подключить необходимый заголовочный файл и указать компилятору путь к директории include. Также, можно подключить как подпроект в cmake файле.
⏳ Ручной подбор параметров B и L. Необходимо реализовать автоматический подбор.
⏳ Просеивание не может выполняться в многопоточном режиме, необходимо переписать алгоритм.
⏳ Решение СЛАУ использует метод Гаусса. Учитывая, что поле конечно и вовсе двоичное, то существуют более специализированные и эффективные алгоритмы.