Конспект: простота, решето и вероятностные тесты

Понятия

Простое число делится только на единицу и на себя. Составное имеет делитель поменьше. Единица - ни то, ни другое.

Свидетель - основание, которое доказывает, что число составное. Лжец - основание, при котором составное число ведёт себя как простое.

Число Кармайкла - составное, которое проходит тест Ферма по всем основаниям, взаимно простым с ним. Наименьшее - 561 = 3 · 11 · 17.

Третий корень из единицы - число x, не равное 1 и −1, с x² ≡ 1. По простому модулю таких нет.

Что унести

ЗАДАЧА                              ИНСТРУМЕНТ                 ЦЕНА
все простые до N                    решето Эратосфена          N · ln ln N,  память N
простое ли одно число n             Миллер-Рабин               k степеней по модулю
наименьший делитель p числа n       перебор                    p проб, до √n
                                    ро-метод Полларда          около √p кругов, до n^(1/4)

РЕШЕТО                                  N          простых    шагов решета    перебором для каждого
для p от 2, пока p² ≤ N:                10³           168          7 525             21 367
    если p не вычеркнуто:               10⁵         9 592        889 913          8 765 857
        вычеркнуть p², p² + p, …        10⁶        78 498      9 447 987
вычёркиваний до 10⁶: 2 122 048 - по 2,1 на число

Простых много. До N их около N / ln N; около N простое - одно из ln N чисел. Из тысячи нечётных после 10⁹ простых 99.

ТЕСТ ФЕРМА                              ТЕСТ МИЛЛЕРА-РАБИНА,  n − 1 = d · 2ˢ
x = aⁿ⁻¹ mod n                          x = aᵈ mod n
x ≠ 1  →  составное, доказано           x = 1 или x = n − 1  →  не свидетель
x = 1  →  вывода нет                    до s − 1 квадратов; встретилось n − 1  →  не свидетель
                                        иначе  →  составное, доказано

561, основание 2:   2³⁵ = 263 → 166 → 67 → 1        67² ≡ 1,  а 67 не равно 1 и 560
91, основание 3:    3⁹⁰ ≡ 1 (лжец Ферма),  но 3⁴⁵ ≡ 27 и 27² ≡ 1 - свидетель Миллера-Рабина

Почему два корня. x² ≡ 1 (mod p) значит p делит (x − 1)(x + 1); простое делит один из множителей. У составного модуля множители делят работу: 66 · 68 = 8 · 561.

Ошибка. Ферма, не Кармайкл: лжецов не больше половины. Миллер-Рабин, любое нечётное составное: не больше четверти, k случайных оснований - ошибка 1/4ᵏ. Простое составным не назовёт никогда.

ОСНОВАНИЯ, КОТОРЫЕ НЕ ОШИБАЮТСЯ НИ РАЗУ          ДО ЧИСЛА
2                                                2 047
2, 3                                             1 373 653
2, 3, 5                                          25 326 001
2, 3, 5, 7                                       3 215 031 751
первые 12 простых                                3 · 10²³  (все 64-битные)

РО-МЕТОД                                         n = 8633,  x → x² + 1
x - черепаха, шаг;  y - заяц, два шага           шаг        1   2    3    4     5     6
d = НОД(|x − y|, n)                              x          5  26  677  781  5652  3005
d = 1   → дальше                                 x mod 97   5  26   95    5    26    95
1 < d < n → делитель                             НОД(3005 − 677, 8633) = 97
d = n   → сменить c

Рекорды разложения: 829 бит в 2020 году, 862 и 896 бит в сентябре 2026-го. Ключ в 1024 бита ненадёжен, 2048 - нижняя граница.

Ловушки джокера

«Единица - значит простое». Тест отвечает «составное» или «не знаю». 3⁹⁰ mod 91 = 1.

Одно основание. По основанию 2 тест Ферма пропускает 78 составных до ста тысяч, Миллер-Рабин - 16.

Основания 1 и n − 1. Лгут для любого нечётного числа. Брать от 2 до n − 2.

Нет проверки x = n − 1 до цикла. Простое 13 с основанием 4 объявляется составным: 4³ ≡ −1.

s квадратов вместо s − 1. Лишний квадрат ничего не находит: aⁿ⁻¹ не бывает равно −1.

x * x % n. Квадрат выходит за точность. Считать pow(x, 2, n).

Набор 2, 3, 5, 7 для больших чисел. 3 215 031 751 = 151 · 751 · 28 351 проходит все четыре.

Фиксированные основания для чужих чисел. Число под известный набор строится заранее.

Вычёркивание от 2p. Верно, но лишняя работа. [True] * N - не хватает ячейки N.

Единица в решете. Без prost[1] = False она объявлена простой.

Ро-метод на простом числе. Не остановится, пока цикл не замкнётся по n. Сначала тест простоты.

d = n как ответ. Это отказ, а не делитель.

Близкие множители. p и q рядом - число раскладывается разностью квадратов за несколько проб.

Куда это ведёт

Всё, что нужно, чтобы построить шифр, оказалось лёгким: найти большое простое, перемножить два таких числа, возвести в степень по модулю, найти обратный элемент. Всё, что нужно, чтобы шифр взломать, - разложить произведение обратно - оказалось трудным. Следующая глава собирает из лёгких частей RSA и обмен ключами и показывает, где такая конструкция ломается не из-за математики, а из-за того, как ею пользуются.