Как найти достаточно большие простые числа?

Действительно, стойкость алгоритма RSA основана на возможности выбора простых чисел, состоящих из не менее 100 десятичных знаков. Поиск таких чисел последовательным перебором всех нечетных, начиная с некоторого стартового, и последующим «просеиванием» через решето Эратосфена весьма затруднителен. Проблему решают обходным маневром и решают «приближенно», а точнее — «вероятностно». Возможного кандидата на простое число подвергают испытанию серией однотипных и легко осуществимых тестов. Положительность результата хотя бы одного теста однозначно свидетельствует о том, что кандидат является числом составным; с другой стороны, отрицательный результат теста не дает абсолютной гарантии простоты кандидата, но свидетельствует о том, что вероятность его быть составным уменьшилась на определенную величину, скажем, в два раза. Тогда с увеличением количества отрицательных результатов все меньше шансов у испытуемого числа оказаться составным. Организовав серию испытаний из большого количества — например, 100 — тестов и получив все их результаты отрицательными, мы имеем право сказать, что кандидат является скорее всего («вроде бы») простым, с вероятностью не менее $$ 1-0.5^{100} \approx 99.\underbrace{99\dots99}_{28} \% \ . $$ Для таких чисел используют название вероятностно простые числа. Мы изложим здесь два способа организации упомянутой серии тестов, при этом тестируемое число будем обозначать $ \tilde{p} $.

Теорема Ферма утверждает, что для простого числа $ \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} $, их количество равно $ \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 ☞ ЗДЕСЬ ).

Далее, $$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, приведенной ☞ ЗДЕСЬ). Таким образом, действительно имеем: $ 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_{} $ называется числом Кармайкла²⁾, если условие $ 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 \} $ и проверяем³⁾: $$ 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 $. Применяя алгоритм квадрирования-умножения, последовательно проверяем выполнение условия алгоритма $ 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 $.

Более эффективным (и не имеющим исключительных случаев, подобных числам Кармайкла из алгоритма предыдущего пункта) оказывается алгоритм проверки числа на простоту, основанный на теореме из ☞ ПУНКТА. Пусть $ \widetilde p>2 $ и число $ \widetilde{p}-1 $ имеет четность $ \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 $ (число Кармайкла).

.

[1]. Нодден П., Китте К. Алгебраическая алгоритмика. М.Мир. 1999.

[2]. Саломаа А. Криптография с открытым ключом. М., 1996.