Простые числа

Phi-функция Эйлера

Phi-функция Эйлера, $$\varphi (n)$$, которую иногда называют тотиентой Эйлера, играет очень важную роль в криптографии. Функция $$\varphi (n)$$ находит из ряда чисел 0,1…., n–1 числа, взаимно простые с n. Можно вспомнить из лекции 2, что множество Zn* — числа, которые не больше чем n и взаимно простые с n. Функция $$\varphi (n)$$ вычисляет число элементов этого множества. Ниже показано, как найти это значение:

$$\varphi (1)=0$$.

$$\varphi (p)=p-1$$, если p — простое число.

$$\varphi (m \times n) = \varphi (m) \times \varphi (n) $$, если m и n — взаимно простые.

$$\varphi ({p^e}) = {p^e} - {p^{e - 1}}$$, если p — простое.

Мы можем объединить эти четыре правила, предназначенные для нахождения $$\varphi (n)$$.

$$\varphi (n) = ({p_1}^{{e_1}} - {p_1}^{{e_1} - 1}) \times ({p_2}^{{e_2}} - {p_2}^{{e_2} - 1}) \times \cdot \cdot \cdot \times ({p^{{e_k}}} - {p^{{e_k} - 1}})$$

Очень важно заметить, что значение $$\varphi (n)$$ для больших чисел может быть найдено, если может быть найдено число n и если n может быть представлено в виде разложения простых чисел. Другими словами, трудность нахождения $$\varphi (n)$$ зависит от трудности нахождения разложения n. Это рассматривается в следующем разделе.

Трудность нахождения $$\phi(n)$$ зависит от трудности нахождения разложения n.

Пример 12.7

Какое значение имеет $$\varphi (13)$$?

Решение

Поскольку 13 — простое число, $$\varphi (13)=(13-1)=12$$.

Пример 12.8

Какое значение имеет $$\varphi (10)$$?

Решение

Мы можем использовать третье правило: $$\varphi (10) = \varphi (2) \times \varphi (5) = 1 \times 4 = 4$$, поскольку 2 и 5 — простые числа.

Пример 12.9

Какое значение имеет $$\varphi (240)$$?

Решение

Мы можем записать $$240 = {2^4} \times {3^1} \times {5^1}$$.

Тогда

$$\varphi (240) = ({2^4} - {2^3}) \times ({3^1} - {3^0}) \times ({5^1} - {5^0}) = 64$$

Пример 12.10

Можно ли утверждать, что $$\varphi (49) = \varphi (7) \times \varphi (7) = 6 \times 6 = 36$$ ?

Решение

Нет.

$$\varphi (49) = {7^2} - {7^1} = 42$$

Пример 12.11

Какие числа являются элементами в Z14*?

Решение

$$\varphi (14) = \varphi (7) \times \varphi (2) = 6 \times 1 = 6$$. Элементы – это 1, 3, 5, 9, 11 и 13.

Интересный факт: если n > 2, значение $$\phi(n)$$ — четное.

Малая теорема Ферма

Малая теорема Ферма играет очень важную роль в теории чисел и криптографии. Ниже мы приводим две версии теоремы.

Первая версия

Первая версия говорит, что если p — простое число и a — целое число, такое, что p не является делителем a, тогда $${a^{p - 1}} \equiv 1{\text{ }}\bmod {\text{ }}p$$.

Вторая версия

Вторая версия вводит ограничивающие условие на a. Она утверждает, что если p — простое число и a — целое число, то $${a^p} \equiv a{\text{ }}\bmod {\text{ }}p$$.

Приложения

Хотя мы будем рассматривать приложения этой теоремы позже в этой лекции, теорема очень полезна для того, чтобы решить некоторые проблемы.

Возведение в степень. Малая теорема Ферма иногда полезна для того, чтобы быстро найти решение при возведении в степень. Следующие примеры показывают это.

Пример 12.12

Найдите результат 610 mod 11.

Решение

Мы имеем $${6^{10}}{\text{ }}\bmod {\text{ }}11 \equiv 1$$. Это первая версия малой теоремы Ферма, где p = 11.

Пример 12.13

Найдите результат 312 mod 11.

Решение

Здесь степень (12) и модуль (11) не соответствуют условиям теоремы Ферма. Но, применяя преобразования, мы можем привести решение к использованию малой теоремы Ферма.

$${3^{12}}\bmod {\text{ }}11 \equiv ({3^{11}} \times 3)\bmod {\text{ }}11 \equiv ({3^{11}}\bmod {\text{ }}11)(3{\text{ }}\bmod {\text{ }}11) \equiv (3 \times 3)\bmod {\text{ }}11 = 9$$

Мультипликативные инверсии. Очень интересное приложение теорема Ферма находит для некоторых мультипликативных инверсий, если модуль — простое число. Если p — простое число и a — целое число, такое, что p не является его делителем, тогда a-1mod p = ap-2 mod p. Это может быть легко доказано, если мы умножим обе стороны равенства на a и используем первую версию малой теоремы Ферма:

$$ a \times a^{-1} \mod\ p \equiv a \times a^{p-2} \mod\ p \equiv a^{p-1} \mod\ p \equiv 1 \mod\ p $$

Это приложение позволяет не использовать расширенный алгоритм Евклида для нахождения мультипликативных инверсий.

Пример 12.14

Инверсии по модулю простого числа могут быть найдены без использования расширенного Евклидова алгоритма:

a. 8-1 mod 17 = 817-2 mod 17 = 815 mod 17 = 15 mod 17

b. 5 –1 mod 23 = 523-2 mod 23 = 521 mod 23 = 14 mod 23

c. 60101 mod 101 = 60101-2 mod 101 = 6099 mod 101 = 32 mod 101

d. 22 -1 mod 211 = 22 211-2 modа 211 = 22209 mod 211 = 48 mod 211

Теорема Эйлера

Теорему Эйлера можно представить как обобщения малой теоремы Ферма. Модуль в теореме Ферма — простое число, модуль в теореме Эйлера — целое число. Мы вводим две версии этой теоремы.

Первая версия

Первая версия теоремы Эйлера подобна первой версии малой теоремы Ферма. Если a и n – взаимно простые, то $${a^{\varphi (n)}} \equiv 1{\text{ }}\bmod n$$.

Вторая версия

Вторая версия теоремы Эйлера подобна второй версии малой теоремы Ферма; она устраняет условие, что n должно быть взаимно простым с a. Если $$n = p \times q,a < n$$, а k — целое число, то $${a^{k \times \phi (n) + 1}} \equiv a\bmod n$$.

Приведем нестрогое доказательство второй версии, основанной на первой версии. Поскольку a < n, то возможны три случая:

1. Если a не кратно ни числу p, ни числу q, то a и n – взаимно простые.

$$\tt\parindent0pt a^{k\times \varphi (n)+1} \mod\ n=(a^{\varphi (n)})^{k} \times a \mod\ n=(1)^{k} \times a \mod\ n = \times a \mod\ n $$

2. Если a — кратное число p, $$a = (i \times p)$$, но не кратно числу q.

$$\tt\parindent0pt $a^{\varphi (n)} \mod\ q = (a^{\varphi (q)} \mod\ q)^{\varphi (p)} \mod\ q = 1 \to a^{\varphi (n)} \mod\ q = 1$ $a^{k\times \varphi (n)} \mod\ q = (a^{\varphi (n)} \mod\ q)^{k} \mod\ q = 1 \to a^{k\times \varphi (n)} \mod\ q = 1$ $a^{k\times \varphi (n)} \mod\ q = 1 \to a^{k\times \varphi (n)} = 1+j \times q$ (интерпретация сравнения) $a^{k\times \varphi (n)+1} = a \times (1+j \times q) = a+j\times q\times a=a+(i\times j)\times q\times p = a+(i\times j)\times n$ $a^{k\times \varphi (n)+1} = a+(i\times j)\times n \to a^{k\times \varphi (n)+1} = a \mod\ n$ (отношение конгруэнтности)$$$

3. Если a кратно q ($$a = i \times q$$), но не кратно p, доказательство второго случая то же самое, но p и q меняются местами.

Вторая версия теоремы Эйлера используется в криптографической системе RSА (лекция 10).

Приложения

Хотя мы рассмотрим некоторые приложения теоремы Эйлера позже в этой лекции, теорема очень полезна для того, чтобы решать некоторые задачи.

Возведение в степень. Теорема Эйлера иногда полезна, чтобы быстро найти решение некоторых задач с возведением в степень. Следующие примеры показывают идею этого процесса.

Пример 12.15

Найдите результат 624 mod 35.

Решение

Мы имеем $${6^{24}}\bmod {\text{ }}35 = {6^{\varphi (35)}}\bmod 35 = 1$$

Пример 12.16

Найдите результат 2062 mod 77.

Решение

Если введем k = 1 согласно второй версии, мы имеем:

2062 mod 77 = (20 mod 77) mod 77 = (20)(20) mod 77 = 15

Мультипликативные инверсии. Теорема Эйлера может использоваться, чтобы найти мультипликативную инверсию по простому модулю. Теорема Эйлера может применяться, чтобы найти мультипликативные инверсии по составному модулю. Если n и a – взаимно простые, то $${a^{ - 1}}\bmod n = {a^{\varphi (n) - 1}}\bmod n$$. Это может быть легко доказано умножением обеих сторон равенства на a.

$$ a^{-1} \mod\ n = a \times a^{\varphi (n)-1} \mod\ n = a^{\varphi (n)} \mod\ n = 1 \mod\ n $$

Пример 12.17

Мультипликативная инверсия по составному модулю может быть найдена без использования расширенного евклидова алгоритма, если мы знаем разложение на множители составного объекта:

a. $${8^{ - 1}}\bmod 77 = {8^{\varphi (77) - 1}}\bmod 77 = {8^{59}}\bmod 77 = 29\bmod 77$$

b. $${7^{ - 1}}\bmod 15 = {7^{\varphi (15) - 1}}\bmod 15 = {7^{7}}\bmod 15 = 13\bmod 15$$

c. $${6^{ - 1}}\bmod 187 = {7^{\varphi (187) - 1}}\bmod 187 = {60^{159}}\bmod 187 = 53\bmod 187$$

d. $${71^{ - 1}}\bmod 100 = {71^{\varphi (100) - 1}}\bmod 100 = {71^{39}}\bmod 100 = 31\bmod 100$$

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

Два математика, Мерсенна и Ферма, попытались получить формулу, которая могла бы генерировать простые числа.

Простые числа Мерсенны

Мерсенна предложил следующую формулу, которую называют номера Мерсенны. Он предполагал, что формула перечисляет все простые числа.

M_p = 2^p–1

Если p в приведенной выше формуле — простое число, то, как предполагали, Mp должно быть простым числом. Годы спустя было доказано, что не все числа, полученные по формуле Мерсенны, — простые числа. Ниже приведен список некоторых номеров Мерсенны.

$$\tt\parindent0pt $M_{2} = 2^{2} – 1 = 3$ $M_{3} = 2^{3} – 1 = 7$ $M_{5} = 2^{5} – 1 = 31$ $M_{7} = 2^{7} – 1 = 127$ $M_{11} = 2^{11} – 1 = 2047$ Непростое число ($2047 = 23 \times 89$) $M_{13} = 2^{13} – 1 = 8191$ $M_{17} = 2^{17} – 1 = 131071$ $$

Оказалось, что M11 — не простое число. Однако было найдено, что 41 число по формуле Мерсенны — простые; одно из последних найденных чисел Мерсенны — М124036583, наибольшее число содержит 7 253 733 цифр. Поиск продолжается.

Ферма пробовал найти формулу, которая генерирует простые числа. Следующая формула — для чисел Ферма:

Число в формуле M_p = 2^p–1, называемое числом Мерсенны, может быть или не быть простым числом.

Простые числа Ферма

Ферма попытался найти формулу для генерации простых чисел. Он предложил следующую формулу, которая теперь называется формулой Ферма, и проверил номера от F0 (n=0,1,…) до F4, но оказалось, что уже F4 — не простое число.

$${F_n} = {2^{{2^n}}} + 1$$

F0 = 3

F1 = 17

F2 = 257

F3 = 65537

$$F_{4} = 4294967297 = 641 \times 6700417$$. Не простое число

Фактически было доказано, что многие номера до F24 — составные числа.

12.2. Испытание простоты чисел

Если формулы получения простых чисел, подобно формулам Ферма или Мерсенна, не гарантируют, что полученные числа — простые, то как мы можем генерировать большие простые числа для криптографии? Мы можем только выбрать случайно большое число и провести испытание, чтобы убедиться, что оно — простое.

Нахождение алгоритма, который правильно и эффективно проверяет очень большое целое число и устанавливает: данное число – простое это число или же составной объект, — всегда было проблемой в теории чисел и, следовательно, в криптографии. Однако, недавние исследования (одно из которых мы обсуждаем в этом разделе) выглядят очень перспективными.

Алгоритмы, которые решают эту проблему, могут быть разделены на две обширные категории — детерминированные алгоритмы и вероятностные алгоритмы. Ниже рассматриваются некоторые представители обеих категорий. Детерминированный алгоритм всегда дает правильный ответ. Вероятностный алгоритм дает правильный ответ в большинстве, но не во всех случаях. Хотя детерминированный алгоритм идеален, он обычно менее эффективен, чем соответствующий вероятностный.

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

Детерминированный алгоритм, проверяющий простоту чисел, принимает целое число и выдает на выходе признак: это число — простое число или составной объект. До недавнего времени все детерминированные алгоритмы были неэффективны для нахождения больших простых чисел. Как мы коротко покажем, новые взгляды делают эти алгоритмы более перспективными.

Алгоритм теории делимости

Самое элементарное детерминированное испытание на простоту чисел — испытание на делимость. Мы используем в качестве делителей все числа, меньшие, чем $$\sqrt n $$. Если любое из этих чисел делит n, тогда n — составное. Алгоритм 12.1 показывает проверку на делимость в ее примитивной и очень неэффективной форме.

Алгоритм может быть улучшен, если проверять только нечетные номера. Он может быть улучшен далее, если использовать таблицу простых чисел между 2 и $$\sqrt n $$. Число арифметических операций в алгоритме 12.1 — $$\sqrt n $$. Если мы принимаем, что каждая арифметическая операция использует только операцию на один бит (чисто условное соглашение), тогда сложность разрядной операции алгоритма 12.1 — $$\sqrt {{2^{{n_b}}}} = {2^{{\raise0.7ex\hbox{${{n_b}}$} \!\mathord{\left/ {\vphantom {{{n_b}} 2}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{$2$}}}} $$, где nb – число битов в n. В больших системах, обозначаемых О, сложность может быть оценена O(2n): экспоненциально (см. приложение L). Другими словами, алгоритм делимости неэффективен, если nb большое.

Сложность побитного испытания делимостью показательна.

Пример 12.18

Предположим, что n имеет 200 битов. Какое число разрядных операций должен был выполнить алгоритм делимости?

Решение

Сложность побитовых операций этого алгоритма — $${2^{{\raise0.7ex\hbox{${{n_b}}$} \!\mathord{\left/ {\vphantom {{{n_b}} 2}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{$2$}}}} $$. Это означает, что алгоритму необходимо провести 2100 битовых операций. Если алгоритм имеет скорость 230 операций в секунду, то необходимо 270 секунд для проведения испытаний.

$$\tt\parindent0pt

Тест на делимость (n)

\ \ \ \ \ \ \ \ \ //n – число тестов на простоту

\{ 

\ \ r \gets  2

\ \ while (r < \sqrt n)

\ \ \ \ \{ 

\ \ \ \ if (r|n) return "a composite"  // составное

\ \ \ \ r \gets  r+1

\ \ \ \} 

\ \ return "a prime"  //простое

\}	$$

AKS-алгоритм

В 2002 г. индийские ученые Агравал, Каял и Сахсена (Agrawal, Kayal и Saxena) объявили, что они нашли алгоритм для испытания простоты чисел с полиномиальной сложностью времени разрядных операций 0 ((log2nb)). Алгоритм использует тот факт, что $${(x{\text{ }}-a)^p} \equiv ({x^p}-{\text{ }}a)\bmod p$$. Интересно наблюдать, что некоторые будущие разработки делают этот алгоритм стандартным тестом для определения простоты чисел в математике и информатике.

Пример 12.19

Предположим, что n имеет 200 битов. Какое число разрядных операций должен был выполнить алгоритм AKS?

Решение

Сложность разрядной операции этого алгоритма — O((log 2 n b) 12). Это означает, что алгоритму надо только (log2 200) 12 = 39 547 615 483 битовых операций. На компьютере, способном выполнить 1 миллиард битов в секунду, алгоритму требуется только 40 секунд.

Вероятностные алгоритмы

До AKS-алгоритма все эффективные методы для испытания простоты чисел были вероятностные. Эти методы могут использоваться еще некоторое время, пока AKS формально не принят как стандарт.

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

a. Если целое число, которое будет проверено, — фактически простое число, алгоритм явно возвратит простое число.

b. Если целое число, которое будет проверено, — фактически составной объект, алгоритм возвращает составной объект с вероятностью $$1 - \varepsilon $$, но может возвратить простое число с $$ \varepsilon $$ вероятности. Вероятность ошибки может быть улучшена, если мы выполняем алгоритм несколько раз с различными параметрами или с использованием различных методов. Если мы выполняем алгоритм m раз, вероятность ошибки может уменьшиться до _m.

Тест Ферма

Первый вероятностный метод, который мы обсуждаем, — испытание простоты чисел тестом Ферма.

Если n — простое число, то $$a^{n-1}\equiv 1 \mod n$$.

Обратите внимание, что если n — простое число, то сравнение справедливо. Это не означает, что если сравнение справедливо, то n — простое число. Целое число может быть простым числом или составным объектом. Мы можем определить следующие положения как тест Ферма:

$$\tt\parindent0pt Если n — простое число, то a^{n-1} \equiv 1 \mod\ n Если n — составной объект, то возможно, что a^{n-1} \equiv 1 \mod\ n $$

Простое число удовлетворяет тесту Ферма. Составной объект может пройти тест Ферма с вероятностью $$ \varepsilon $$. Сложность разрядной операции испытания Ферма равна сложности алгоритма, который вычисляет возведение в степень. Позже в этой лекции мы приводим алгоритм для быстрого возведения в степень со сложностью разрядной операции O(nb ), где О — номер битов в n. Вероятность может быть улучшена, если проверка делается с несколькими числами (a1, a2 и так далее). Каждое испытание увеличивает вероятность, что испытуемое число – это простое число.

Пример 12.20

Проведите испытание Ферма для числа 561.

Решение

Используем в качестве основания число 2.

2561-1 = 1 mod 561

Число прошло тест Ферма, но это — не простое число, потому что

$$561 = 33 \times 17$$.

Испытание квадратным корнем

В модульной арифметике, если n — простое число, то квадратный корень равен только 1 (либо +1, либо –1). Если n — составной объект, то квадратный корень — +1 или (-1), но могут быть и другие корни. Это называют испытанием простоты чисел квадратным корнем. Обратите внимание, что в модульной арифметике –1 означает n–1.

$$\tt\parindent0pt Если n — простое число, $\sqrt 1 \mod\ n = \pm 1$ Если n — составной объект, $\sqrt 1 \mod\ n = \pm 1$, и возможны другие значения $$

Пример 12.21

Каковы квадратные корни 1 mod n, если n равно 7 (простое число)?

Решение

Единственные квадратные корни 1 mod n – это числа 1 и –1. Мы можем видеть, что

12 = 1 mod 7	  (–1)2 = 1 mod 7
22 = 4 mod 7	  (–2)2 = 4 mod 7
32 = 2 mod 7	  (–3)2 = 2 mod 7

Заметим, что тест не дает результатов для 4, 5 и 6, потому что 4 = –3 mod 7, 5 = –2 mod 7 и 6 = –1 mod 7.

Пример 12.22

Каков квадратный корень из 1 mod n, если n равно 8 (составное)?

Решение

Имеется три решения: 1, 3, 5 и 7 (которые дают –1). Мы можем также видеть, что

12 = 1 mod 8	  (–1)2 = 1 mod 8
32 = 1 mod 8	  (–5)2 = 1 mod 8

Пример 12.23

Каков квадратный корень из 1 mod n, если n равно 17 (простое)?

Решение

Имеются только два решения, соответствующие поставленной задаче: это 1 и (–1).

12 = 1 mod 17	  (-1)2 = 1 mod 17
22 = 4 mod 17	  (-2)2 = 4 mod 17
32 = 9 mod 17	  (-3)2 = 9 mod 17
42 = 16 mod 17	  (-4)2 = 16 mod 17
52 = 8 mod 17	  (-5)2 = 8 mod 17
62 = 2 mod 17	  (-6)2 = 2 mod 17
72 = 15 mod 17	  (-7)2 = 15 mod 17
82 = 13 mod 17	  (-8)2 = 13 mod 17

Заметим, что не надо проверять целые числа, большие 8, потому что 9 = –8 mod 17

Пример 12.24

Каков квадратный корень из 1 mod n, если n равно 22 (составное)?

Решение

Сюрприз в том, что имеется только два решения: +1 и –1, хотя 22 — составное число.

12    = 1 mod 22
(-1)2 = 1 mod 22

Хотя во многих случаях имеется испытание, которое показывает нам однозначно, что число составное, но это испытание провести трудно. Когда дано число n, то все числа, меньшие, чем n (кроме чисел 1 и n–1), должны быть возведены в квадрат, чтобы гарантировать, что ни одно из них не равно 1. Это испытание может использоваться для чисел (не +1 или –1), которые в квадрате по модулю n дают значение 1. Этот факт помогает в испытании Миллера–Рабина, которое рассматривается в следующем разделе.

Тест Миллера-Рабина

Тест Миллера-Рабина определения простого числа есть комбинация тестов Ферма и квадратного корня. Он элегантным способом находит сильное псевдопростое число (простое число с очень высокой вероятностью). В этом тесте мы записываем n–1 как произведение нечетного числа m и степени числа 2.

$$ n – 1 = m \times 2^{k} $$

В тесте Ферма при основании a можно записать так, как это показано ниже.

Идея теста на простоту числа на основе Ферма

$$a^{n-1}=a^{m\times2k}=[a^m]^2^k=[a^m]^2$$

Другими словами, вместо того чтобы вычислять an-1 (mod n) в один шаг, мы можем сделать это в k + 1 шагов. Какое преимущество в таком применении? Преимущество заключается именно в том, что испытание квадратным корнем может быть выполнено на каждом шаге. Если квадратный корень показывает сомнительные результаты, мы останавливаемся и объявляем n составным номером. На каждом шаге мы обеспечиваем, что тест Ферма и испытание квадратным корнем удовлетворено на всех парах смежных шагов, если оно удовлетворительно (если результат равен 1).

Инициализация

Выберите основу и вычислите T = am, в который m = (n – 1) / 2k.

a. Если T равно +1 или –1, объявляют, что n — сильное псевдопростое число, и процесс останавливается. Мы говорим, что n прошел два испытания: тест Ферма и испытание квадратным корнем. Почему? Потому что если T равно $$ \pm {\text{1}}$$, то T станет 1 на следующем шаге и остается 1 до прохождения теста Ферма. Кроме того, T прошел испытание тестом квадратного корня, потому что T был бы равен 1 на следующем шаге и квадратный корень был бы равен 1 (на следующем шаге) и равен $$ \pm {\text{1}}$$ (на этом шаге).

b. Если T равен другому значению, мы не уверены, является ли n простым числом или составным объектом, значит, процесс будет продолжаться на следующем шаге.

Шаг 1

Возводим T в квадрат.

a. Если результат равен +1, мы определенно знаем, что тест Ферма пройден, потому что T остается 1 для последующих испытаний. Испытание квадратным корнем, однако, не прошло. Поскольку T равно 1 на этом шаге и имело на предыдущем шаге другое значение, чем $$ \pm {\text{1}}$$ (причина, почему мы не остановились на предыдущем шаге), n объявляют составным объектом, и процесс останавливается.

b. Если результат равен (–1), мы знаем, что n в конечном счете пройдет тест Ферма. Мы знаем, что он пройдет испытание квадратным корнем, потому что T равно (–1) в этом шаге и станет 1 на следующем шаге. Мы объявляем n сильным псевдослучайным простым числом и останавливаем процесс.

c. Если T имеет еще какое-либо значение, мы не уверены, имеем ли мы дело с простым числом, и процесс продолжается на следующем шаге.

Шаги 2 до k–1

Этот шаг и все остальные шаги до k–1 такие же, как и шаг 1.

Этот шаг не является необходимым. Если мы достигли его и не приняли решение, он не поможет нам. Если результат этого шага (–1), значит, тест Ферма пройден, но поскольку результат предыдущего шага — не $$ \pm {\text{1}}$$, испытание квадратное корня не пройдено. После шага k – 1, если процесс не остановлен, мы объявляем, что n — составное.

Тест Миллера-Рабина требует от 0 до k–1.

Алгоритм 12.2 показывает псевдокод для теста Миллера-Рабина.

$$\tt\parindent0pt

Тест Миллера-Рабина (n, a)    \ \ \ \ \          // n —  число; a —  основание

\{ 

\ \ Find m and k such that $n–1 = m \times  2^{k}$

\ \ $T \gets  a^{m} \mod\ n$

\ \ if ( $T = \pm 1$) return "a prime"

\ \ for (I $\gets$  1 to k–1)     \ \ \ \ \\                   // k–1 — максимальное число шагов

\ \{ 

\ \ \ $T \gets  T^{2} \mod\ n$

\ \ \ if (T = +1) return "a composite"      \ \ \    // составное

\ \ \ if (T = –1) return "a prime"      \ \ \ \       // простое

\ \} 

return "a composite"	$$

Существует доказательство, что каждый раз, когда для числа проводится тест Миллера-Рабина, вероятность получить результат "не простое число" — 1/4. Если прошло m тестов (с m различными основаниями), вероятность, что тест выдаст не простое число — (1/4) m.

Пример 12.25

Проведите тест Миллера-Рабина к числу 561.

Решение

Используя основание 2, получим $$561 - 1 = 35 \times 2^4$$, что означает, что m = 35, k = 4 и а = 2

$$\tt\parindent0pt Инициализация:\ \ \ T = 2^{35} \mod\ 561 = 263 \mod\ 561 k = 1\ \ \ \ \ \ T = 263^{2} \mod\ 561 = 166 \mod\ 561 k = 2\ \ \ \ \ \ T = 166^{2} \mod\ 561 = 67 \mod\ 561 k = 3\ \ \ \ \ \ T = 67^{2} \mod\ 561 = +1 \mod\ 561 \to \text{ составное} $$

Пример 12.26

Мы уже знаем, что 27 — не простое число. Попробуем применить тест Миллера-Рабина.

Решение

Основание равно 2, тогда $$27-1 = 13 \times {2^1}$$, что означает m = 13, k = 1 и a = 2. В этом случае k – 1 = 0, и мы должны сделать только шаг инициализации:

T = 213 mod 27 = 11 mod 27. Однако поскольку алгоритм не делает ни одного цикла, вырабатывается решение "составной объект".

Пример 12.27

Мы знаем, что 61 — простое число; давайте посмотрим, что даст тест Миллера-Рабина

Решение

Мы используем основание 2.

$$\tt\parindent0pt $61 – 1 = 15 \times 2^{2} \to m = 15 k = 2 a = 2 $ Инициализация:\ \ \ T = 2^{15} \mod\ 61 = 11 \mod\ 61 \ к = 1\ \ \ \ \ \ T = 11^{2} \mod\ 61 = –1 \mod\ 61 \to \text{простое число} $$

Обратите внимание, что последний результат — это 60 mod 61, но мы знаем, что 60 = –1 mod 61.

Рекомендованные тесты простоты чисел

Сегодня один из самых популярных тестов простоты чисел — комбинация теории делимости и тест Миллера-Рабина. При этом рекомендуются следующее шаги:

Выбрать нечетное целое число, потому что все четные целые числа (кроме 2) — явно составные объекты.

Сделать некоторые тривиальные испытания теории делимости на некоторых известных простых числах, таких как 3, 5, 7, 11, 13: так, чтобы убедиться, что вы не имеете дело с очевидным составным объектом. Если они не являются делителями при всех этих испытаниях, сделайте следующий шаг. Если выбранное число не прошло хотя бы один из этих тестов, вернитесь на один шаг и выберите другое нечетное число.

Выбрать набор оснований для теста. Большое множество оснований предпочтительно.

Сделать тест Миллера-Рабина на каждом из оснований. Если любой из них не проходит, вернитесь на один шаг и выберите другой нечетный номер. Если тесты прошли для всех оснований, объявите это число как сильное псевдопростое число.

Пример 12.28

Номер 4033 — составной объект ($$37 \times 109$$). Это подтверждает рекомендованное испытание простоты чисел?

Решение

1. Выполним проверку согласно теории делимости. Проверим сначала числа 2, 3, 5, 7, 11, 17 и 23 – не являются делителями числа 4033.

2. Выполним испытание Миллера-Рабина с основанием 2, тогда $$4033-1 = 63 \times {2^6}$$, что означает m = 63 и k = 6.

$$\tt\parindent0pt Инициализация: $T \equiv 2^{63} (mod\ 4033) \equiv 3521 (mod\ 4033)$ \ $k = 1$\ \ \ \ \ \ \ \ $T \equiv T^{2} = 3521^{2} (mod\ 4033) = –1 (mod\ 4033) \to \text{Тест прошел}$ $$

3. Но мы не удовлетворены. Мы продолжаем с другим основанием — 3.

$$\tt\parindent0pt Инициализация: \ \ $T \equiv 3^{63}(mod\ 4033) \equiv 3551(mod\ 4033)$ $k = 1\ \ \ \ \ \ T \equiv T^{2} \equiv 3551^{2} (mod\ 4033 \equiv 2443 (mod\ 4033)$ $k = 2\ \ \ \ \ \ T \equiv T^{2} \equiv 2443^{2} (mod\ 4033 \equiv 3442 (mod\ 4033)$ $k = 3\ \ \ \ \ \ T \equiv T^{2} \equiv 3442^{2} (mod\ 4033 \equiv 2443 (mod\ 4033) $ $k = 4\ \ \ \ \ \ T \equiv T^{2} \equiv 2443^{2} (mod\ 4033 \equiv 3442 (mod\ 4033)$ $k = 5\ \ \ \ \ \ T \equiv T^{2} \equiv 3442^{2} (mod\ 4033 \equiv 2443 (mod\ 4033)$ Не соответствует (составное) $$

12.3. Разложение на множители

Разложение на множители — предмет непрерывного исследования в прошлом; и такие же исследования, вероятно, продолжатся в будущем. Разложение на множители играет очень важную роль в безопасности некоторых криптосистем с открытым ключом (см. лекции 14-15).

Основная теорема арифметики

Согласно Основной теореме арифметики любое положительное целое число больше единицы может быть уникально записано в следующей главной форме разложения на множители, где p1, p2, ..., pk — простые числа и e1, e2, ..., ek — положительные целые числа.

$$ n = p^{e1}_1\times p_{2}^{e_2}\times\dots\times p^{k}_{e_k} $$

Есть непосредственные приложения разложения на множители, такие как вычисление наибольшего общего делителя и наименьшего общего множителя.

Наибольший общий делитель

В лекции 2 мы уже обсуждали наибольший общий делитель двух номеров, НОД (a, b). Посмотрите, как евклидов алгоритм дает это значение, но это значение может также быть найдено, если мы знаем разложение на множители чисел a и b.

$$a = {p_1}^{{a_1}} \times {p_2}^{{a_2}} \times \ldots \times {p_k}^{{a_k}}$$ $$b = {p_1}^{{b_1}} \times {p_2}^{{b_2}} \times \ldots \times {p_k}^{{b_k}}$$ $$HOD(a,b) = {p_1}^{\min ({a_1},{b_1})} \times {p_2}^{\min ({a_2},{b_1})} \times \ldots \times {p_k}^{\min ({a_k},{b_1})}$$

Наименьшее общее кратное

Наименьшее общее кратное, НОК (a, b), — наименьшее целое число, кратное числам a и b. Используя разложение, мы также находим НОК (a, b).

$$a = {p_1}^{{a_1}} \times {p_2}^{{a_2}} \times \ldots \times {p_k}^{{a_k}}$$ $$HOD(a,b) = {p_1}^{\max ({a_1},{b_1})} \times {p_2}^{\max ({a_2},{b_1})} \times \ldots \times {p_k}^{\max ({a_k},{b_1})}$$

Может быть доказано, что НОД (a,b) и НОК (a,b) связаны с друг другом, как это показано ниже:

$$ НОК (a,b) \times НОД (a,b) = a \times b $$

Методы разложения на множители

Поиск эффективных алгоритмов для разложения на множители больших составных чисел ведется давно. К сожалению, совершенный алгоритм для этого пока не найден. Хотя есть несколько алгоритмов, которые могут разложить число на множители, ни один не способен провести разложение достаточно больших чисел в разумное время. Позже мы увидим, что это хорошо для криптографии, потому что современные криптографические системы полагаются на этот факт. В этой секции мы даем несколько простых алгоритмов, которые проводят разложение составного числа. Цель состоит в том, чтобы сделать процесс разложения на множители менее трудоёмким.

Метод проверки делением

Самый простой и наименее эффективный алгоритм — метод разложения на множители проверкой делением. Мы просто пробуем все положительные целые числа начиная с 2, для того чтобы найти одно, которое делит n. После обсуждения решета Эратосфена мы знаем, что если n составное, то делитель будет простым числом $$p \leqslant \sqrt n $$. Алгоритм 12.3 показывает этот метод. Алгоритм имеет два цикла: один внешний и один внутренний, находит уникальные множители в разложении; внутренняя петля находит повторяющиеся множители разложения. Например, $$24 = {2^3} \times 3$$. Внешний цикл множители 2 и 3. Внутренний цикл находит, что число 2 множитель.

$$\tt\parindent0pt

разложение проверкой\_  делением (n)

\{                           // n раскладываемое число

\ \ $a \gets  2$

\ \ while ($a \le  \sqrt n$)

\ \ \{                                                      

\ \ \ while ($n \mod\ a = 0$)

\ \ \{ 

\ \ \ \ output a\ \ \ \      // элементы  выхода "один за другим"

\ \ \ \ $n = n/a$

\ \ \ \} 

\ \ $a \gets  a + 1$

\ \ \} 

\ if ($n > 1$) output n\ \ \ \        // n не имеет больше множителей

\}	$$

Сложность. Метод проверки делением обычно хорош, если n < 210, но он неэффективен и неосуществим для разложения больших целых чисел. Сложность алгоритма (приложение L) показательна.

Пример 12.29

Используйте алгоритм проверки делением, чтобы найти сомножители числа 1233.

Решение

Мы выполняем программу, основанную на алгоритме, и получаем следующий результат:

$$1233 = {3^2} \times 137$$

Пример 12.30

Используйте алгоритм проверки делением, чтобы найти сомножители 1523357784.

Решение

Мы выполняем программу, основанную на алгоритме, и получаем следующий результат:

$$1523357784 = {2^3} \times {3^2} \times 13 \times 37 \times 43987$$

Метод Ферма

Метод Ферма разложения на множители (алгоритм 12.4) делит номер n на два положительных целых числа (a и b — не обязательно простые числа) так, чтобы $$n = a \times b$$.

$$\tt\parindent0pt

Разложение\_  на\_  множители Ферма (n)\ \ \ \      // n — раскладываемое число

\{ 

\ \ $x \gets  \sqrt n$

\ \ while (< n)       // наименьшее целое, большее, чем $\sqrt n$

\ \ \ \ \{ 

\ 

\ \ \ \ $w \gets  x^{2} – n$

\ \ \ \ if (w полный квадрат числа) $y \gets  \sqrt w ;\ a \gets  x + y;\ b \gets  x-y;$ return a and b

\ \ \ \ $x \gets  x+1$

\ \ \ \ \} 

\}	$$

Метод Ферма основан на факте, что если мы можем найти x и y, такие, что n = x2 – y2, тогда мы имеем

$$ n = x^{2} – y^{2}= a \times b\text{ при }a = (x + y)\text{ и }b = (x – y) $$

Метод сводится к попытке найти два целых числа a и b, близкие друг к другу ($$a \approx b $$). Начинаем с наименьшего целого числа, большего, чем $$x = \sqrt n $$. Потом пробуем найти другое целое число y, такое, чтобы выполнялось уравнение y2 = x2 – n. В каждой итерации мы должны рассмотреть, является ли результат x² – n полным квадратом. Если мы находим такое значение для y, мы вычисляем a и b и выходим из цикла. Если мы не делаем этого, мы проводим другую итерацию.

Заметим, что метод не обязательно находит разложение на простые числа (каноническое разложение); алгоритм должен быть повторен рекурсивно для каждого из значений a и b, пока не будут найдены сомножители в виде простых чисел.

Сложность. Сложность метода Ферма является близкой к показательному закону (см. приложение L).

p – 1 Метод Полларда

В 1974 г. Джон Поллард разработал метод, который находит разложение числа p на простые числа. Метод основан на условии, что p – 1 не имеет сомножителя, большего, чем заранее определенное значение B, называемое границей. Алгоритм Полларда показывает, что в этом случае

p = НОД (2B! – 1, n )

Алгоритм 12.5 показывает псевдокод для p – 1 метода Полларда разложения на множители. Когда мы выходим из второго цикла, в a сохраняется 2B!.

$$\tt\parindent0pt

Pollard\_ (p–1)\_ Factorization (n,B)

\{\ \ \ \ \ \                      // n —  раскладываемое число

\ \ $a \gets  2$

\ \ $e \gets  2$

\ \ while ($e \le  B$)

\ \ \ \ \{ 

\ \ \ \ $a \gets  a^{e} \mod\ n$

\ \ \ \ $e \gets  e +1$

\ \ \ \} 

\ \ $p \gets \ gsd\ (a–1, n)$\ \ \         // gsd – НОД  (наибольший общий делитель)

\ \ if 1 < p < n return p

\ \ return failure

\}	$$

Сложность. Заметим, что этот метод требует сделать B – 1 операций возведения в степень (a = a e mod n). Как мы увидим позже в этой лекции, есть быстрый алгоритм возведения в степень, который выполняет это за 2 1og2 B операций. Метод также использует вычисления НОД, который требует n3 операций. Мы можем сказать, что сложность — так или иначе больше, чем O(B) или O(2n), где nb — число битов в B. Другая проблема – этот алгоритм может заканчиваться сигналом об ошибке. Вероятность успеха очень мала, если B имеет значение, не очень близкое к величине $$\sqrt n $$.

Пример 12.31

Используя p – 1 метод Полларда, найдите сомножители числа 57247159 с границей B = 8.

Решение

Мы выполняем программу, основанную на рассмотренном выше алгоритме, и находим, что p = 421. Фактически $$57247159 = 421 \times 135979$$. Обратите внимание, что 421 — простое число и p –1 не имеет ни одного сомножителя, большего 8, т.е. ($$421-1 = {2^2} \times 3 \times 5 \times 7$$).

РО (Rho) – метод Полларда

В 1975 г. Джон М. Поллард разработал второй метод для разложения на множители, который базируется на следующих положениях:

a. Предположим, что есть два целых числа, x1 и x2, таких, что p делит x1 – x2, но эта разность не делится на n.

b. Может быть доказано, что p = НОД (x1 – x2, n). Поскольку p делит x1 – x2 , можно записать, что $${x_1}-{x_2} = q \times p$$. Но поскольку n не делит x1 – x2, очевидно, что q не делится n. Это означает, что НОД (x1 – x2, n) является либо 1, либо сомножитель.

Следующий алгоритм повторно выбирает x1 и x2, пока не находит соответствующую пару.

Выберите x1 — малое случайное целое число, называемое первоисточником.

Используйте функцию, чтобы вычислить x2, такую, чтобы n не делило x1 – x2. Функция, которая может быть применена, — это x2 = f (x1 ) = x1 2 + a (a обычно выбирается как 1).

Вычислить НОД (x1 – x2 , n). Если это не 1, результат – сомножитель. Алгоритм останавливается. Если это 1, то происходит возвращение, чтобы повторить процесс с x1. Теперь мы вычисляем x3. Заметим, что в следующем раунде мы начинаем с x3 и так далее. Если мы перечислим значения нескольких x, используя РО (rho) алгоритм Полларда, мы увидим, что дуга значений в конечном счете повторяется, создавая форму, подобную греческой букве РО (rho) или в греческом алфавите $$\rho$$), как это показано на рис. 12.2.

(рис 12.2) Успешные числа в Ро алгоритме Полларда

Чтобы уменьшить число итераций, алгоритм был немного изменен. Он начинается с пары (x0, x0), и итеративно вычисляет (x1, x2), (x 2, x4), (x3, x6), …. (xi .x2i), используя равенство xi+1 = f (xi). В каждой итерации мы применяем функцию f (xi) (начиная с шага 2). При этом вычисление идут следующим образом: в паре вычисляется один раз первый элемент и дважды вычисляется второй элемент (см. алгоритм 12.6).

$$\tt\parindent0pt

Pollard\_  rho \_ Factorization (n, B)\ \ \ \      // n — число, которое надо разложить

\{ 

\ \ $x \gets  2$

\ \ $y \gets  2$

\ \ $p \gets  i$

\ \ while (p = 1)

\ \ \ \{ 

\ \ \ \ $x \gets  f(x) \mod\ n$

\ \ \ \ $y \gets  f(f(y) \mod\ n) \mod\ n$

\ \ \ \ $p \gets  gcd (x - y, n)$\ \ \ \           // gsd (a,b) – это НОД (a,b)

\ \ \ \} 

\ \ return p

\}\ \ \ \ \          // если p = n, программа не выполнена	$$

Сложность. Метод требует $$\sqrt p $$ арифметических операций. Однако поскольку мы предполагаем, что p будет меньше или равняться $$\sqrt n $$, мы ожидаем около n1/4 арифметические операций. Это означает, что сложность разрядной операции 0 ($${2^{{\raise0.7ex\hbox{${{n_b}}$} \!\mathord{\left/ {\vphantom {{{n_b}} 4}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{$4$}}}}$$) показательна.

Пример 12.32

Предположим, что есть компьютер, который, может выполнить 230 (почти 1 миллиард) разрядных операций в секунду. Какое приблизительно время потребуется, чтобы разложить на множители целое число размера

a. 60 десятичных цифр

b. 100 десятичных цифр

Решение

a. Множество 60 десятичных цифр имеют почти 200 битов. Сложность — $${2^{{\raise0.7ex\hbox{${{n_b}}$} \!\mathord{\left/ {\vphantom {{{n_b}} 4}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{$4$}}}}$$или 250. Со скоростью 230 операций в секунду алгоритм может быть выполнен в 220 секунды или почти за 12 дней

b. Множество 100 десятичных цифр — это почти 300 битов. Сложность — 275. Со скоростью 230 операций в секунду алгоритм может быть выполнен в 245 секунд или за много лет

Пример 12.33

Мы написали программу, чтобы вычислить разложение 434617. Результат — 709 ($$434617 = 709 \times 613$$) Таблица 12.2 показывает значения пар (x и y) и p в этом процессе.

Более эффективные методы

В течение прошлых нескольких десятилетий были изобретены несколько методов разложения на множители, они кратко рассматриваются ниже.

Значения x, y и p в примере 12.33

x	y	p
2	2	1
5	26	1
26	23713	1
677	142292	1
23713	157099	1
345589	52128	1
142292	41831	1
380320	68775	1
157099	427553	1
369457	2634	1
52128	63593	1
102901	161353	1
41831	64890	1
64520	21979	1
68775	16309	709

Квадратичное решето

Померанс изобрел метод разложения на множители, называемый методом квадратичного решета. Метод применяет процедуру просеивания, чтобы найти значение x2mod n. Метод используется, чтобы разложить на множители целые числа с более чем 100 цифрами. Его сложность — 0 (ec), где $$C \approx 2{(\ln n\ln \ln n)^{1/2}}$$. Обратите внимание, что это – субпотенциальная сложность.

Решето поля чисел

Эндрик Ленстра и Арджин Ленстра изобрели метод разложения на множители и назвали его метод решета поля чисел. Метод использует процедуру просеивания в алгебраической кольцевой структуре к $${x^2} \equiv {y^2}\bmod n$$. Показано, что этот метод быстрее для разложения чисел с более чем 120 десятичными цифрами. Его сложность – O(eС) где $$C \approx {(\ln n)^{1/3}}{(\ln \ln n)^{2/3}}$$ . Обратите внимание, что это — также субпоказательная сложность.

Пример 12.34

Предположим, что есть компьютер, который может выполнить 230 (почти 1 миллиард) битовых операций в секунду. Какое приблизительно время требуется для этого компьютера, чтобы разложить на множители целое число из 100 десятичных цифр, используя один из следующих методов?

a. Метод квадратичного решета

b. Метод решета поля чисел

Решение

Номер с 100 десятичными цифрами имеет почти 300 битов (n = 2300).

ln (2300) = 207 и lnln (2300) = 5.

a. Для метода квадратичного решета мы имеем

$${\left( {207} \right)^{1/2}} \times {\left( 5 \right)^{1/2}} = 14 \times 2,23 = 32$$.

Это означает, что нам надо e32 битовых операций, которые могут быть сделаны в (e32)/ (230) = 20 часов.

b. При методе решета поля чисел мы имеем $$\left( {207} \right) \times {\left( 5 \right)^{2/2}} = 6 \times 3 \approx 18$$. Это означает, что нам надо e 18 битовых операций, которые могут быть сделаны за $$({e^{30}})/({2^{30}}) \approx 6$$ секунд. Однако эти результаты правильны, только если мы имеем компьютер, который может выполнить 1 миллиард битовых операций в секунду.

Другие проблемы

В лекциях 14-15 мы обсудим прикладные вопросы задачи разложения на множители для вскрытия криптосистем с открытым ключом. Если будут изобретены более эффективные методы разложения на множители, то криптосистемы с открытым ключом вынуждены будут использовать большие целые числа, чтобы противостоять криптоанализу. Изобретатели RSA создали основу для конкуренции методов разложения на множители номеров до 2048 битов (больше чем 600 цифр).

12.4. Китайская теорема об остатках

Китайская теорема об остатках (CRT — Chinese Reminder Theorem) используется, чтобы решить множество уравнений с одной переменной, но различными взаимно простыми модулями, как это показано ниже:

$$\tt\parindent0pt x \equiv a_{1} (mod\ m_{1}) x \equiv a_{2} (mod\ m_{2}) … x \equiv a_{k} (mod\ m_{k}) $$

Китайская теорема об остатках утверждает, что вышеупомянутые уравнения имеют единственное решение, если модули являются взаимно простыми.

Пример 12.35

Следующий пример содержит систему уравнений с различными модулями:

$$\tt\parindent0pt $x \equiv 2(mod\ 3)$ $x \equiv 3(mod\ 5)$ $x \equiv 2(mod\ 7)$ $$

Для этой системы уравнений x = 23. Это значение удовлетворяет все уравнения: $$23 \equiv 2\left( {\bmod 3} \right)$$, $$23 \equiv 3\left( {\bmod 5} \right) $$ , $$23 \equiv 2\left( {\bmod 7} \right)$$.

Решение

Решение системы уравнений выполняется в следующем порядке:

Найти $$M = {m_1} \times {m_2} \times \ldots \times {m_k}$$. Это общий модуль.

Найти M1 = M/m1, M2 = M/m2,…., Mk = M/mk.

Используя соответствующие модули m1, m2,…., mk, найти мультипликативную инверсию M1, M2,…, Mk. Обозначим ее M1-1, M2-1,…, Mk-1.

Решение системы уравнений

$$ x = (a_{1} \times M_{1} \times M_{1}^{-1} + a_{2} \times M_{2} \times M_{2}^{-1}+\dots+ a_{k} \times M_{k} \times M_{k}^{-1}) \mod\ M $$

Обратите внимание, что система уравнений может иметь решение, даже если модули не взаимно простые. Однако в криптографии мы интересуемся только решением уравнений с взаимно простыми модулями.

Пример 12.36

Найдите решение системы уравнений

$$\tt\parindent0pt $x \equiv 2(mod\ 3)$ $x \equiv 3(mod\ 5)$ $x \equiv 2(mod\ 7)$ $$

Из предыдущего примера мы уже знаем, что ответ x = 23. Определим его в четыре шага.

Решение

$$M = 3 \times 5 \times 7 = 105$$

M1 = 105/3 = 35, M2 = 105/5 =21, M3 = 105/7 = 15

Инверсии M1-1 = 2, M2-1 = 1, M3-1 = 1

$$x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 23\bmod 105$$

Пример 12.37

Найти целое, которое дает в остатке 3, если его разделить на 7 и 13, но без остатка делится на 12.

Решение

Это проблема китайской теоремы об остатке. Мы можем составить три уравнения и найти значение x.

$$\tt\parindent0pt $x \equiv 3(mod\ 7)$ $x \equiv 3(mod\ 13)$ $x \equiv 0(mod\ 12)$ $$

Если проведем четыре шага, мы найдем x = 276. Можем проверить, что 276 = 3 mod 7, 276 = 3 mod 13 и 276 делится на 12 (частное 23 и остаток 0).

Приложения

Китайская теорема об остатках часто применяется в криптографии. Одно из таких применений – решение квадратных уравнений — будет обсуждаться в следующей секции. Другое приложение — представление очень большого числа в виде списка малых целых чисел.

Пример 12.38

Предположим, нам надо вычислить z = x + y, где x = 123 и y = 334, но система принимает только числа меньше 100. Эти числа можно представить следующими уравнениями:

$$\tt\parindent0pt $x \equiv 24(mod\ 99) \ \ \ y \equiv 37(mod\ 99)\ \ \ x \equiv 25(mod\ 98)$ $y \equiv 40(mod\ 98)\ \ \ x \equiv 26(mod\ 97) \ \ \ y \equiv 43(mod\ 97)$ $$

Сложим каждое уравнение x с соответствующим уравнением y:

$$\tt\parindent0pt $x + y \equiv 61(mod\ 99) \to z \equiv 61(mod\ 99)x + y \equiv 65(mod\ 98) \to$ $z \equiv 65(mod\ 98)x + y \equiv 69(mod\ 97) \to z \equiv 69(mod\ 97)$ $$

Теперь эти три уравнения могут быть решены, используя китайскую теорему об остатках, чтобы найти z. Один из приемлемых ответов равен z = 457.