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

Реализованные алгоритмы

Тесты простоты

1. Наивная проверка простоты за $\mathcal{O}(\sqrt{n})$
2. Тест простоты Ферма
3. Тест простоты Миллера-Рабина
4. Тест простоты Люка-Лемера ($2^p-1$)
5. Тест простоты Люка-Лемера-Ризеля ($k \cdot 2^n - 1,\ k<2^n$)
6. Тест Люка, сильный тест Люка, улучшенный сильный тест Люка
7. Тест простоты Бейли-Померанца-Селфриджа-Уогстаффа (BPSW), основанный на: тесте Ферма, тесте Миллера-Рабина
8. Тест простоты Прота ($k \cdot 2^n + 1,\ k<2^n$)

Генерация простых чисел

1. Поиск минимального простого не меньшего $k$ (перебор + тест простоты)
2. Генерация случайного простого на отрезке (перебор + тест простоты)
3. Генерация случайного простого методом Маурера (с сертификатом простоты)

Факторизация

1. Наивная факторизация за $\mathcal{O}(\sqrt{n})$
2. Факторизация Ферма
3. Ро-алгоритм Полларда
4. $p-1$ - алгоритм Полларда
5. Алгоритм Диксона

Другое

1. Вычисление символа Якоби $\left( \frac{a}{n} \right)$ за $\mathcal{O}(\log \min(a,n))$
2. Вычисление $n$-го члена последовательности Люка за $\mathcal{O}(\log n)$
3. Решето Эратосфена за $\mathcal{O}(n)$ (поиск минимального простого делителя для всех до $n$)

Сборка проекта

1. Склонируйте репозиторий:

git clone https://github.com/crazyilian/big-prime-numbers
cd big-prime-numbers

2. Создайте директорию для сборки

mkdir build
cd build

3. Сконфигурируйте и соберите проект

cmake ..
cmake --build .