Всем привет! Этот блог будет посвящен разным недетерминированным тестам простоты и, в частности, самому известному и самому используемому из них в олимпиадном программировании — тесту Миллера-Рабина. Немного поискав, я обнаружил, что материалов по этой теме на русском не то чтобы много, поэтому пришло время это исправлять! (Тем более лишний конспект лекции по ОКТЧ еще никому не мешал).
Обозначения
Сразу договоримся о них.
$$$\equiv_m$$$ означает сравнимость по модулю $$$m$$$.
$$$Z_m^*$$$ — группа остатков по модулю $$$m$$$, взаимно простых с $$$m$$$.
$$$\Big(\dfrac{a}{p}\Big)$$$ — символ Лежандра. С технической точки зрения, в рамках этого блога мы не будем использовать от него ничего, кроме свойства $$$\Big(\dfrac{a}{p}\Big) \equiv_p a^{\frac{p-1}{2}}$$$, поэтому можно принять это за определение.
$$$\Big(\dfrac{a}{m}\Big)$$$ — символ Якоби. Может чуть менее известный, чем символ Лежандра, однако, опять же, кроме его определения нам от него ничего и не потребуется. $$$\Big(\dfrac{a}{m}\Big)$$$ определен для нечетных m, и при $$$m=p_1^{\alpha _1}*\ldots*p_k^{\alpha _k}$$$ равен $$$\prod _{i=1} ^k \Big(\dfrac{a}{p_i}\Big)^{\alpha_i}$$$.
$$$ord_m(a)$$$ — порядок числа $$$a$$$ по модулю $$$m$$$, т.е. минимальная степень, в которую надо возвести $$$a$$$, чтобы получить 1. Имеет смысл только когда $$$a \in Z_m^*$$$.
$$$\nu_2(x)$$$ — максимальная степень двойки, на которую делится $$$x$$$. (__builtin_ctz(x) придумали в ..., люди до: $$$\,$$$)
Тест Ферма
В основе теста лежит Малая теорема Ферма:
разве что в слегка необычной записи. Опишем сам тест: пусть нам дано число m, которое мы хотим проверить на простоту, возьмем случайный элемент $a$ из $$$Z_m^*$$$ и проверим, что $$$a^{m-1} \equiv_m 1$$$. Если бы число $$$m$$$ было простым, то сравнение точно было бы верным. Поэтому если наш выбранный элемент $$$a$$$ опроверг это сравнение, то можно заключить, что $$$m$$$ составное.
Оценим, насколько этот тест эффективен. Обозначим $$$B_F = \{ a \in Z_m^* \mid a^{m-1} \equiv_m 1 \}$$$.
Утверждение 1: Если $$$B_F \ne Z_m^*$$$, то $$$|B_F| \leqslant \frac{1}{2} |Z_m^*|$$$.
Идею из доказательства этого факта мы увидим еще не раз. А именно, заметим, что на самом деле $$$B_F$$$ — это подгруппа группы $$$Z_m^*$$$. Действительно, для этого надо проверить 3 свойства: что $$$1 \in B_F$$$, что $$$a \in B_F \implies a^{-1} \in B_F$$$, и что $$$a, b \in B_F \implies ab \in B_F$$$.
Свойства эти проверяются методом пристального взгляда в определение $$$B_F$$$. Теперь наше утверждение следует из того, что размер подгруппы всегда делит размер группы.
Из утверждения 1 следует приятный факт: пусть $$$B_F \ne Z_m^*$$$, и $$$m$$$ соответственно составное, тогда вероятность определить это 1 тестом не менее $$$\frac{1}{2}$$$. Неплохо.
С другой стороны, если $$$B_F = Z_m^*$$$, то у нас нет ни малейшего шанса на успех, т.к. любая проверка не даст результата. Поэтому возникает предположение: $$$B_F = Z_m^* \iff m - \text{простое}$$$. В таком случае сделав $$$x$$$ независимых тестов мы можем быть уверены, что с шансом $$$1-2^{-x}$$$ наше число простое. Однако... это предположение неверно.
Определение: Составное число $$$m$$$ называется числом Кармайкла, если $$$B_F = Z_m^*$$$.
Утверждение 2: $$$m$$$ — число Кармайкла тогда и только тогда, когда $$$m$$$ составное, нечетное, свободно от квадратов и для любого делителя $$$m$$$ — $$$p_i$$$ выполнено: $$$m-1 \, \mathop{\vdots} \, p_i-1$$$.
Так-с, давайте сначала докажем, что для чисел Кармайкла выполняются все заявленные свойства.
Первым шагом доказательства этого утверждения будет выписывание определения. Пусть $$$m=p_1^{\alpha _1}*\ldots*p_k^{\alpha _k}$$$, тогда
Зафискриуем нечетный простой делитель $$$p_i$$$. Воспользуемся существованием первообразного корня по модулю $$$p_i ^{\alpha_i}$$$. Иными словами утверждается, что существует такое $$$a \in Z _{p_i ^{\alpha_i}} ^* $$$, что $$$ord _{p_i ^{\alpha_i}}(a) = \varphi(p_i ^{\alpha_i}) = (p_i-1)p_i ^{\alpha_i - 1}$$$. Используем это: 2 строчками (считая в дескотопной версии) выше написано, что $$$m-1$$$ делится на порядок любого элемента — ну значит и на $$$(p_i-1)p_i ^{\alpha_i - 1}$$$ тоже. Однако $$$m-1$$$ и $$$p_i ^{\alpha_i - 1}$$$ взаимнопросты, т.к. $$$p_i$$$ делит $$$m$$$, поэтому отсюда заключаем, что $$$\alpha_i = 1$$$ и $$$m-1 \, \mathop{\vdots} \, p_i - 1$$$.
Осталось разобраться с двойкой, т.е. доказать, что $$$m$$$ нечетно. Ну пусть $$$m = 2^s t$$$. Если $$$t \ne 1$$$, т.е. имеет какой-то простой делитель $$$p$$$, то по доказанному $$$m-1 \, \mathop{\vdots} \, p - 1 \, \mathop{\vdots} \, 2$$$, противоречие. Если же $$$m = 2^s$$$, то при $$$s > 1: -1 \notin B_F$$$, т.е. $$$m$$$ не число Кармайкла. При $$$s = 1$$$ у нас $$$m = 2$$$, но число Кармайкла должно быть составным.
Вот и все, мы доказали, что для чисел Кармайкла выполняются все заявленные свойства. В обратную сторону делается намного проще. Имеем $$$m-1 \, \mathop{\vdots} \, p_i - 1$$$ по условию и $$$p_i - 1 \, \mathop{\vdots} \, ord _{p_i}(a)$$$ по свойству порядка. Вот мы и получили, что хотели (см. 3 равносильных условия выше).
На этом доказательство утверждения 2 заверешено.
Ура! Теперь мы, например, можем написать программу, находящую все числа Кармайкла до $$$10^8$$$, просто используя только что доказанный критерий и решето Эратосфена.
Утверждение 3: У любого числа Кармайкла не менее трех различных простых делителей
Это несложное упражнение остается неленивому читателю. [Надо применить утв. 2].
Тест Соловея-Штрассена
К сожалению, этот тест имеет мало практического применения, т.к. как мы далее покажем, он строго хуже теста Миллера-Рабина). Однако это не повод его не изучить. Итак, этот тест представляет собой улучшение предыдущего теста Ферма и лишен того досадного недостатка, что некоторые составные числа никогда не будут таковыми определены. Опишем сам тест: как известно для простого нечетного $$$p$$$ и для любого ненулевого остатка $$$a$$$ имеет место равенство $$$a^{\frac{p-1}{2}} \equiv_p \Big(\dfrac{a}{p}\Big)$$$. Вот и давайте это перенесем на случай произвольного $$$m$$$: если $$$a^{\frac{m-1}{2}} \equiv_m \Big(\dfrac{a}{m}\Big)$$$ не выполнено, то $$$m$$$ составное. Обратите внимание, что здесь, как в общем-то и в тесте Миллера-Рабина, мы предполагаем, что $$$m$$$ нечетное. Также обратите внимание, что в первом сравнении речь о символе Лежандра, во втором — уже о его обобщении — символе Якоби.
Перед тем, как анализировать этот тест, давайте чуть-чуть поговорим о реализации. Во-первых, я немножко наврал, когда говорил, что от символа Якоби на не потребуется ничего, кроме его определения. Потому что из него совершенно непонятно, как его вычислять. А сделать это можно с помощью так называемого квадратичного закона взаимности, однако этот вопрос останется за рамками этого блога. Во-вторых, мы всегда говорим о том, что мы выбираем $$$a$$$ случайным остатком из $$$Z_m^*$$$, хотя это не является каким-то тривиальным действием. Поясним, что на самом деле под этим понимается: давайте выберем просто рандомное число $$$a$$$ в диапазоне $$$[1, m-1]$$$, и посчитаем $$$\gcd(a, m)$$$. Если он оказался равным 1, то это и значит, что $$$a \in Z_m^*$$$, а в противном случае мы нашли нетривиальный делитель $$$m$$$ ($$$1 \ne \gcd(a, m) \mid m$$$), поэтому можно сразу заключить, что $$$m$$$ составное. Кроме этого есть еще такой трюк: на самом деле $$$a$$$ можно выбирать в диапазоне $$$[2, m-2]$$$, поскольку можно показать, что остатки $$$\pm 1$$$ проходят как тест Соловея-Штрассена, так и тест Миллера-Рабина для любого $$$m$$$. Т.е. нет смысла делать на них проверку. Доказательство этого для 1 вроде плюс-минус очевидно, как и для -1 в тесте Миллера-Рабина, а вот для -1 в тесте Соловея-Штрассена с ходу, конечно, может быть не совсем понятно, однако тоже верно.
Теперь давайте наконец проанализируем этот тест. Обозначим $$$B_{SS} = \{ a \in Z_m^* \mid a^{\frac{m-1}{2}} \equiv_m \Big(\dfrac{a}{m}\Big) \}$$$. Во-первых, верно утверждение, аналогичное утверждению 1. А именно если $$$B_{SS} \ne Z_m^*$$$, то $$$|B_{SS}| \leqslant \frac{1}{2}|Z_m^*|$$$. И доказывается ровно так же! Ведь $$$B_{SS}$$$ — подгруппа $$$Z_m^*$$$. Проверяется тем же ультраметодом, что и тогда, разве что сейчас потребуется знание мультипликативности символа Якоби. Во-вторых, $$$B_{SS} \subset B_F$$$. Это тоже очевидно, ведь $$$\Big(\dfrac{a}{m}\Big) = \pm 1$$$, поэтому любое число из $$$B_{SS}$$$ при возведении в квадрат даст единицу. Ну и наконец последнее свойство, ради которого мы все тут и собрались.
Утверждение 4: $$$B_{SS} = Z_m^* \iff m - $$$ простое.
Если это утверждение верно, то теперь мы наконец можем проверять числа на простоту! Поскольку сделав $$$x$$$ проверок, мы можем быть абсолютно уверены, что с вероятностью $$$1-2^{-x}$$$ число простое). Перейдем к доказательству утверждения. Справа налево — очевидно. Слева направо — давайте разбираться.
Ну пусть $$$m$$$ составное, и $$$B_{SS} = Z_m^*$$$. Тогда $$$m$$$ — число Кармайкла, иначе $$$B_{SS} \subset B_F \subsetneq Z_m^*$$$. Благо, про эти самые числа мы уже много что знаем, и наконец-то можем пустить в ход факты. Например, мы можем сказать, что $$$m = p_1 p_2 \ldots p_k$$$, где $$$k \geqslant 3$$$, и все $$$p_i$$$ различны. Основная идея заключается в том, что мы просто построим $$$a \in Z_m^*$$$ такой, что $$$a \notin B_{SS}$$$. А построим мы его при помощи Китайской теоремы об остатках:
Где $$$b$$$ таков, что $$$\Big(\dfrac{b}{p_1}\Big) = -1$$$. Вот и все, не так уж и сложно получилось... Давайте же проверим. $$$\Big(\dfrac{a}{m}\Big) = \prod _{i=1} ^k \Big(\dfrac{a}{p_i}\Big) = \Big(\dfrac{b}{p_1}\Big) \prod _{i=2} ^k \Big(\dfrac{1}{p_i}\Big) = (-1)*1*\ldots*1 = -1$$$. Однако если $$$a^{\frac{m-1}{2}} \equiv_m -1$$$, то, сужая на модуль $$$p_2$$$, получаем, что $$$a^{\frac{m-1}{2}} \equiv 1^{\frac{m-1}{2}} \equiv 1 \equiv -1 \mod p_2$$$, противоречие.
Тест Миллера-Рабина
Итак, мы наконец-то пришли к нему. Опишем идею теста: пусть есть нечетное простое $$$p$$$ и ненулевой остаток $$$a$$$. По Малой теореме Ферма: $$$a^{p-1} \equiv_p 1$$$. Давайте последовательно извлекать из этого уравнения квадратный корень. Т.е. мы имеем либо $$$a^{\frac{p-1}{2}} \equiv_p -1$$$, либо $$$a^{\frac{p-1}{2}} \equiv_p 1$$$. Во-втором случае не будем останавливаться на достигнутом и извлечем корень еще раз, т.е. либо $$$a^{\frac{p-1}{4}} \equiv_p -1$$$, либо $$$a^{\frac{p-1}{4}} \equiv_p 1$$$ и т.д. до тех пор, пока мы можем делить $$$p-1$$$ пополам. И в конченом счете у нас будет либо что $$$a^t \equiv_p -1$$$, либо $$$a^t \equiv_p 1$$$, где $$$t$$$ нечетное, соответственно корень извлечь будет уже нельзя. Теперь опишем сам тест: мы будем считать, что $$$m$$$ нечетно, и пусть $$$m-1 = 2^s t$$$. Тогда мы хотим выполнение любого из следующих условий: либо $$$a^{\frac{m-1}{2}} \equiv_m -1$$$, либо $$$a^{\frac{m-1}{4}} \equiv_m -1$$$, $$$\ldots$$$, либо $$$a^{t} \equiv_m -1$$$, либо $$$a^{t} \equiv_m 1$$$. Если ни одно из этих условий не выполнено, то $$$m$$$ составное. По-другому на это можно смотреть вот так: пусть $$$p$$$ простое. Тогда $$$a^{p-1} - 1 = (a^{\frac{p-1}{2}}+1)(a^{\frac{p-1}{4}}+1) \ldots (a^t+1)(a^t-1) \equiv_p 0$$$, поэтому хотя бы 1 скобка должна равняться нулю. Ровно это мы и проверяем.
Реализовать такую проверку можно следующим образом: быстрым возведением в степень найдем $$$x = (a^t \mod m)$$$. Если $$$x = 1$$$, то все ок. Если $$$x = -1$$$, то тоже ок. Иначе мы должны проверить сравнимо ли хоть одно из чисел $$$a^{2t}, a^{4t}, \ldots, a^{\frac{m-1}{2}}$$$ с $$$-1$$$. Однако все эти числа могут быть получены итеративным возведением числа $$$x$$$ в квадрат. Поэтому 1 проверка работает за $$$O(log \, t)$$$ на возведение в степень и $$$O(s)$$$ на проверку всех остатков, последовательно возводя $$$x$$$ в квадрат — итого $$$O(log \, m)$$$ на 1 проверку.
Пара небольших вопросов, прежде чем идти дальше: 1) Правда ли, что в реализации мы гарантируем, что $$$a \in Z_m^*$$$? 2) Проверьте корректность этой реализации для чисел 7 и 9 (тем более что число 9 находится в некотором особом положении, как мы увидим далее).
Итак, начнем анализ. Обозначим $$$M_0 = \{a \in Z_m^* \mid a^t \equiv_p 1 \}$$$, $$$M_j ' = \{a \in Z_m^* \mid a^{2^j t} \equiv_p -1 \}$$$ для $$$0 \leqslant j < s$$$. $$$B_{MR} = M_0 \bigsqcup M_0 ' \bigsqcup M_1 ' \ldots \bigsqcup M_{s-1} '$$$ — множество остатков, проходящие тест Миллера-Рабина. На повестке дня лишь 2 утверждения:
Утверждение 5: $$$B_{MR} \subset B_{SS}$$$.
Утверждение 6: Если $$$m$$$ составное, то $$$|B_{MR}| \leqslant \frac{1}{4}|Z_m^*|$$$ при $$$m > 9$$$.
Для начала поймем, что это означает. Из утв 5. следует, что тест Миллера-Рабина работает не хуже теста Соловея-Штрассена, который уже нам давал вероятность не ниже $$$1 - 2^{-x}$$$ на $$$x$$$ проверок. Однако утв. 6 очень сильно ее улучшает! А именно, теперь вероятность не ниже $$$1 - 4^{-x}$$$. Довольно значительно. Перейдем к доказательству.
Доказательство утверждения 5: К сожалению, у нас будет 3 случая. Почему так? Ну, потому что $$$B_{MR}$$$ состоит из концептуально 2 разных типов множеств — $$$M_0$$$ и $$$M_j '$$$, а также $$$\Big(\dfrac{a}{m}\Big)$$$, фигурирующий в определении $$$B_{SS}$$$, может быть как 1, так и -1. Везде далее $$$m=p_1^{\alpha _1}*\ldots*p_k^{\alpha _k} = 2^s t + 1$$$.
- 1 случай. $$$a \in M_{s-1} '$$$, т.е. $$$a^{\frac{m-1}{2}} \equiv_m -1$$$, и мы хотим доказать, что $$$\Big(\dfrac{a}{m}\Big) \equiv a^{\frac{m-1}{2}} \equiv_m -1$$$.
Лемма.
Давайте быстренько приведем доказательство, тем более это несложно, а идею из него мы еще увидим.
Теперь будем активно пользоваться этой леммой. Для начала вычленим информацию из условия:
Значит по лемме $$$s = \nu_2(m-1) = \nu_2(ord _{p_i}(a)) \leqslant \nu_2(p_i-1)$$$. Тогда запишем, что $$$p_i - 1 = 2^s t_i$$$. Символ Лежандра равен -1, если $$$t_i$$$ — нечетно (по лемме). Т.к. мы хотим доказать, что символ Якоби равен -1, то для этого достаточно показать, что в $$$m$$$ входит нечетное число таких $$$p_i$$$ (с учетом кратности), что $$$t_i$$$ нечетны. Ну действительно, посмотрим на уравнение $$$m=p_1^{\alpha _1}*\ldots*p_k^{\alpha _k}$$$ по модулю $$$2^{s+1}$$$. Все те $$$p_i$$$, для которых $$$t_i$$$ четно, сравнимы с 1 по этому модулю. А все те $$$p_i$$$, для которых $$$t_i$$$ нечетно, и еще $$$m$$$ сравнимы с $$$2^s + 1$$$. Т.е. получаем, что $$$m \equiv 2^s+1 \equiv \prod p_i \equiv (2^s+1)^L$$$, где $$$L$$$ — количество $$$p_i$$$ с нечетным $$$t_i$$$, короче говоря то, что мы и ищем. Ну отсюда легко заключить, что $$$L$$$ нечетно, поскольку $$$(2^s+1)^2 \equiv 1 \mod 2^{s+1}$$$, ровно то, что мы и хотели.
- 2 случай. $$$a \in M_{j} '$$$ для $$$j \ne s-1$$$, т.е. $$$a^{\frac{m-1}{2^k}} \equiv_m -1$$$ для $$$k > 1$$$, и мы хотим доказать, что $$$\Big(\dfrac{a}{m}\Big) \equiv a^{\frac{m-1}{2}} \equiv (a^{\frac{m-1}{2^k}})^{2^{k-1}} \equiv (-1)^{2^{k-1}} \equiv 1 \mod m$$$.
Таким же образом распишем:
Значит $$$s-(k-1) = \nu_2(\frac{m-1}{2^{k-1}}) = \nu_2(ord _{p_i}(a)) \leqslant \nu_2(p_i-1)$$$. Запишем $$$p_i - 1 = 2^{s-(k-1)} t_i$$$, и тогда символ Лежанждра будет равен -1, если $$$t_i$$$ нечетно (по лемме). Т.е. мы опять хотим оценить $$$L$$$ — количество $$$p_i$$$ с нечетным $$$t_i$$$, но на этот раз, т.к. символ Якоби должен быть 1, наша цель доказать, что $$$L$$$ четно. Для этого рассмотрим уравнение $$$m=p_1^{\alpha _1}*\ldots*p_k^{\alpha _k}$$$ по модулю $$$2^{s-(k-1)+1}$$$. Все те $$$p_i$$$, для которых $$$t_i$$$ четно, и еще $$$m$$$ сравнимы с 1 по этому модулю. А все те $$$p_i$$$, для которых $$$t_i$$$ нечетно, сравнимы с $$$2^{s-(k-1)} + 1$$$. Получаем $$$1 \equiv (2^{s-(k-1)} + 1)^L \mod 2^{s-(k-1)+1}$$$. Т.к. $$$(2^{s-(k-1)} + 1)^2 \equiv 1 \mod 2^{s-(k-1)+1}$$$, то $$$L$$$ четно, ч.т.д.
- 3 случай. $$$a \in M_0$$$, т.е. $$$a^t \equiv_m 1$$$, и мы хотим доказать, что $$$\Big(\dfrac{a}{m}\Big) \equiv a^{\frac{m-1}{2}} \equiv (a^t)^{2^s} \equiv 1^{2^s} \equiv 1 \mod m$$$.
Так, ну тут все совсем просто: $$$a^t \equiv_m 1 \implies t \, \mathop{\vdots} \, ord _{p_i}(a) \implies \nu_2(ord _{p_i}(a)) = 0$$$, т.к. $$$t$$$ нечетно. Значит $$$\Big(\dfrac{a}{p_i}\Big) = 1$$$ для вообще всех $$$p_i$$$ (по лемме). Ну тогда и $$$\Big(\dfrac{a}{m}\Big) = 1$$$, ч.т.д.
На этом доказательство утверждения 5 заверешено.
Доказательство утверждения 6: Напомним, что $$$m=p_1^{\alpha _1}*\ldots*p_k^{\alpha _k} = 2^s t + 1$$$. Давайте разберем 3 случая — если $$$k = 1$$$, если $$$k = 2$$$ и если $$$k \geqslant 3$$$.
- 1 случай. $$$k = 1$$$, т.е. $$$m = p^{\alpha}$$$. Этот случай стоит особняком от двух других, так что давайте разберем его первым.
Напомним, что $$$B_{MR} \subset B_{SS} \subset B_F$$$. Давайте оценим $$$|B_F|$$$. Имеем $$$a \in B_F \iff a^{p^{\alpha}-1} \equiv 1 \mod p^{\alpha}$$$. Т.е. $$$p^{\alpha}-1 \, \mathop{\vdots} \, ord _{p^{\alpha}} (a)$$$. Но также и $$$\varphi(p^{\alpha}) = (p-1) p^{\alpha-1} \, \mathop{\vdots} \, ord _{p^{\alpha}} (a)$$$. Значит и $$$\gcd (p^{\alpha}-1, (p-1) p^{\alpha-1}) = p-1 \, \mathop{\vdots} \, ord _{p^{\alpha}} (a) \implies a^{p-1} \equiv 1 \mod p^{\alpha}$$$.
Вот тут ключевой момент: $$$a^{p-1} \equiv 1 \mod p ^{\alpha} \iff (p-1)b \equiv 0 \mod \varphi(p ^{\alpha}) = (p-1)p ^{\alpha - 1}$$$, где $$$a \equiv_m g^b$$$, поскольку группа $$$Z _{p^{\alpha}} ^*$$$ является циклической, или, что то же самое, поскольку по модулю $$$p^{\alpha}$$$ существует первообразный корень.
Ну и все. Т.к. получившееся уравнение имеет ровно $$$p-1$$$ решение, то $$$|B_F| = p-1$$$. Ну вот и все, $$$| B _{MR}| \leqslant |B_F| = p-1 \leqslant \frac{1}{4} |Z_m^*| = \frac{1}{4} (p-1) p ^{\alpha - 1}$$$. Второе неравенство верно при больших $$$m$$$, а именно при $$$m > 9$$$.
- 2 случай. $$$k \geqslant 3$$$, т.е. $$$m$$$ можно представить в виде $$$m = xyz$$$ произведения трех попарно взаимнопростых сомножителей.
Определим множества $$$M_j = \{ a \in Z_m^* \mid a^{2^j t} \equiv_m 1 \}$$$ для $$$0 \leqslant j \leqslant s$$$. Заметьте, что $$$M_0$$$ и так уже было определено.
Для начала давайте визуализируем наши множества $$$M_0, M_0 ', \ldots, M_{s-1} '$$$.
Основная идея состоит в следующем: рассмотрим множество $$$M_{j+1}$$$, где $$$0 \leqslant j < s$$$. Его элементы, возведенные в $$$2^{j+1} t$$$ степень, дают остатки 1 по модулю $$$m$$$, т.е. дают остаток 1 по модулям $$$x$$$, $$$y$$$, $$$z$$$ одновременно. Посмотрим, из чего состоит это множество. Ну, во-первых, $$$M_j \subset M_{j+1}$$$ — это те элементы, которые в степени $$$2^j t$$$ дают остаток 1 по модулю $$$m$$$, или то же самое дают остаток 1 по модулям $$$x$$$, $$$y$$$, $$$z$$$. Во-вторых, $$$M_j ' \subset M_{j+1}$$$, поскольку это элементы, чьи $$$2^j t$$$ степени дают остаток $$$-1$$$ по модулю $$$m$$$, или то же самое дают остаток $$$-1$$$ по модулям $$$x, y, z$$$. Так вот давайте рассмотрим множество $$$N_j \subset M_{j+1} \setminus (M_j \bigsqcup M_j ')$$$ — это такие числа, которые в степени $$$2^j t$$$ дают остатки $$$\pm 1$$$ по модулям $$$x$$$, $$$y$$$, $$$z$$$, но не одинаковые. Для лучшего понимания см. картинку.
Иными словами $$$N_j = \{ a \in M_{j+1} \setminus (M_j \bigsqcup M_j ' ) \mid a^{2^j t} \equiv_x \pm 1 \; and \; a^{2^j t} \equiv_y \pm 1 \; and \; a^{2^j t} \equiv_z \pm 1 \}$$$.
Теперь, легко видеть, что $$$N_j \cap B_{MR} = \varnothing$$$ и что все $$$N_j$$$ не пересекаются (внимательно убедитесь в этом; картинки должны вам помочь). Поэтому давайте оценим размеры $$$N_j$$$ — если они окажутся достаточно большими, то $$$B_{MR}$$$ будет достаточно маленьким. В этом нам поможет следующая лемма:
Лемма: Здесь $$$m$$$ необязательно совпадает с $$$m$$$ из задачи. Пусть $$$A = \{ a \in Z_m^* \mid a^T = 1 \}$$$, $$$B = \{ a \in Z_m^* \mid a^T = a_0 \}$$$. Тогда если $$$B \ne \varnothing$$$, то $$$|A| = |B|$$$.
Ну действительно, если $$$b_0 \in B$$$, то $$$B = b_0A$$$, т.е. между $$$B$$$ и $$$A$$$ существует биекция — просто домножение на $$$b_0$$$.
Давайте эту лемму применим. Например вот так: если $$$M_j ' \ne \varnothing$$$, то $$$|M_j '| = |M_j|$$$. Или например вот так: если $$$M_j ' \ne \varnothing$$$, то $$$|N_j| = 6|M_j '|$$$. Действительно, у нас есть 6 комбинаций $$$\pm 1$$$ по модулям $$$x$$$, $$$y$$$, $$$z$$$, каждая из них задает какой-то остаток по модулю $$$m$$$. Чтобы доказать утверждение, надо понять почему каждая из них непуста. Ну потому что по каждому из модулей $$$x$$$, $$$y$$$, $$$z$$$ есть остаток, который принимает как 1, так и -1 (потому что $$$M_j '$$$ не пусто), поэтому комбинируя их Китайской теоремой об остатках, получим требуемое.
Тогда визуализируем себе что происходит таким образом: изначально у нас есть только элементы множества $$$M_0$$$ — все они принадлежат $$$B_{MR}$$$. Затем мы начинаем докидывать элементы в $$$B_{MR}$$$, начиная с $$$M_0 '$$$ и заканчивая $$$M_{s-1} '$$$. Однако каждый раз, когда $$$M_j '$$$ непусто, мы находим $$$|N_j| = 6|M_j '|$$$ элементов, которые $$$B _{MR}$$$ не принадлежат. Тогда хочется сказать, что вообще-то мы нашли в 6 раз больше элементов не из $$$B _{MR}$$$, чем находится в самом $$$B _{MR}$$$, поэтому $$$|B _{MR}| \leqslant \frac{1}{7} |Z _m ^*| $$$. Нюанс тут в том, что мы забыли учесть элементы из $$$M _0$$$. Давайте же поправим это. Заметим, что $$$-1 \in M _0 '$$$, поэтому $$$M_0 '$$$ непусто, поэтому $$$|M _0'| = |M _0| = |N _0|/6$$$, т.е. изначально у нас 2 части элементов из $$$B _{MR}$$$ и 6 частей элементов не из $$$B _{MR}$$$. Ну вот и все, это доказывает искомую оценку на $$$|B _{MR}| \leqslant \frac{1}{4} |Z _m ^*|$$$.
На этом доказательство этого случая завершено, однако давайте отметим следующее: если бы у $$$m$$$ было хотя бы 4 различный простых делителя, т.е. $$$m$$$ представлялось бы в виде произведения 4 попарно взаимнопростых сомножителей, то на самом деле мы могли построить $$$N_j$$$ намного большего размера. А именно мы бы брали 16 комбинаций $$$\pm 1$$$, две из них отвечают множествам $$$M_j$$$ и $$$M_j '$$$, остальные 14 отвечают $$$N_j$$$. Поэтому мы получаем оценку $$$|B _{MR}| \leqslant \frac{1}{8} |Z _m ^*|$$$. Если $$$m$$$ имеет хотя бы 5 различных простых множителей, то $$$|B _{MR}| \leqslant \frac{1}{16} |Z _m ^*|$$$, и т.д.
- 3 случай $$$k = 2$$$.
Остался последний случай. Если мы провернем предыдущее доказательство, то получим лишь оценку на $$$|B _{MR}| \leqslant \frac{1}{2} |Z _m ^*|$$$, это не то, что нам надо. Однако давайте заметим моментик: на самом деле мы доказали чуть более сильный факт. На секундочку возвращаясь в случай $$$k \geqslant 3$$$, мы не просто показали, что $$$|B _{MR}| \leqslant \frac{1}{4} |Z _m ^*|$$$, а $$$|B _{MR}| \leqslant \frac{1}{4} |B_F|$$$! Почему так? Ну, потому что на самом деле все рассматриваемые нами множества — $$$M_j, M_j ', N_j, B _{MR}$$$ — все они являются помножествами $$$B_F$$$. Действительно, взгляните на все определения этих множеств и убедитесь, что если его элементы возвести в $$$m-1 = 2^s t$$$ степень, то они дадут $$$1$$$ по модулю $$$m$$$. Ну и раз так, то остался последний шаг — если $$$k = 2$$$, то $$$|B_F| \leqslant \frac{1}{2} |Z_m^*|$$$, т.к. $$$m$$$ не является числом Кармайкла. Поэтому $$$|B _{MR}| \leqslant \frac{1}{2} |B_F| \leqslant \frac{1}{4} |Z_m^*|$$$, ч.т.д.
На этом доказательство утверждения 6 заверешено.
Убираем недетерминированность
Если вас тревожит использование вероятностного алгоритма, потому что в самый ответственный момент раунда он вдруг упадет, или балансировка между временем работы и вероятностью правильности ответа треплет вам нервы, не переживайте, поскольку выход есть! Если вы смотрели реализацию теста Миллера-Рабина выше (самое время ее посмотреть), то, наверное, уже знаете, о чем речь. В реальных задачах числа, проверяемые вами на простоту, обычно ограничены $$$10^9$$$ или на крайний случай $$$10^{18}$$$. Так вот для этих диапазонов есть фиксированные наборы значений, на которых надо сделать проверки, чтобы по ним гарантированно определить простое ли ваше число. Т.е. вместо того чтобы $$$10/20/30$$$ раз выбирать $$$a$$$ рандомным, можно проитерировать $$$a$$$ по заранее заготовленному списку.
Если ваши числа до $$$1.1*10^{11}$$$, можете использовать
{2, 3, 5, 7}(за одним исключением в виде3'215'031'751).Если ваши числа до $$$3.8*10^{18}$$$, можете использовать
{2, 3, 5, 7, 11, 13, 17, 19, 23}.Если ваши числа до $$$4.7*10^9$$$, можете использовать
{2, 7, 61}.Если ваши числа до $$$10^{18}$$$ (точной константы не знаю), можете использовать
{2, 325, 9375, 28178, 450775, 7795265022}.
Первые два-три варианта запомнить легко, однако если вы можете скопировать или переписать эти магические числа, то можно использовать все. Эти и еще кучу других магических констант можно найти на этом сайте: https://miller-rabin.appspot.com/.
Ну вот и все, надеюсь, получилось неплохо.
Comments (0)
