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

История

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

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

Если натуральные числа ${\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}}$ , а также их произведение.

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

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

${\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}}}$ , причем справедлива формула :

${\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 -е равенство в системе : ${\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}}$ . Противоречие

Замечания

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

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

верны также

${\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 — длина восстанавливаемого числа в битах .

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

Приведём ниже алгоритмы решения задачи, которая ставится в теореме — восстановление числа ${\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}$ .

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

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

Шаг 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}}$ однозначно представимо в виде

${\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\}}$ мы сможем подставить их в формулу и найти искомое решение :

Обозначим через ${\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}}$ .

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

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

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

Пусть ${\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}},}$ отображение корректно.

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

Применения

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

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

Примечания

Литература

• — М. : МЦНМО , 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.
• / Инютин С. А. // Меотская археологическая культура — Монголо-татарское нашествие. — М. : Большая российская энциклопедия, 2012. — ( Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов ; 2004—2017, т. 20). — ISBN 978-5-85270-354-5 .
• Нестеренко А. . — 2011. — 190 с.
• Осипов, Н. Н. (2008)
• Смарт Н. . — 2005. — 528 с.
• Сонг Й. Ян. . — М. , Ижевск: «Регулярная и хаотическая динамика», «Институт компьютерных исследований», 2011. — 312 с. — ISBN 978-5-93972-873-7 .
• Фергюсон, Нильс ; Шнайер, Брюс . . — М. : Вильямс, 2004. — 432 с.
• Финько О. А. : Монография — М. : ИПУ РАН , 2003. — 214 с.
• Hazewinkel, Michiel, ed. (2001), , Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4
• , (англ.) // / — IEEE , 1983. — Vol. 29, Iss. 2. — P. 208—210. — ISSN ; —
• (англ.) // : Proceedings of the Workshop on Cryptography Burg Feuerstein, Germany, March 29–April 2, 1982 / — Berlin, Heidelberg, New York City, London: , 1983. — P. 371—375. — ( ; Vol. 149) — ISBN 978-3-540-11993-7 — ISSN ; —

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• от 31 марта 2018 на Wayback Machine