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

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

Исходная формулировка Сунь Цзы: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) с решением x = 23 + 105k где k ∈ ℤ

История

Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (кит. упр. 孙子算经, пиньинь sunzi suanjing), предположительно датируемом III веком н. э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах», датируемой 1247 годом, где было приведено точное решение^[1].

Формулировка

Если натуральные числа ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ попарно взаимно просты, то для любых целых ${\displaystyle r_{1},r_{2},\dots ,r_{n}}$ таких, что ${\displaystyle 0\leqslant r_{i}<a_{i}}$ при всех ${\displaystyle i\in \{1,2,\dots ,n\},}$ найдётся число ${\displaystyle N}$, которое при делении на ${\displaystyle a_{i}}$ даёт остаток ${\displaystyle r_{i}}$ при всех ${\displaystyle i\in \{1,2,\dots ,n\}}$. Более того, если найдутся два таких числа ${\displaystyle N_{1}}$ и ${\displaystyle N_{2}}$ (соответствующих утверждению выше), то ${\displaystyle N_{1}\equiv N_{2}{\pmod {a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}}$.

Доказательства

Индукция по числу уравнений

Воспользуемся методом математической индукции. При ${\displaystyle n=1}$ утверждение теоремы очевидно. Пусть теорема справедлива при ${\displaystyle n=k-1}$, тогда существует число ${\displaystyle m}$, дающее остаток ${\displaystyle r_{i}}$ при делении на ${\displaystyle a_{i}}$ при ${\displaystyle i\in \{1,2,\dots ,k-1\}}$. Обозначим

${\displaystyle d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}}$.

Выберем произвольное число ${\displaystyle a_{k}}$, взаимно простое со всеми ${\displaystyle a_{1}\dots a_{k-1}}$ и рассмотрим числа ${\displaystyle M=\{m,m+d,m+2d,\dots ,m+(a_{k}-1)\cdot d\}=\{m+t\cdot d\}_{0\leqslant t<a_{k}}}$. Покажем, что все ${\displaystyle t\in \{0,\dots ,a_{k}-1\}}$ являются остатками при делении каких-либо элементов из ${\displaystyle M}$ на ${\displaystyle a_{k}}$.

Допустим это не так, то есть существует некоторое ${\displaystyle r_{k}<a_{k}}$, которое не принадлежит множеству всех остатков при делении элементов ${\displaystyle M}$ на ${\displaystyle a_{k}}$. Поскольку количество этих элементов равно ${\displaystyle |M|=a_{k}}$, а возможных остатков при делении элементов из ${\displaystyle M}$ на ${\displaystyle a_{k}}$ может быть не более чем ${\displaystyle a_{k}-1}$ (ведь ни одно число не даёт остаток ${\displaystyle r_{k}}$), то среди них найдутся два числа, имеющих равные остатки (по принципу Дирихле). Пусть это числа ${\displaystyle m+t_{1}d}$ и ${\displaystyle m+t_{2}d}$ при ${\displaystyle t_{1}\neq t_{2}}$. Тогда их разность ${\displaystyle (m+t_{1}d)-(m+t_{2}d)=(t_{1}-t_{2})d}$ делится на ${\displaystyle a_{k}}$, что невозможно, так как ${\displaystyle t_{1}<a_{k}}$, ${\displaystyle t_{2}<a_{k}}$, ${\displaystyle 0<|t_{1}-t_{2}|<a_{k}}$ и ${\displaystyle d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}}$ взаимно просто с ${\displaystyle a_{k}}$, так как числа ${\displaystyle a_{1},a_{2},\dots ,a_{k}}$ попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число ${\displaystyle N=m+t\cdot d}$, которое при делении на ${\displaystyle a_{k}}$ даёт остаток ${\displaystyle r_{k}}$. В то же время при делении на ${\displaystyle a_{1},a_{2},\dots ,a_{k-1}}$ число ${\displaystyle N}$ даёт остатки ${\displaystyle r_{1},r_{2},\dots ,r_{k-1}}$ соответственно, так как ${\displaystyle m+t\cdot d\equiv m{\pmod {a_{i}}}}$.

Докажем теперь, что ${\displaystyle N_{1}\equiv N_{2}{\pmod {a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}}$. В самом деле ${\displaystyle N_{1}\equiv N_{2}\equiv r_{i}{\pmod {a_{i}}}}$, то есть ${\displaystyle N_{1}-N_{2}\equiv 0{\pmod {a_{i}}}}$. Таким образом, число ${\displaystyle N_{1}-N_{2}}$ делится без остатка на все ${\displaystyle a_{i}}$, а также их произведение.

Конструктивный метод доказательства

Описанное ниже доказательство теоремы помогает решить практически важную задачу — поиск решения системы линейных сравнений по модулю^[2]. Рассмотрим систему уравнений:

${\displaystyle {\begin{cases}x\equiv r_{1}{\pmod {a_{1}}},\\x\equiv r_{2}{\pmod {a_{2}}},\\\cdots \cdots \cdots \cdots \cdots \cdots \\x\equiv r_{n}{\pmod {a_{n}}}.\\\end{cases}}}$

(1)

Если наборы ${\displaystyle (r_{1},r_{2},\dots ,r_{n})}$ и ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$ удовлетворяют условию теоремы, то решение системы (1) существует и единственно с точностью до операции взятия по модулю ${\displaystyle M}$, где ${\displaystyle M={\displaystyle \prod _{i=1}^{n}a_{i}}}$, причем справедлива формула^[2][3][4]:

${\displaystyle x=\sum _{i=1}^{n}r_{i}M_{i}M_{i}^{-1}}$, где ${\displaystyle M_{i}={\frac {M}{a_{i}}}}$, а ${\displaystyle M_{i}^{-1}}$ — мультипликативно обратный к ${\displaystyle M_{i}{\bmod {a}}_{i}}$ элемент в кольце ${\displaystyle \mathbb {Z} _{a_{i}}}$.

(2)

Покажем, что определённый таким образом ${\displaystyle x}$ является решением — проверим, что для него выполняется i-е равенство в системе^[3]: ${\displaystyle x\equiv \sum _{j=1}^{n}r_{j}M_{j}M_{j}^{-1}\equiv r_{i}M_{i}M_{i}^{-1}\equiv r_{i}{\pmod {a_{i}}}}$ Второе равенство справедливо так как ${\displaystyle M_{j}\equiv {\displaystyle \prod _{k\neq j}^{n}a_{k}}\equiv 0{\pmod {a_{i}}}}$ при всех ${\displaystyle i\neq j}$, третье так как ${\displaystyle M_{i}^{-1}}$ является обратным для ${\displaystyle M_{i}}$ по модулю ${\displaystyle a_{i}}$. Повторяя рассуждения для всех ${\displaystyle i}$, убедимся, что ${\displaystyle x}$, определённый формулой (2), является решением для (1).

В силу выбранного числа ${\displaystyle M}$ все числа ${\displaystyle x'\equiv x{\pmod {M}}}$ будут удовлетворять системе.

Покажем теперь, что среди чисел ${\displaystyle 0,1,\dots ,M-1}$ (множество ${\displaystyle A}$) не найдется другого решения, кроме найденного нами ранее. Проведём доказательство этого факта от противного. Предположим, что получилось найти хотя бы два решения ${\displaystyle x_{1},x_{2}\in A}$ для некоторого набора остатков ${\displaystyle r}$. Так как множество ${\displaystyle B}$ всех допустимых наборов ${\displaystyle (r_{1},r_{2},\dots ,r_{n})}$ является равномощным множеству ${\displaystyle A}$, то для ${\displaystyle {\overline {A}}_{x}:=A\setminus \{x_{1},x_{2}\}}$ и ${\displaystyle {\overline {B}}_{r}:=B\setminus \{r\}}$ выполнено ${\displaystyle |{\overline {A}}_{x}|<|{\overline {B}}_{r}|}$. Однако по доказанному ранее, для любого набора из ${\displaystyle {\overline {B}}_{r}}$ существует решение из ${\displaystyle {\overline {A}}_{x}}$, следовательно, по принципу Дирихле, найдутся как минимум 2 набора остатков, которым соответствует одно и то же ${\displaystyle x\in A}$. Для такого ${\displaystyle x}$ найдется ${\displaystyle a_{i}}$ такое, что ${\displaystyle x\equiv r_{1},x\equiv r_{2}{\pmod {a_{i}}}}$ и ${\displaystyle r_{1}\neq r_{2}}$. Противоречие^[5]

Замечания

Из доказанного выше следует, что существует взаимно однозначное соответствие между вектором остатков из ${\displaystyle B}$ и числом из множества ${\displaystyle A}$ для любого набора ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$, т.е. отображение ${\displaystyle B}$ в ${\displaystyle A}$, заданное (2), является биективным^[5]. Заметим, что кроме соответствия

${\displaystyle (x{\pmod {M}})\leftrightarrow (r_{1}{\pmod {a_{1}}},r_{2}{\pmod {a_{2}}},\dots ,r_{n}{\pmod {a_{n}}}),}$

верны также^[6][7]

${\displaystyle (x_{1}\pm x_{2}{\pmod {M}})\leftrightarrow (r_{11}\pm r_{21}{\pmod {a_{1}}},r_{12}\pm r_{22}{\pmod {a_{2}}},\dots ,r_{1n}\pm r_{2n}{\pmod {a_{n}}})}$,

${\displaystyle (x_{1}x_{2}{\pmod {M}})\leftrightarrow (r_{11}r_{21}{\pmod {a_{1}}},r_{12}r_{22}{\pmod {a_{2}}},\dots ,r_{1n}r_{2n}{\pmod {a_{n}}})}$.

Вычислительная сложность перехода от вектора остатков к числу оценивается как ${\displaystyle O(k^{2})}$, где k — длина восстанавливаемого числа в битах^[3].

Алгоритмы поиска решений

Приведём ниже алгоритмы решения задачи, которая ставится в теореме — восстановление числа ${\displaystyle x}$ по набору его остатков от деления на некоторые заданные взаимно простые числа ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$.

Элементарная алгебра

Как пример рассмотрим систему:

${\displaystyle {\begin{cases}x\equiv 1{\pmod {2}},\\x\equiv 2{\pmod {3}},\\x\equiv 6{\pmod {7}}.\\\end{cases}}}$

Для решения системы выпишем отдельно решения первого, второго и третьего уравнений (достаточно выписать решения не превосходящие ${\displaystyle 2\cdot 7\cdot 3=42}$):

${\displaystyle x_{1}\in \{1,3,5,7,9,11,\dots ,39,\mathbf {41} ,43,\dots \},}$

${\displaystyle x_{2}\in \{2,5,8,11,14,\dots ,38,\mathbf {41} ,44,\dots \},}$

${\displaystyle x_{3}\in \{6,13,20,27,34,\mathbf {41} ,48,\dots \}.}$

Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю 42. В нашем случае ${\displaystyle x\in \{41,83,125,\dots \}}$ или ${\displaystyle x\equiv 41{\pmod {42}}.}$

Для того, чтобы продемонстрировать другой путь, переформулируем задачу. Найдем тройку чисел ${\displaystyle (u,v,w)}$ таких, что:

${\displaystyle {\begin{cases}x=1+2u,\\x=2+3v,\\x=6+7w.\\\end{cases}}}$

Подставив ${\displaystyle x}$ из первого уравнения во второе, получим ${\displaystyle 1+2u\equiv 2{\pmod {3}}}$, тогда ${\displaystyle 2u\equiv 1{\pmod {3}}}$, или ${\displaystyle 4u\equiv 2{\pmod {3}}}$, или ${\displaystyle u\equiv 2{\pmod {3}}}$, или ${\displaystyle u=2+3s}$;

подставив затем ${\displaystyle x}$ из первого уравнения в третье с учетом выражения для ${\displaystyle u}$ получим ${\displaystyle 1+2(2+3s)\equiv 6{\pmod {7}}}$ или ${\displaystyle 6s\equiv 1{\pmod {7}}}$, тогда ${\displaystyle 36s\equiv 6{\pmod {7}}}$ и следовательно ${\displaystyle s\equiv 6{\pmod {7}}}$;

тогда ${\displaystyle x=1+2(2+3\cdot 6)=41}$.

Алгоритм на основе китайской теоремы об остатках

Алгоритм сводится к поиску решений по формуле, данной в теореме^[8].

Шаг 1. Вычисляем ${\displaystyle M={\displaystyle \prod _{i=1}^{n}a_{i}}}$.

Шаг 2. Для всех ${\displaystyle i\in \{1,2,\dots ,n\}}$ находим ${\displaystyle M_{i}={\frac {M}{a_{i}}}}$.

Шаг 3. Находим ${\displaystyle M_{i}^{-1}\equiv {\frac {1}{M_{i}}}{\bmod {a_{i}}}}$ (например, используя расширенный алгоритм Евклида).

Шаг 4. Вычисляем искомое значение по формуле ${\displaystyle x\equiv \sum _{i=1}^{n}r_{i}M_{i}M_{i}^{-1}\mod M}$.

Алгоритм Гарнера

Рассмотрим набор модулей ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$, удовлетворяющих условию теоремы. Другой теоремой из теории чисел утверждается, что любое число ${\displaystyle 0\leqslant x<M=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}$ однозначно представимо в виде^[9]

${\displaystyle x=x_{1}+x_{2}\cdot a_{1}+x_{3}\cdot a_{1}\cdot a_{2}+\dots +x_{n}\cdot a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n-1}}$.

Вычислив по порядку все коэффициенты ${\displaystyle x_{i}}$ для ${\displaystyle i\in \{1,2,\dots ,n\}}$ мы сможем подставить их в формулу и найти искомое решение^[10]:

Обозначим через ${\displaystyle r_{ij}=a_{i}^{-1}{\bmod {a_{j}}}}$ и рассмотрим выражение для ${\displaystyle x}$ по модулю ${\displaystyle a_{i}}$, где ${\displaystyle i\in \{2,\dots ,n\}}$, получим:

${\displaystyle x_{1}=r_{1}}$;

${\displaystyle r_{2}=(x_{1}+x_{2}a_{1}){\bmod {a_{2}}}}$;

${\displaystyle x_{2}=(r_{2}-x_{1})r_{12}{\bmod {a_{2}}}}$;

${\displaystyle r_{3}=(x_{1}+x_{2}a_{1}+x_{3}a_{1}a_{2}){\bmod {a_{3}}}}$;

${\displaystyle x_{3}=((r_{3}-x_{1})r_{13}-x_{2})r_{23}{\bmod {a_{3}}}}$

и так далее.

Сложность вычисления коэффициентов ${\displaystyle x_{i}}$ для данного алгоритма ${\displaystyle O(n^{2})}$. Такая же сложность и восстановления искомого числа по найденным коэффициентам.

Вариации и обобщения

Формулировка для колец

Пусть ${\displaystyle A,B_{1},\dots ,B_{n}}$ — коммутативные кольца с единицей, ${\displaystyle \varphi _{i}\colon A\to B_{i}}$ — сюръективные гомоморфизмы, обладающие свойством ${\displaystyle \ker \varphi _{i}+\ker \varphi _{j}=A}$ для всех ${\displaystyle i,j\in \{1,\dots ,n\},i\neq j}$. Тогда гомоморфизм

${\displaystyle \Phi \colon A\to \prod _{i=1}^{n}B_{i}}$,

заданный формулой

${\displaystyle \Phi (a)=(\varphi _{1}(a),\dots ,\varphi _{n}(a))}$,

является сюръективным. Более того, ${\displaystyle \Phi }$ определяет изоморфизм

${\displaystyle A/\left(\bigcap _{i=1}^{n}\ker \varphi _{i}\right)\cong \prod _{i=1}^{n}B_{i}}$.

Если положить ${\displaystyle A=\mathbb {Z} /(a_{1}\cdot \ldots \cdot a_{n}\mathbb {Z} ),B_{i}=\mathbb {Z} /a_{i}\mathbb {Z} \ (i=1,2,\dots ,n;\ a_{i}\in \mathbb {Z} )}$ и определить гомоморфизмы следующим образом

${\displaystyle \varphi _{i}(x)=x\,{\bmod {\,a_{i}}}}$,

то мы получим арифметическую версию теоремы.

Также часто встречается эквивалентная формулировка для колец, где ${\displaystyle B_{i}}$ имеют форму ${\displaystyle A/I_{i}}$ для некоторого набора идеалов ${\displaystyle I_{1},\dots ,I_{n}}$, гомоморфизмы ${\displaystyle \varphi _{i}}$ являются естественными проекциями на ${\displaystyle A/I_{i}}$ и требуется, чтобы ${\displaystyle I_{i}+I_{j}=A}$ для любых ${\displaystyle i,j\in \{1,\dots ,n\},i\neq j}$. Другими словами, если идеалы ${\displaystyle I_{1},\dots ,I_{n}}$ попарно взаимно просты (то есть сумма двух различных идеалов равна самому кольцу), то их произведение совпадает с их пересечением, и факторкольцо по этому произведению изоморфно произведению факторов:

${\displaystyle A/(I_{1}I_{2}\ldots I_{n})\cong A/I_{1}\times A/I_{2}\times \ldots \times A/I_{n}}$.

Кроме того существует обобщение на некоммутативные кольца без единиц с дополнительным условием, автоматически выполняющимся на кольцах с единицами.^[11]

Также известно обобщение на решётки и коммутативные идемпотентные полукольца.^[12]

Доказательство для евклидовых колец

Пусть ${\displaystyle R}$ — евклидово кольцо и ${\displaystyle m,n}$ — взаимно простые числа. Тогда докажем, что существует корректно заданный изоморфизм:

${\displaystyle R/_{(mn)}\cong R/_{(m)}\times R/_{(n)}}$

Прямое отображение ${\displaystyle [x]_{mn}\longrightarrow ([x]_{m},\ [x]_{n})}$ очевидно.

Для доказательства существования обратного отображения рассмотрим классы эквивалентности ${\displaystyle [1]}$ и ${\displaystyle [0]}$:

${\displaystyle ([1]_{m},\ [0]_{n})\longrightarrow [u]_{mn}}$,

${\displaystyle ([0]_{m},\ [1]_{n})\longrightarrow [v]_{mn}}$.

Найдём ${\displaystyle [u]_{mn}}$, решив следующую систему уравнений:

${\displaystyle {\begin{cases}u\equiv 1\ {\pmod {m}}\\u\equiv 0\ {\pmod {n}}\end{cases}}}$

${\displaystyle \exists y\in \mathbb {Z}$ :\ u=ny,\ ny\equiv 1{\pmod {m}}}

Аналогично найдём ${\displaystyle [v]_{mn}}$:

${\displaystyle \exists x\in \mathbb {Z}$ :\ v=mx,\ mx\equiv 1{\pmod {n}}}

Покажем, что в общем виде выполняется:

${\displaystyle ([a]_{m},\ [b]_{n})\longrightarrow [au+bv]_{mn},}$

${\displaystyle au+bv\equiv a{\pmod {m}}}$, так как ${\displaystyle v\equiv 0{\pmod {m}}}$ и ${\displaystyle u\equiv 1{\pmod {m}},}$

${\displaystyle au+bv\equiv b{\pmod {n}}}$, так как ${\displaystyle u\equiv 0{\pmod {n}}}$ и ${\displaystyle v\equiv 1{\pmod {n}}.}$

Проверим корректность отображения, то есть что при взятии разных элементов из классов ${\displaystyle [a]_{m},\ [b]_{n}}$ результат не меняется:

${\displaystyle {\begin{cases}a\equiv a'{\pmod {m}},\\b\equiv b'{\pmod {n}}.\end{cases}}}$

Значит ${\displaystyle au+bv\equiv a'u+b'v{\pmod {mn}},}$ отображение корректно.

Можно проверить, что построенное отображение действительно обратное .

Применения

Китайская теорема об остатках широко применяется в теории чисел, криптографии и других дисциплинах.

• Взаимно однозначное соответствие между некоторым числом и набором его остатков, определяемым набором взаимно простых чисел, существование которого утверждается в теореме, на практике помогает работать не с длинными числами, а с наборами их коротких по длине остатков. Кроме того, вычисления по каждому из модулей можно выполнять параллельно^[13]. Если в качестве базиса взять, к примеру, первые 500 простых чисел, длина каждого из которых не превосходит 12 битов, то этого хватит для представления чисел длиной до 1519 десятичных знаков (сумма десятичных логарифмов первых 500 простых чисел равна 1519,746…). Например, в алгоритме RSA вычисления производятся по модулю большого числа n, представимого в виде произведения двух больших простых чисел. Теорема позволяет перейти к вычислениям по модулю этих простых делителей, которые по величине уже порядка корня из n, а значит имеют в два раза меньшую битовую длину^[14]. Отметим также, что применение вычислений согласно китайской теореме об остатках делает алгоритм RSA восприимчивым к атакам по времени^[15].
• Такое представление числа под названием системы остаточных классов использовалось в ранних ЭВМ, особенно специализированных, т. к. позволяло выполнять арифметические операции над числами с большим числом битов путем параллельного вычисления операций над остатками. Так как модули можно было взять с небольшим числом битов, то таблицы операций над остатками по каждому модулю можно было просто запомнить в ПЗУ, как таблицу Пифагора, что позволяло производить арифметическую операцию практически за один такт.
• На Теореме основаны схема Асмута — Блума и схема Миньотта — пороговые схемы разделения секрета в группе участников. Секрет могут узнать только k из n участников, объединив свои ключи^[16][17].
• Одним из применений является быстрое преобразование Фурье на основе простых чисел^[18].
• Теорема лежит в основе принципа Хассе поиска целочисленных корней уравнения^[19].
• Теорема может быть использована при доказательстве свойства мультипликативности функции Эйлера^{[источник не указан 1692 дня]}.
• На Теореме основывается алгоритм Полига — Хеллмана нахождения дискретного логарифма за полиномиальное время для чисел, имеющих специальный вид^[20].
• Теорема имеет множество применений в шифровании и дешифровании в криптографических системах, например, в криптосистеме Рабина или в шифре Виженера^[21].
• Реализация функций алгебры логики числовыми методами^[22].

Примечания

1. Ишмухаметов, 2011, p. 36.
2. Нестеренко, 2011, p. 19.
3. Габидулин, Кшевецкий, Колыбельников, 2011, p. 229.
4. Осипов Н. Н., 2008, p. 80.
5. Осипов Н. Н., 2008, p. 19.
6. Габидулин, Кшевецкий, Колыбельников, 2011, p. 230.
7. Фергюсон, Нильс, Шнаер, Брюс, 2004, p. 249.
8. Нестеренко, 2011, p. 20.
9. Нестеренко, 2011, Теорема 2.4, p. 21.
10. Нестеренко, 2011, p. 22.
11. Некоммутативный случай без единицы  (неопр.). Дата обращения: 18 апреля 2018. Архивировано 19 апреля 2018 года.
12. Обобщение на решётки  (неопр.). Дата обращения: 18 апреля 2018. Архивировано 19 апреля 2018 года.
13. Инютин, 2012.
14. Фергюсон, Нильс, Шнаер, Брюс, 2004, p. 250.
15. Ян Сонг Й, 2011, 8.4.
16. Mignotte, 1982.
17. Asmuth, Bloom, 1983.
18. R. Tolimieri. FFT Algorithms Архивная копия от 17 декабря 2013 на Wayback Machine.
19. Otmar Venjakob p-adic Numbers and the Hasse Principle Архивная копия от 2 февраля 2017 на Wayback Machine.
20. Василенко, 2003, с. 130—131.
21. Минеев, Чубариков, 2010.
22. Финько, 2003, p. 19, 117.

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2
• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
• Гольденберг А.И. Задача остатков (рус.) // В.О.Ф.Э.М.. — 1887. — № 35. — С. 247—253.
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие — Казань: Казанский университет, 2011. — 190 с.
• Ленг, Серж. Алгебра. — М.: Мир, 1968. — С. 82—83.
• Минеев М. П., Чубариков В. Н. Об одном применении китайской теоремы об остатках к шифру Виженера. М.: ДАН. — 2010. — Том: 430. — №1. — С. 21, 22.
• Модулярная арифметика : [арх. 3 декабря 2022] / Инютин С. А. // Меотская археологическая культура — Монголо-татарское нашествие. — М. : Большая российская энциклопедия, 2012. — (Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов ; 2004—2017, т. 20). — ISBN 978-5-85270-354-5.
• Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.
• Осипов, Н. Н. Теория чисел (2008)
• Смарт Н. Криптография. — 2005. — 528 с.
• Сонг Й. Ян. Криптоанализ RSA. — М., Ижевск: «Регулярная и хаотическая динамика», «Институт компьютерных исследований», 2011. — 312 с. — ISBN 978-5-93972-873-7.
• Фергюсон, Нильс; Шнайер, Брюс. Практическая криптография. — М.: Вильямс, 2004. — 432 с.
• Финько О. А. Модулярная арифметика параллельных логических вычислений: Монография — М.: ИПУ РАН, 2003. — 214 с.
• Hazewinkel, Michiel, ed. (2001), "Chinese remainder theorem", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Asmuth C., Bloom J. A modular approach to key safeguarding (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1983. — Vol. 29, Iss. 2. — P. 208—210. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1983.1056651
• Mignotte M. How to Share a Secret (англ.) // Cryptography: Proceedings of the Workshop on Cryptography Burg Feuerstein, Germany, March 29–April 2, 1982 / T. Beth — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 1983. — P. 371—375. — (Lecture Notes in Computer Science; Vol. 149) — ISBN 978-3-540-11993-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-39466-4_27

Ссылки

• Weisstein, Eric W. Chinese Remainder Theorem (англ.) на сайте Wolfram MathWorld.
• Chinese Remainder Theorem на Planetmath.org Архивная копия от 31 марта 2018 на Wayback Machine