Large Prime Numbers

Большие простые числа

Программный курсовой проект 3 курса посвященный реализации библиотеки с алгоритмами, связанными с выявлением простых чисел и разложении составных чисел на простые множители (с использованием длинной арифметики).

Для работы с числами неограниченной длины используется сторонняя библиотека GMPXX на основе библиотеки GMP. Проект собирается c помощьью утилиты make, с генерацией файлов сборки через CMake. Для форматирования кода в проекте используются clang-tidy и clang-format. Требования версий стандарта C++ и утилиты CMake указаны в корневом конфигурационном файле CMakeLists.txt.

Из зависимостей необходимо установить gmp и gmpxx.

Структура проекта:

• /contrib -- содержит дополнительные субмодули библиотеки: GoogleTest и GoogleBenchmark.

• /src -- содержит саму реализованную библиотеку

• /tests -- содержит тесты корректности с использованием GoogleTest

• /benchmarks -- содержит тесты производительности и сравнение разных имплементаций с использованием GoogleBenchmark

Перечень реализованных алгоритмов:

Вероятностные алгоритмы определения простоты:

1. Тест Ферма
2. Тест Эйлера - Якоби
3. Тест Миллера - Рабина
4. Тест Бейли - Вагстаффа - Люка
5. Сильный тест Бейли - Вагстаффа - Люка
6. Тест V-последовательности Люка
7. Тест Бейли — Померанца — Селфриджа — Уогстаффа
8. Усиленный тест Бейли — Померанца — Селфриджа — Уогстаффа

Детерменированные алгоритмы определения простоты:

1. Тест перебором делителей
2. Тест Люка - Лемера

Алгоритмы факторизации:

1. Квадратичное решето

---

Автор проекта: Блинов Илья