!!§!! Вспомогательная страница к разделу
☞
((:crypto#алгоритм_rsa КРИПТОГРАФИЯ)). Предполагается знакомство с базовыми понятиями ((:probability ТЕОРИИ ВЕРОЯТНОСТЕЙ)).[[Считайте, что Вы их знаете, если сходу можете решить следующую задачу.]]
----
!!?!! Пусть $ N \in \mathbb N $. Определить вероятность того, что число случайным образом выбранное из множества $ \{1,2,\dots,N\} $ будет ((:numtheory#взаимно_простые_числа взаимно просто)) с $ N_{} $.
==Вероятностно простые числа==
~~TOC~~
Как найти достаточно большие простые числа?
Действительно, стойкость ((:crypto#алгоритм_rsa алгоритма RSA)) основана на возможности выбора простых чисел, состоящих из
не менее 100 десятичных знаков. Поиск таких чисел последовательным перебором всех нечетных,
начиная с некоторого стартового, и последующим "просеиванием" через решето
Эратосфена весьма затруднителен. Проблему решают обходным маневром и решают "приближенно", а точнее --- "вероятностно". Возможного кандидата на простое
число подвергают испытанию серией однотипных и легко осуществимых тестов.
Положительность результата хотя бы одного теста однозначно свидетельствует о
том, что кандидат является числом __составным__; с другой стороны,
отрицательный результат теста не дает абсолютной гарантии простоты кандидата,
но свидетельствует о том, что вероятность его быть составным уменьшилась
на определенную величину, скажем, в два раза. Тогда с увеличением количества
отрицательных результатов все меньше шансов у испытуемого числа оказаться
составным. Организовав серию испытаний из большого количества ---
например, 100 --- тестов и получив все их результаты отрицательными, мы
имеем право сказать, что кандидат является __скорее всего__
("вроде бы") __простым__, с вероятностью не менее
$$ 1-0.5^{100} \approx 99.\underbrace{99\dots99}_{28} \% \ . $$
Для таких чисел используют название **вероятностно простые числа**.
Мы изложим здесь два способа организации упомянутой серии тестов, при этом тестируемое число
будем обозначать $ \tilde{p} $.
===Вероятностный алгоритм, основанный на теореме Ферма==
((:modular#теорема_ферма Теорема Ферма)) утверждает, что для простого числа
$ \widetilde{p} $ сравнение
$$x^{\widetilde{p}-1} \equiv 1 \pmod{\widetilde{p}} $$
будет выполняться для всех чисел $ x\in\{ 1,\dots,\widetilde{p}-1 \} $.
Если же число $ \widetilde{p} $ составное, то, как правило, будет существовать достаточно большое
количество $ x_{} $, для которых то же сравнение места не имеет.
Число $ \widetilde{p} $ называется **псевдопростым по основанию** $ B $, если $ B^{\widetilde{p}-1} \equiv 1 \pmod{\widetilde{p}} $.
!!П!! **Пример.** Составные числа $ \widetilde{p} $ из множества $ \{2,\dots,10000\} $, имеющие максимальные отношения $ N/ \widetilde{p}>0.2 $, где $ N $ --- количество чисел множества $ \{ 1,\dots,\widetilde{p}-1 \} $, для которых выполняется $ x^{\widetilde{p}-1} \equiv 1 \pmod{\widetilde{p}} $.
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
\widetilde{p} & 4 & 9 & 15 & 65 & 91 & 133 & 341 & 451 & 481 & \mathbf{561} & 703 & \mathbf{1105} & 1387 & 1541 & \mathbf{1729}\\
\hline
N & 1 & 2 & 4 & 16 & 36 & 36 & 100 & 100 & 144 & 320 & 324 & 768 & 324 & 484 & 1891 \\
\hline
N/ \tilde{p} & 0.25 & 0.222 & 0.266 & 0.246 & 0.395 & 0.270 & 0.293 & 0.221 & 0.299 & \mathbf{0.570} & 0.460 &
\mathbf{0.695} & 0.233 & 0.314 & \mathbf{0.749} \\
\end{array}
$$
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
\widetilde{p} & 1891 & 2047 & \mathbf{2465} & 2701 & \mathbf{2821} & 3277 & 4033 & 4371 & 5461 & 6533 & \mathbf{6601} & 7107 & 8321 & \mathbf{8911} \\
\hline
N & 900 & 484 & 1792 & 1296 & 2160 & 784 & 1296 & 920 & 1764 & 2116 & 5280 & 1496 & 2704 & 7128 \\
\hline
N/ \widetilde{p} & 0.475 & 0.236 & \mathbf{0.727} & 0.480 & \mathbf{0.766} & 0.239 & 0.321 & 0.210 & 0.323 & 0.324 & \mathbf{0.800} & 0.21 & 0.325 & \mathbf{0.800} \\
\end{array}
$$
Видим, что для всех чисел, за исключением семи, выделенных **шрифтом**, указанное отношение меньше $ 0.5 $.
Оказывается, что замеченная в примере закономерность, является проявлением общего правила.
Рассмотрим все числа множества $ \{1,\dots, \widetilde{p}-1\} $, взаимно простые
с $ \widetilde{p} $, их ((:numtheory#функция_эйлера количество равно)) $ \phi (\widetilde{p}) $. Эти числа можно рассортировать по двум непересекающимся подмножествам:
$$
\begin{array}{ccl}
\mathbb V_1 &=& \left\{x\ \Big| \, x^{\widetilde{p}-1} \equiv 1 \pmod{\widetilde{p}} \ ,
\ \operatorname{HOD} (x,\widetilde{p})=1 \right\} \ , \\
\mathbb V_2 &=& \left\{y\ \Big| \, y^{\widetilde{p}-1}
\not \equiv 1 \pmod{\widetilde{p}} \ , \ \operatorname{HOD} (y,\widetilde{p})=1 \right\} \ .
\end{array}
$$
!!Т!! **Теорема 1.** //Если множество// $ \mathbb V_2 $ //не пусто, то число его элементов не меньше числа элементов// $ \mathbb V_1 $.
**Доказательство.** Если $ \mathbb V_1=\{x_1,\dots,x_{\ell} \} $ и
$ 1\le x_1 < \dots < x_{\ell}\le \widetilde{p}-1 $,
а $ y_{*}\in \mathbb V_2 $, то числа
$$y_1=x_1 y_{*} \pmod{\widetilde{p}} ,\dots,\ y_{\ell}=x_{\ell}y_{*} \pmod{\widetilde{p}} $$
будут все различными и принадлежать множеству $ \mathbb V_2 $. Действительно,
если $ y_j=y_k $ при $ k>j $, то $ x_j y_{*} \equiv x_k y_{*} \pmod{\widetilde{p}} $,
т.е. число $ (x_k-x_j)y_{*} $ делится на $ \widetilde{p} $. Но это невозможно, поскольку
по условию на множество $ \mathbb V_2 $ имеем $ \operatorname{HOD} (y_{*},\widetilde{p})=1 $,
а $ x_k-x_j<\widetilde{p} $ (см. теорему 3
☞
((:numtheory#взаимно_простые_числа ЗДЕСЬ)) ).
Далее,
$$y_j^{\widetilde{p}-1} \equiv_{_{\widetilde{p}}} \left(x_j y_{*} \right)^{\widetilde{p}-1}
=x_j^{\widetilde{p}-1}y_{*}^{\widetilde{p}-1} \equiv_{_{\widetilde{p}}} y_{*}^{\widetilde{p}-1}
\not \equiv_{_{\tilde{p}}} 1 $$
и $ \operatorname{HOD} (y_j,\widetilde{p})= \operatorname{HOD} \left(x_j y_{*}, \widetilde{p} \right) = 1 $
по свойствам $ x_{j} $ и $ y_{*} $ (и теореме 2, приведенной
☞
((:numtheory#взаимно_простые_числа ЗДЕСЬ))). Таким образом, действительно имеем: $ y_j \in \mathbb V_2 $.
Итак, множество $ \mathbb V_2 $ содержит, по меньшей мере, столько же элементов,
сколько $ \mathbb V_1 $.
♦
Множество $ \mathbb V_2 $ заведомо пусто, если число $ \widetilde{p} $ простое.
Однако существуют и составные числа $ A_{} $, для которых множество $ \mathbb V_2 $ пусто. Именно они давали "выбросы" для отношений $ N/\widetilde{p} $ в таблице примера из начала пункта.
Составное число $ A_{} $ называется **числом Кармайкла**[[Кармайкл Роберт (Carmichael Robert, 1879-1967) --- американский математик. Биография
☞
((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Carmichael.html ЗДЕСЬ)).]], если условие $ x^{A-1} \equiv 1 \pmod{A} $ выполняется для всех чисел $ x_{} $, взаимно простых с $ A_{} $.
!!Т!! **Теорема 2.** //Нечетное число// $ A_{} $ //является числом Кармайкла тогда
и только тогда, когда для любого его простого множителя// $ p_{} $ //число// $ A-1 $// делится
на// $ p-1 $,// а само число// $ A_{} $ //не делится на// $ p^2 $.
!!=>!! Число Кармайкла должно быть произведением не менее трех различных простых чисел.
**Доказательство.** Действительно, при $ p_2>p_1 $ число $ p_1p_2-1 $ не может
делиться нацело на $ p_2-1 $.
♦
Числа Кармайкла крайне редки, среди первых $ 100\,000 $ чисел их всего $ 16 $:
$$
561,\ 1105,\ 1729,\ 2465,\ 2821,\ 6601,\ 8911,\ 10585,\ 15841,\
29341,\ 41041,\ 46657,\ 52633,\ 62745,\ 63973,\ 75361 \ .
$$
Тем не менее, в 1994 г. была доказана бесконечность их множества.
!!П!! **Пример.** Проверить, что число $ 75361 $ является числом Кармайкла.
**Решение.** Имеем: $ 75361=11 \cdot 13 \cdot 17 \cdot 31 $. Разность
$ 75361-1=2^5\cdot 3 \cdot 5 \cdot 157 $ делится на любое из чисел
$ 10,\, 12,\, 16,\, 30 $.
♦
!!?!! Проверить, что числа $ 294409 $ и $ 56052361 $ являются числами Кармайкла.
----
Первый вероятностный алгоритм
проверки числа
$ \tilde{p} $
на простоту
Последовательно выбираем различные
целые $ B_1,\dots,B_K $ из множества $ \{1, \dots, \tilde{p}-1 \} $ и проверяем[[Можно предварительно проверять выполнение условия $ \operatorname{HOD} (B_j,\widetilde{p})>1 $, но можно и не делать этого.]]:
$$ B_j^{\widetilde{p}-1} \not \equiv 1 \pmod{\widetilde{p}} \ . $$
Если хотя бы одно из этих условий выполняется, то число $ \widetilde{p} $ --- составное.
Если ни одно из условий не выполняется ни при одном $ j\in\{1,\dots,K\} $, то либо
* число $ \widetilde{p} $ является числом Кармайкла, но вероятность этого события пренебрежимо мала;
* число $ \widetilde{p} $ --- составное, но не число Кармайкла; вероятность этого события $ \le 1/2^K $;
* число $ \widetilde{p} $ --- простое; вероятность этого события $ \ge 1-1/2^K $.
----
Действительно, если число $ \widetilde{p} $ --- составное, не являющееся числом Кармайкла,
то, по теореме $ 1 $, множество $ \mathbb V_2 $ содержит не меньше элементов,
чем $ \mathbb V_1 $. Поэтому выбранное наугад число $ B_{j} $, если оно удовлетворяет
условию $ \operatorname{HOD} (B_j,\widetilde{p})=1 $, попадет __не в__ $ \mathbb V_2 $, __а в__ $ \mathbb V_1 $
с вероятностью $ \le 1/2 $. Вероятность того, что два подряд выбранных
числа $ B_{j} $ не попадут в $ \mathbb V_2 $ будет уже $ \le 1/4 $, и т.д.
Таким образом, при достаточно большой выборке $ B_1,\dots,B_K $ мы "почти
наверняка" убедимся, что $ \tilde{p} $ --- составное. Если же все
условия алгоритма не выполняются для достаточно большой выборки чисел
$ B_{j} $, то, скорее всего, число $ \widetilde{p} $ --- простое.
!!П!! **Пример.** Является ли число $ 721801 $ простым?
**Решение.** Возьмем $ B_1=2,B_2=3,B_3=5,B_4=7,B_5=11 $. Применяя алгоритм
((:modular#вычисление_остатков_степенных_выражений квадрирования-умножения)), последовательно проверяем
выполнение условия алгоритма $ B_j^{\widetilde{p}-1} \not \equiv 1 \pmod{\widetilde{p}} $. Для $ B_5=11 $ условие
выполняется. Тестируемое число является составным, действительно: $ 721801=601 \cdot 1201 $.
♦
!!?!! Число $ \widetilde{p} $ из предыдущего примера обладает следующим свойством: для любого $ B\in \{1,\dots, \tilde{p}-1 \} $ такого, что $ \operatorname{HOD} (B,\tilde{p})=1 $, выполняется
$$ B^{\widetilde{p}-1} \equiv 1 \pmod{\widetilde{p}} \qquad \mbox{ или } \qquad B^{\widetilde{p}-1} \equiv A \pmod{\widetilde{p}} \ ,
$$
где $ A_{} $ --- фиксированное число (для рассмотренного примера $ A=719\,398 $). Доказать, что отмеченное свойство справедливо для всех чисел $ \widetilde{p} $ вида $ \widetilde{p}=p(2\,p-1) $, где оба сомножителя --- простые числа. Указать в этом случае выражение для $ A_{} $.
!!§!! В таблице примера из начала пункта именно такие числа $ \tilde{p} $ дают значения $ N_{} $ равные полным квадратам и "выбросы" для отношений $ N/\tilde p $ достигающие $ 0.5 $.
===Алгоритм Рабина-Миллера==
Более эффективным (и не имеющим исключительных случаев, подобных числам Кармайкла из алгоритма предыдущего пункта) оказывается алгоритм проверки числа на простоту,
основанный на теореме из
☞
((:modular:index#критерий_простоты_числа ПУНКТА)). Пусть $ \widetilde p>2 $ и число $ \widetilde{p}-1 $ имеет ((:modular:index#первообразный_корень четность)) $ \mathfrak r $, т.е.
$ \widetilde p-1=2^{\mathfrak r}q $, где $ q $ --- нечетное.
Если число $ \widetilde p $
--- простое, то для любого числа $ x\in \{1, \dots, \widetilde{p}-1\} $
выполняются условия
1.
либо $ x^q \equiv 1 \pmod{\widetilde p} $,
2.
либо $ x^{2^iq} \equiv -1 \pmod{\widetilde p} $ для некоторого $ i\in \{0,\dots, {\mathfrak r} -1 \} $.
Оказывается, что для составного $ \widetilde p $ существует достаточно большое количество значений $ x $, для которых
ни одно из указанных условий выполняться не будет. Именно, обозначим
$ \mathbb U_1 = \big\{ x\in\{1,\dots, \widetilde{p}-1\} \ \Big| \operatorname{HOD}(x,\widetilde{p})=1,\ x $ удовлетворяет хотя бы одному одному из условий
1
-
2
$ \big\} $
$ \mathbb U_2 = \big\{ x\in\{1,\dots, \widetilde{p}-1\} \ \Big| \operatorname{HOD}(x,\widetilde{p})=1,\ x $ не удовлетворяет ни одному одному из условий
1
-
2
$ \big\} $.
Для простых $ \widetilde{p} $ множество $ \mathbb U_2 $ заведомо пусто. Для составных $ \widetilde{p} $, очевидно, $ \operatorname{Card} (\mathbb U_1) + \operatorname{Card} (\mathbb U_2)= \phi (\widetilde{p}) $.
!!Т!! **Теорема [Рабин]**. //Для составных чисел// $ \widetilde{p}>9 $ //множество// $ \mathbb U_2 $ //содержит по крайней мере в три раза больше
элементов, чем// $ \mathbb U_1 $:
$$ \operatorname{Card} (\mathbb U_2) \ge 3 \operatorname{Card} (\mathbb U_1) \, . $$
----
Алгоритм Рабина-Миллера
проверки числа
$ \tilde{p} $
на простоту
Пусть $ \widetilde{p}>9 $ и $ \widetilde{p}-1=2^{\mathfrak r}q $, где $ q $ --- нечетное.
Последовательно выбираем различные
целые $ B_1,\dots,B_K $ из множества $ \{1, \dots, \widetilde{p}-1\} $ и проверяем:
$$
\begin{array}{rcl}
\quad B_j^{q} &\not \equiv & 1 \pmod{\widetilde{p}} , \\
B_j^{q} &\not \equiv& -1 \pmod{\widetilde{p}}, \\
B_j^{2q} &\not \equiv& -1 \pmod{\widetilde{p}}, \\
& \dots & \\
B_j^{2^{{\mathfrak r} -1}q} &\not \equiv& -1 \pmod{\widetilde{p}}.
\end{array}
$$
Если хотя бы для одного $ j $ все эти условия выполняются, то число $ \widetilde{p} $ --- составное.
Если для каждого $ j\in \{1,\dots,K\} $ не выполняется хотя бы одно из
условий, то
* либо число $ \widetilde{p} $ --- составное; вероятность этого события $ \le 1/4^K $;
* либо число $ \widetilde{p} $ --- простое; вероятность этого события $ \ge 1- 1/4^K $.
----
!!П!! Является ли число $ 46657 $ простым?
**Решение.** $ 46657-1=2^6\cdot 729 $, т.е. $ {\mathfrak r}=6,\, q=729 $.
Берем в качестве $ B_j $ последовательные простые числа и при
проверке условий алгоритма Рабина-Миллера обращаем внимание, что каждая
степень $ B_j^{2^{i}q} $ вычисляется как квадрат предыдущей
$ B_j^{2^{i -1}q} $. Все сравнения рассматриваются по модулю $ 46657 $:
$$2^{729} \equiv 512 ,\
512^2 \equiv 28859 ,\
28859^2\equiv 14431 , \
14431^2 \equiv 23570 , \ 23570^2 \equiv 1 ,
$$
и последнее возведение в квадрат излишне.
**Ответ.** Нет. **Проверка.** $ 46657=13\cdot 37 \cdot 97 $ (число Кармайкла).
((:crypto:pprime:pockl .))
==Источники==
[1]. **Нодден П., Китте К.** //Алгебраическая алгоритмика.// М.Мир. 1999.
[2]. **Саломаа А.** //Криптография с открытым ключом.// М., 1996.