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

редактировать

Теорема для решений совместных сравнений

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

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

Самое раннее известное утверждение теоремы сделано китайским математиком Сунь-цзы в Сунь-цзы Суань-цзы в 3 веке нашей эры.

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

Китайская теорема об остатках (выраженная в терминах сравнений ) верна для каждой области главных идеалов. Он был обобщен на любое коммутативное кольцо с формулировкой, включающей идеалы.

Содержание

1 История
2 Утверждение
3 Доказательство
- 3.1 Уникальность
- 3.2 Существование (первое доказательство)
- 3.3 Существование (конструктивное доказательство)
  - 3.3.1 Примеры двух модулей
  - 3.3.2 Общий случай
- 3.4 Существование (прямое построение)
4 Вычисление
- 4.1 Систематический поиск
- 4.2 Поиск путем просеивания
- 4.3 Использование конструкции существования
- 4.4 Как линейная диофантова система
5 По кольцам одномерных многочленов и евклидовым областям
- 6.1 Интерполяция Лагранжа
- 6.2 Интерполяция Эрмита
7 Обобщение на непростые модули
8 Обобщение на произвольные кольца
9 Приложения
- 9.1 Нумерация последовательностей
- 9.2 Быстрое преобразование Фурье
- 9.3 Шифрование
- 9.4 Разрешение неоднозначности диапазона <
- 9.5 Теорема Дедекинда
10 См. Также
11 Примечания
12 Ссылки
13 Дополнительная литература
14 Внешние ссылки

История

Т Самое раннее известное утверждение теоремы как проблема с конкретными числами появляется в книге 3-го века Сунь-цзы Суань-цзин китайского математика Сунь-цзы:

Есть верх вещи, которые номер неизвестен. Если мы посчитаем их по три, у нас останется два; к пятеркам у нас остается три; а к семеркам осталось два. Сколько всего существует?

Работа Сунь-цзы не содержит ни доказательства, ни полного алгоритма. Что представляет собой алгоритм решения этой проблемы, описал Арьябхата (6 век). Особые случаи китайской теоремы об остатках были также известны Брахмагупте (7 век) и фигурируют в Фибоначчи Liber Abaci (1202). Позже результат был обобщен в виде полного решения под названием Ta-yan-shu (大衍術) в Ch'in Chiu-shao в 1247 Математическом трактате в девяти разделах (數書九章, Шу-шу Чиу-чан), который был переведен на английский язык в начале 19 века британским миссионером Александром Вайли.

Китайская теорема об остатках появляется в книге Гаусса 1801 года Disquisitiones Arithmeticae.

Понятие конгруэнций было введено впервые и использовано Гауссом в его Disquisitiones Arithmeticae 1801 года. Гаусс показывает, что это остаток китайской теорему для задач, которые имеют определенные периоды по отношению к солнечному и лунному циклам и по римскому указанию. "Гаусс вводит решения, уже использовалась Эйлером., но на самом деле была древним методом, который появлялся несколько раз.

Утверждение

Пусть n 1,..., n k быть целыми числами больше 1, которые часто называют модулями или делителями. Обозначим через N произведение n i.

. Китайская теорема об остатках утверждает, что если n i являются попарно взаимно простыми, и если 1,..., a k - целые числа такие, что 0 ≤ a i< niдля каждого i, тогда существует одно и только одно целое число x, такое что 0 ≤ x Евклидово деление числа x на n i - это i для каждого i.

Это можно переформулировать следующее им образом в терминах конгруэнций : Если n i попарно взаимно просты, и если 1,..., a k - любые целые числа, тогда существуют такие целые числа x, что

x ≡ a 1 (mod n 1) ⋮ x ≡ ak (mod nk), {\ displaystyle {\ begin {выровнено} x \ Equiv a_ {1} {\ pmod {n_ {1}}} \\ \, \, \, \ vdots \\ x \ Equiv a_ {k} {\ pmod {n_ {k}}}, \ end {align}}}

{\ displaystyle {\ begin {align} x \ Equiv a_ {1} {\ pmod {n_ {1}}} \\ \, \, \, \ vdots \\ x \ Equiv a_ {k} {\ pmod {n_ {k}}}, \ end {align}}}

и любые два решения, скажем x 1 и x 2, конгруэнтны по модулю N, то есть x 1 ≡ x 2 (mod N).

В абстрактной алгебре теорема часто переформулируется следующим образом: если n i попарно взаимно просты, карта

x mod N ↦ (x mod n 1,…, х мод NK) {\ Displaystyle х {\ bmod {N}} \; \ mapsto \; (x {\ bmod {n}} _ {1}, \, \ ldots, \, x {\ bmod {n}} _ {k})}

{\ displaystyle x {\ bmod {N}} \; \ mapsto \; (x {\ bmod {n}} _ {1}, \, \ ldots, \, x {\ bmod {n}} _ {k})}

определить изоморфизм колец

Z / NZ ≅ Z / N 1 Z × ⋯ × Z / nk Z {\ displaystyle \ mathbb {Z} / N \ mathbb {Z} \ cong \ mathbb {Z} / n_ {1} \ mathbb {Z} \ times \ cdots \ раз \ mathbb {Z} / n_ {k} \ mathbb {Z}}

{\ displaystyle \ mathbb {Z} / N \ mathbb {Z} \ cong \ mathbb {Z} / n_ {1} \ mathbb {Z } \ times \ cdots \ times \ mathbb {Z} / n_ {k} \ mathbb {Z}}

между r ввод из целых чисел по модулю N и прямого произведения колец целых чисел по модулю n i. Это означает, что для выполнения арифметических операций в $Z / NZ, {\ displaystyle \ mathbb {Z} / N \ mathbb {Z},}$ ${\ displaystyle \ mathbb {Z} / N \ mathbb {Z},}$ можно выполнять одно и то же вычисление независимо в каждом $Z / ni Z {\ displaystyle \ mathbb {Z} / n_ {i} \ mathbb {Z}}$ ${\ displaystyle \ mathbb { Z} / n_ {i} \ mathbb {Z}}$ , а получить результат, применив изоморфизм (справа налево). Это может быть намного быстрее, чем прямое вычисление, если N и количество операций большое. Это широко используется под названием многомодульное вычисление для линейной алгебры над целыми числами или рациональными числами.

Теорема также может быть переформулирована на языке комбинаторики как тот факт, что бесконечные арифметические прогрессии целых чисел образуют Helly.

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

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

Уникальность

Предположим, что x и y являются решениями всех сравнений. Времена x и y дают одинаковые остатки, при делении на n i их разность x - y кратна каждому n i. Временем n i попарно взаимно просты, их произведение N делит также x - y, и, таким образом, x и y конгруэнтны по модулю N. Если x и y должны быть неотрицательными и меньше N (как в первом утверждении теоремы), то их разность может быть кратной N, только если x = y.

Существование (первое доказательство)

Карта

x mod N ↦ (x mod n 1,…, x mod nk) {\ displaystyle x {\ bmod {N}} \ mapsto (x {\ bmod {n}} _ {1}, \ ldots, x {\ bmod {n}} _ {k})}

{\ displaystyle x {\ bmod {N}} \ mapsto (x {\ bmod {n}} _ {1}, \ ldots, x {\ bmod {n}} _ {k})}

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

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

Существование (конструктивное доказательство)

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

Примеры двух модулей

Мы хотим решить систему:

x ≡ a 1 (mod n 1) x ≡ a 2 (mod n 2), {\ displaystyle {\ начало {выровнено } х \ эквив {1} {\ pmod {n_ {1}}} \\ х \ эквив {2} {\ pmod {п_ {2}}}, \ end {выровнено}}}

{\ displaystyle {\ begin {align} x \ Equiv a_ {1} {\ pmod {n_ {1}}} \\ x \ Equiv a_ {2} {\ pmod {n_ {2}}}, \ end {align}}}

где $n 1 {\ displaystyle n_ {1}}$ $n_ {1}$ и $n 2 {\ displaystyle n_ {2}}$ $n_ {2}$ взаимно просты.

Личность Безу подтверждение существования двух целых чисел $m 1 {\ displaystyle m_ {1}}$ $m_ {1}$ и $m 2 {\ displaystyle m_ {2}}$ $m_ {2}$ такое, что

m 1 n 1 + m 2 n 2 = 1. {\ displaystyle m_ {1} n_ {1} + m_ {2} n_ {2} = 1.}

{\ displaystyle m_ {1} n_ {1} + m_ {2} n_ {2} = 1.}

Целые числа $m 1 {\ displaystyle m_ {1}}$ $m_ {1}$ и $m 2 {\ displaystyle m_ {2}}$ $m_ {2}$ могут быть вычислены с помощью расширенного алгоритма Евклида.

Решение дается формулой

x = a 1 m 2 n 2 + a 2 m 1 n 1. {\ displaystyle x = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1}.}

{\ displaystyle x = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1}.}

Действительно,

x = a 1 m 2 n 2 + a 2 м 1 N 1 знак равно a 1 (1 - m 1 n 1) + a 2 m 1 n 1 = a 1 + (a 2 - a 1) m 1 n 1, {\ displaystyle {\ begin {align} x = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1 } \\ = a_ {1} (1-m_ {1} n_ {1}) + a_ {2} m_ {1} n_ {1} \\ = a_ {1} + (a_ {2} -a_ {1}) m_ {1} n_ {1}, \ end {align}}}

{\ displaystyle {\ begin {align} x = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1} \\ = a_ {1} (1-m_ {1} n_ {1}) + a_ {2} m_ {1} n_ {1} \\ = a_ {1} + (a_ {2} -a_ {1}) m_ {1} n_ {1}, \ end {align}}}

подразумевая, что $x ≡ a 1 (mod n 1). {\ displaystyle x \ Equiv a_ {1} {\ pmod {n_ {1}}}.}$ ${\ displaystyle x \ Equiv a_ {1} {\ pmod {n_ {1} }}.}$ Второе сравнение доказано аналогично, заменой индексов 1 и 2.

Общий случай

Рассмотрим последовательность соотношений сравнения:

x ≡ a 1 (mod n 1) ⋮ x ≡ ak (mod nk), {\ displaystyle {\ begin {align} x \ Equiv a_ {1} {\ pmod { n_ {1}}} \\ \ vdots \\ x \ Equiv a_ {k} {\ pmod {n_ {k}}}, \ end {align}}}

{\ displaystyle {\ begin {align} x \ Equiv a_ {1} {\ pmod {n_ {1}}} \\ \ vdots \\ x \ Equiv a_ {k} {\ pmod {n_ {k}}}, \ end {align}}}

где $ni {\ displaystyle n_ {i}}$ $n_ {i}$ попарно взаимно просты. Два первых уравнения имеют решение $a 1, 2 {\ displaystyle a_ {1,2}}$ ${\ displaystyle a_ {1,2}}$ , предоставленное методом из предыдущего раздела. Набор решений этих двух уравнений является набором всех решений уравнений

x ≡ a 1, 2 (mod n 1 n 2). {\ displaystyle x \ Equiv a_ {1,2} {\ pmod {n_ {1} n_ {2}}}.}

{\ displaystyle x \ Equiv a_ {1,2} {\ pmod {n_ {1} n_ {2}}}.}

Как и другие $ni {\ displaystyle n_ {i}}$ $n_ {i}$ n 1 n 2, {\ displaystyle n_ {1} n_ {2},} ${\ displaystyle n_ {1} n_ {2},}$ это сводит решение исходной задачи k уравнений взаимной задаче с $k - 1 { \ displaystyle k-1}$ $к-1$ уравнения. Итерируя этот процесс, в итоге можно получить решение исходной проблемы.

Существование (прямое построение)

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

Пусть $N i = N / n i {\ displaystyle N_ {i} = N / n_ {i}}$ ${\ displaystyle N_ {i} = N / n_ {i}}$ будет произведением всех модулей, кроме одного. <Времена 324>ni {\ displaystyle n_ {i}} $n_ {i}$ попарно взаимно просты, $N i {\ displaystyle N_ {i}}$ $N_ {i}$ и $ni {\ displaystyle n_ {i}}$ $n_ {i}$ взаимно просты. Таким образом, используется идентификатор Безу, и существуют целые числа $M i {\ displaystyle M_ {i}}$ $M_ {i }$ и $mi {\ displaystyle m_ {i}}$ $m_ {i}$ такой, что

M i N i + mini = 1. {\ displaystyle M_ {i} N_ {i} + m_ {i} n_ {i} = 1.}

{\ displaystyle M_ {i} N_ {i} + m_ {i} n_ {i} = 1.}

Решение системы сравнения :

x = ∑ i = 1 kai M i N i. {\ displaystyle x = \ sum _ {i = 1} ^ {k} a_ {i} M_ {i} N_ {i}.}

{\ displaystyle x = \ sum _ {i = 1} ^ {k} a_ {i} M_ {i} N_ {я}.}

Фактически, as $N j {\ displaystyle N_ {j}}$ $N_ {j}$ кратно $ni {\ displaystyle n_ {i}}$ $n_ {i}$ для $i ≠ j, {\ displaystyle i \ neq j,}$ ${\ displaystyle i \ neq j,}$ у нас есть

Икс ≡ ai M i N я ≡ ai (1 - mini) ≡ ai (mod ni), {\ displaystyle x \ Equiv a_ {i} M_ {i} N_ {i} \ Equiv a_ {i} ( 1-m_ {i} n_ {i}) \ Equiv a_ {i} {\ pmod {n_ {i}}},}

{\ displaystyle x \ Equiv a_ {i} M_ {i} N_ {i} \ Equiv a_ {i} (1-m_ {i} n_ {i}) \ Equiv a_ {i} {\ pmod {n_ {i}}},}

для каждого $i. {\ displaystyle i.}$ $i.$

Вычисление

Рассмотрим систему сравнений:

x ≡ a 1 (mod n 1) ⋮ x ≡ ak (mod nk), {\ displaystyle {\ begin {выровнено} x \ Equiv a_ {1} {\ pmod {n_ {1}}} \\ \ vdots \\ x \ Equiv a_ {k} {\ pmod {n_ {k}}}, \\\ end {выровнено }}}

{\ displaystyle {\ begin {align} x \ Equiv a_ {1} {\ pmod {n_ {1}}} \\ \ vdots \\ x \ Equiv a_ { k} {\ pmod {n_ {k}}}, \\\ конец {выровнено}}}

где $ni {\ displaystyle n_ {i}}$ $n_ {i}$ попарно взаимно просты, и пусть $N = n 1 n 2 ⋯ nk. {\ displaystyle N = n_ {1} n_ {2} \ cdots n_ {k}.}$ ${\ displaystyle N = n_ {1} n_ {2} \ cdots n_ {k}.}$ В этом разделе описываются несколько методов вычисления уникального решения для $x {\ displaystyle x}$ $x$ , такое что $0 ≤ x < N, {\displaystyle 0\leq x$ ${\ displaystyle 0 \ leq x <N,}$ , и эти методы применяются в примере:

x ≡ 0 (mod 3) x ≡ 3 (mod 4) x 4 (mod 5). {\ displaystyle {\ begin {align} x \ Equiv 0 {\ pmod {3}} \\ x \ Equiv 3 {\ pmod {4}} \\ x \ Equiv 4 {\ pmod {5}}. \ end {выровненный}}}

{\ displaystyle {\ begin {выровнено} x \ Equiv 0 {\ pmod {3}} \\ x \ Equiv 3 {\ pmod {4}} \\ x \ Equiv 4 {\ pmod {5}}. \ End {align}}}

Систематический поиск

Легко проверить, является ли значение x решением: достаточно вычислить остаток от евклидова деления x на каждом n я. Таким образом, чтобы найти решение, последовательно проверять целые числа от 0 до N, пока не будет найдено решение.

, несмотря на то, что этот метод очень неэффективен: в рассматриваемом здесь простом случае необходимо проверить 40 целых чисел (включая 0), чтобы найти решение, которое равно 39. Это экспоненциальное время, поскольку размер входных данных равен с точностью до постоянного множителя, количество цифр N, а среднее количество операций порядка N.

Следовательно, этот метод редко используется ни для рукописных вычислений, ни на компьютерах.

Поиск путем просеивания

Поиск может быть ускорен за счет просеивания. Для этого метода мы предполагаем, без ограничения общности, что $0 ≤ ai < n i {\displaystyle 0\leq a_{i}$ ${\ displaystyle 0 \ Leq a_ {i} <n_ {i}}$ (если бы это было достаточно заменить каждый $ai {\ displaystyle a_ {i}}$ $a_ {i}$ на остатки от деления на $ni {\ displaystyle n_ {i}}$ $n_ {i}$ ). Это означает, что решение принадлежит арифметической прогрессии

a 1, a 1 + n 1, a 1 + 2 n 1,… {\ displaystyle a_ {1}, a_ {1} + n_ {1}, a_ {1} + 2n_ {1}, \ ldots}

{\ displaystyle a_ {1}, a_ {1} + n_ {1}, a_ {1} + 2n_ {1}, \ ldots }

Проверяя значения этих чисел по модулю $n 2, {\ displaystyle n_ {2},}$ ${\ displaystyle n_ {2},}$ , в итоге можно найти решение $x 2 {\ displaystyle x_ {2}}$ $x_ {2}$ двух первых сравнений. Тогда решение принадлежит арифметической прогрессии

x 2, x 2 + n 1 n 2, x 2 + 2 n 1 n 2,… {\ displaystyle x_ {2}, x_ {2} + n_ {1} n_ {2}, x_ {2} + 2n_ {1} n_ {2}, \ ldots}

{\ displaystyle x_ {2}, x_ {2} + n_ {1} n_ { 2}, x_ {2} + 2n_ {1} n_ {2}, \ ldots}

Проверка значений этих чисел по модулю $n 3, {\ displaystyle n_ {3},}$ ${\ displaystyle n_ {3},}$ , и продолжение до тех пор, пока каждый модуль не будет проверен, дает окончательное решение.

Этот метод работает быстрее, если модули упорядочены по убыванию значений, то есть если $n 1>n 2>⋯>n k. {\ displaystyle n_ {1}>n_ {2}>\ cdots>n_ {k}.}$ $n_{1}>n_ {2}>\ cdots>n_ {k}.$ Для примера это дает следующее вычисление. 5 (наибольший модуль), которые равны 4, 9 = 4 + 5, 14 = 9 + 5,... Для каждого из них вычислите остаток по 4 (второй по величине модуль), пока не получите число сравнимо с 3 по модулю 4 Затем можно продолжить, добавляя 20 = 5 × 4 на каждом шаге и вычисляя только остатки по 3. Это дает

4 по модулю 4 → 0. Продолжить

4 + 5 = 9 по модулю 4 → 1. Продолжайте

9 + 5 = 14 по модулю 4 → 2. Продолжайте

14 + 5 = 19 по модулю 4 → 3. ОК, продолжайте, рассматривая остатки по модулю 3 и добавляя 5 × 4 = 20 каждый раз

19 mod 3 → 1. Продолжайте

19 + 20 = 39 mod 3 → 0. Хорошо, вот результат.

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

Использование конструкции существования

Конструктивное доказательство существования существования показывает, что в двух модулей решение может быть получено вычислением коэффициентов Безу модули, за которыми следуют несколько умножений, сложностей и редукций по модулю $n 1 n 2 {\ displaystyle n_ {1} n_ {2}}$ $n_ {1} n_ {2}$ (для достижения результата в интервале $(0, n 1 n 2-1) {\ displaystyle (0, n_ {1} n_ {2} -1)}$ ${\ displaystyle (0, n_ {1} n_ {2} -1)}$ ). Коэффициенты времени Безу могут быть вычислены с помощью расширенного алгоритма Евклида, полное вычисление, самое большее, имеет квадратичную временную сложность $O ((s 1 + s 2) 2), { \ displaystyle O ((s_ {1} + s_ {2}) ^ {2}),}$ ${\ Displaystyle O ((s_ {1} + s_ {2}) ^ {2}),}$ где $si {\ displaystyle s_ {i}}$ $s_ {i}$ обозначает количество цифр $нет. {\ displaystyle n_ {i}.}$ ${\ displaystyle n_ {i}.}$

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

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

В текущем примере (имеет только три модуля) обе стратегии идентичны и работают следующим образом.

Идентификатор Безу для 3 и 4 равенство

1 × 4 + (- 1) × 3 = 1. {\ displaystyle 1 \ times 4 + (- 1) \ times 3 = 1.}

{\ displaystyle 1 \ times 4 + (- 1) \ times 3 = 1.}

Если подставить это в формулу для доказательства существования, получим

4 × 0 + (- 3) × 3 = - 9 {\ displaystyle 4 \ times 0 + (- 3) \ times 3 = -9}

{\ displaystyle 4 \ times 0 + (- 3) \ times 3 = -9}

для решения двух первых сравнений, остальные решения получаются добавлением −9 любого кратного 3 × 4 = 12. Можно продолжить любое из решений, но решение 3 = −9 +12 меньше (в абсолютное значение) и, таким образом, упрощает вычисление.

Тождество Безу для 5 и 3 × 4 = 12 равно

5 × 5 + (- 2) × 12 = 1. {\ displaystyle 5 \ times 5 + (- 2) \ times 12 = 1.}

{\ displaystyle 5 \ times 5 + (- 2) \ times 12 = 1.}

Снова применяя ту же формулу, мы получаем решение задачи:

25 × 3 - 24 × 4 = - 21. {\ displaystyle 25 \ times 3-24 \ times 4 = -21.}

{\ displaystyle 25 \ times 3-24 \ times 4 = -21.}

Другие решения получаются путем сложения любого кратного 3 × 4 × 5 = 60, наименьшее положительное решение равно −21 + 60 = 39.

Как линейная диофантова система

Система c Онгруэнции, решаемые китайской теоремой об остатках, могут быть переписаны как система совместных линейных диофантовых уравнений :

x = a 1 + x 1 n 1 ⋮ x = ak + xknk, {\ displaystyle {\ begin {align} x = a_ {1} + x_ {1} n_ {1} \\ \ vdots \\ x = a_ {k} + x_ {k} n_ {k}, \ end {align}}}

{\ displaystyle {\ begin {align} x = a_ {1} + x_ {1} n_ {1} \\ \ vdots \\ х = а_ {к} + х_ {к} п_ {к}, \ конец {выровнено}}}

где неизвестно целыми числами являются $х {\ displaystyle x}$ $x$ и $xi. {\ displaystyle x_ {i}.}$ $x_ {i}.$ Следовательно, любой общий метод решения таких систем может быть использован для принятия решений китайской теоремы об остатках, например, уменьшение матрицы системы до Нормальная форма Смита или нормальная форма Эрмита. Однако, как обычно при использовании общего алгоритма для более конкретной проблемы, этот подход менее эффективен, чем метод из предыдущего раздела, основанный на прямом использовании тождества Безу.

в основных идеальных областях

В § Утверждение теоремы китайская теорема об остатках была сформулирована тремя различными способами: в терминах остатков, сравнений и изоморфизма колец. Утверждение в терминах остатков, как правило, не применяется к областям главных идеалов, поскольку остатки не устойчивых в таких кольцах. Однако две другие версии имеют смысл для основной идеальной области R: достаточно заменить «целое число» на «элемент области» и $Z {\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ на R. Эти две версии теоремы верны в данном контексте, доказательства (кроме первого существования) основы на лемме Евклида и тождество Безу, которые верны над каждым основным доменом.

Однако, в общем, теорема не предоставляет никаких методов решения, если у вас нет алгоритма вычисления коэффициентов тождества Безу.

Для одного колец многочленов и евклидовых областей

Утверждение в терминах остатков, приведенное в § Утверждение теоремы не может быть обобщено ни на какую область главных идеалов, но его обобщение на Евклидовы домены просты. Одномерные многочлены над полем являются типичным примером евклидовой области, не является целыми числами. Поэтому мы формулируем теорему для случая кольца одной области $R = K [X] {\ displaystyle R = K [X]}$ ${\ displaystyle R = K [X]}$ над полем $K. {\ displaystyle K.}$ $K.$ Чтобы получить теорему для общей евклидовой области, достаточно заменить степень евклидовой функции евклидовой области.

Китайская теорема об остатках для многочленов такова: Пусть $P i (X) {\ displaystyle P_ {i} (X)}$ ${\ displaystyle P_ {i} (X)}$ (модули) будут, для i = 1,..., k, попарно взаимно простые многочлены в $R = K [X] {\ displaystyle R = K [X]}$ ${\ displaystyle R = K [X]}$ . Пусть $di = deg ⁡ P i {\ displaystyle d_ {i} = \ deg P_ {i}}$ ${\ displaystyle d_ {i} = \ deg P_ {i}}$ будет степенью $P i (X) {\ displaystyle P_ {i} (X)}$ ${\ displaystyle P_ {i} (X)}$ и $D {\ displaystyle D}$ $D$ быть суммой $ди. {\ displaystyle d_ {i}.}$ ${\ displaystyle d_ {i}.}$ Если $A i (X),…, A k (X) {\ displaystyle A_ {i} (X), \ ldots, A_ {k} (X)}$ ${\ displaystyle A_ {i} ( X), \ ldots, A_ {k} (X)}$ - многочлены такие, что $A i (X) = 0 {\ displaystyle A_ {i} (X) = 0}$ ${\ displaystyle A_ {i} (X) = 0}$ или $deg ⁡ A i < d i {\displaystyle \deg A_{i}$ ${\ displaystyle \ deg A_ {i} <d_ {i}}$ для каждого i, тогда существует один и только один многочлен $P (X) {\ displaystyle P (X)}$ $P (X)$ , такой, что $deg ⁡ P < D {\displaystyle \deg P$ ${\ displaystyle \ deg P <D}$ и остаток от евклидова деления от $P (X) {\ displaystyle P (X)}$ $P (X)$ на $P i (X) {\ displaystyle P_ {i} ( X)}$ ${\ displaystyle P_ {i} (X)}$ равно $A i (X) {\ displaystyle A_ {i} (X)}$ ${\ displaystyle A_ {i} (X)}$ для каждого i.

Построение решения может быть выполнено, как в § Существование (конструктивное доказательство) или § Существование (прямое доказательство). Однако последнее построение можно упростить, используя, как показано ниже, разложение частичного дроби вместо расширенного алгоритма Евклида.

Таким образом, мы хотим найти многочлен $P (X) {\ Displaystyle P ( X)}$ $P (X)$ , который удовлетворяет сравнение

P (X) ≡ A i (X) (mod P i (X)), {\ displaystyle P (X) \ Equiv A_ {i} (X) {\ pmod {P_ {i} (X)}},}

{\ displaystyle P (X) \ Equiv A_ {i} (X) {\ pmod {P_ {i} (X)}},}

для $i = 1,…, k. {\ displaystyle i = 1, \ ldots, k.}$ ${\ displaystyle i = 1, \ ldots, k.}$

Рассмотрим многочлены

Q (X) = ∏ i = 1 k P i (X) Q i (X) = Q (X) P i (ИКС). {\ Displaystyle {\ begin {align} Q (X) = \ prod _ {i = 1} ^ {k} P_ {i} (X) \\ Q_ {i} (X) = {\ frac {Q (X)} {P_ {i} (X)}}. \ End {align}}}

{\ displaystyle {\ begin {align} Q (X) = \ prod _ {i = 1} ^ {k} P_ {i } (X) \\ Q_ {i} (X) = {\ frac {Q (X)} {P_ {i} (X)}}. \ End {align}}}

Разложение на частичные дроби $1 / Q (X) {\ displaystyle 1 / Q (X)}$ ${\ displaystyle 1 / Q (X)}$ дает k многочленов $S i (X) {\ displaystyle S_ {i} (X)}$ ${\ displaystyle S_ {i} (X)}$ со степенями $deg ⁡ S i (X) < d i, {\displaystyle \deg S_{i}(X)$ ${\ displaystyle \ deg S_ {i} (X) <d_ {i},}$ такими, что

1 Q (Икс) знак равно ∑ я знак равно 1 К S я (Икс) п я (Х), {\ Displaystyle {\ гидроразрыва {1} {Q (X)}} = \ сумма _ {я = 1} ^ {k} {\ frac {S_ {i} ( X)} {P_ {i} (X)}},}

{\ displaystyle {\ frac {1 } {Q (X)}} = \ sum _ {i = 1} ^ {k} {\ frac {S_ {i} (X)} {P_ {i} (X)}},}

и, следовательно,

1 = ∑ i = 1 k S i (X) Q i (ИКС). {\ displaystyle 1 = \ sum _ {i = 1} ^ {k} S_ {i} (X) Q_ {i} (X).}

{\ displaystyle 1 = \ sum _ {i = 1} ^ {k} S_ {i} (X) Q_ {i} (X).}

Тогда решение системы совместных сравнений дается полиномом

∑ я знак 1 к А я (Х) S я (Х) Q я (Х). {\ displaystyle \ sum _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X).}

{\ displaystyle \ sum _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X).}

Фактически, мы имеем

∑ i = 1 k A i (X) S i (X) Q i (X) = A i (X) + ∑ j = 1 k (A j (X) - A i (X)) S j (X) QJ ( Икс) ≡ A я (Икс) (модуль п я (X)), {\ Displaystyle \ сумма _ {я = 1} ^ {k} A_ {я} (X) S_ {я} (X) Q_ {i} (X) = A_ {i} (X) + \ sum _ {j = 1} ^ {k} (A_ {j} (X) -A_ {i} (X)) S_ {j} (X) Q_ { j} (X) \ Equiv A_ {i} (X) {\ pmod {P_ {i} (X)}},}

{\ displaystyle \ sum _ {i = 1} ^ {k} A_ {i} (X) S_ { i} (X) Q_ {i} (X) = A_ {i} (X) + \ sum _ {j = 1} ^ {k} (A_ {j} (X) -A_ {i} (X)) S_ {j} (X) Q_ {j} (X) \ Equ A_ {i} (X) {\ pmod {P_ {i} (X)}},}

для $1 ≤ i ≤ k. {\ displaystyle 1 \ leq i \ leq k.}$ ${\ displaystyle 1 \ leq i \ leq k.}$

Это решение может иметь степень больше, чем $D = ∑ i = 1 k d i. {\ displaystyle D = \ sum _ {i = 1} ^ {k} d_ {i}.}$ ${\ displaystyle D = \ sum _ {i = 1} ^ {k} d_ {i}.}$ Уникальное решение со степенью меньше $D {\ displaystyle D}$ $D$ можно вывести, рассматривая остаток $B i (X) {\ displaystyle B_ {i} (X)}$ ${\ displaystyle B_ {i} (X)}$ евклидова деления $A i (X) S i (X) {\ displaystyle A_ {i } (X) S_ {i} (X)}$ ${\ displaystyle A_ {i} (X) S_ {i} ( X)}$ на $P i (X). {\ Displaystyle P_ {i} (X).}$ ${\ displaystyle P_ {i} (X).}$ Это решение:

P (X) = ∑ я = 1 К В я (X) Q я (X). {\ displaystyle P (X) = \ sum _ {i = 1} ^ {k} B_ {i} (X) Q_ {i} (X).}

{\ displaystyle P (X) = \ сумма _ {я = 1} ^ {k} B_ {i} (X) Q_ {i} (X).}

Интерполяция Лагранжа

Особый случай китайской теоремы об остатке для многочленов есть интерполяция Лагранжа. Для этого рассмотрим k монических многочленов первой степени:

P i (X) = X - x i. {\ displaystyle P_ {i} (X) = X-x_ {i}.}

{\ displaystyle P_ {i} (X) = X-x_ {i}.}

Они попарно взаимно просты, если $x i {\ displaystyle x_ {i}}$ $x_ {i}$ все разные. Остаток от деления на $P i (X) {\ displaystyle P_ {i} (X)}$ ${\ displaystyle P_ {i} (X)}$ многочлена $P (X) {\ displaystyle P (X)}$ $P (X)$ равно $P (xi). {\ displaystyle P (x_ {i}).}$ $P (x_i).$

Теперь пусть $A 1,…, A k {\ displaystyle A_ {1}, \ ldots, A_ {k}}$ $A_ {1}, \ ldots, A_ {k }$ быть константами (многочленами степени 0) в $К. {\ displaystyle K.}$ $K.$ И интерполяция Лагранжа, и китайская теорема об остатках утверждают существование уникального многочлена $P (X), {\ displaystyle P (X),}$ ${\ displaysty ле P (X),}$ степени меньше, чем $k {\ displaystyle k}$ $k$ , так что

P (xi) = A i, {\ displaystyle P (x_ {i}) = A_ {i},}

{\ Displaystyle P (x_ {i}) = A_ {i},}

для каждого $я. {\ displaystyle i.}$ $i.$

Формула интерполяции Лагранжа в данном случае является результатом приведенного выше приведенного решения. Точнее, пусть

Q (X) = ∏ i = 1 k (X - x i) Q i (X) = Q (X) X - x i. {\ Displaystyle {\ begin {align} Q (X) = \ prod _ {i = 1} ^ {k} (X-x_ {i}) \\ [6pt] Q_ {i} (X) = { \ frac {Q (X)} {X-x_ {i}}}. \ end {align}}}

{\ displaystyle {\ begin {align} Q (X) = \ prod _ {i = 1} ^ {k} (X-x_ {i}) \\ [6pt] Q_ {i} (X) и = {\ frac {Q (X)} {X-x_ {i}}}. \ end {align}}}

Разложение на частичные дроби из $1 Q (X) {\ displaystyle {\ frac {1} {Q (X)}}}$ ${\ displaystyle {\ frac {1} {Q (X)}}}$ равно

1 Q (X) = ∑ i = 1 k 1 Q i (xi) (X - X i). {\ displaystyle {\ frac {1} {Q (X)}} = \ sum _ {i = 1} ^ {k} {\ frac {1} {Q_ {i} (x_ {i}) (X-X_ {i})}}.}

{\ displaystyle {\ frac {1} {Q (X)}} = \ sum _ {i = 1} ^ {k} {\ frac {1} {Q_ {i} ( x_ {i}) (X-X_ {i})}}.}

Фактически, сводя правую часть к общему знаменателю, получаем

∑ i = 1 k 1 Q i (xi) (X - X i) = 1 Q (Икс) ∑ я знак равно 1 К Q я (Икс) Q я (хи), {\ Displaystyle \ сумма _ {я = 1} ^ {к} {\ гидроразрыва {1} {Q_ {я} (х_ {я}) (X-X_ {i})}} = {\ frac {1} {Q (X)}} \ sum _ {i = 1} ^ {k} {\ frac {Q_ {i} (X)} {Q_ {i} ( x_ {i})}},}

{\ displaystyle \ sum _ {i = 1} ^ {k} {\ frac {1} {Q_ {i} (x_ {i}) (X-X_ {i})}} = {\ frac {1} {Q (X)}} \ sum _ {i = 1} ^ {k} {\ frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}},}

и числитель равен единице, так как многочленом степени меньше $k, {\ displaystyle k,}$ $к,$ который принимает один для $k { \ displaystyle k}$ $k$ различных значений $X. {\ displaystyle X.}$ $X.$

Используя приведенную выше общую формулу, мы получаем формулу интерполяции Лагранжа:

P (X) = ∑ i = 1 k A i Q i (X) Q i (x i). {\ displaystyle P (X) = \ sum _ {i = 1} ^ {k} A_ {i} {\ frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}}. }

{\ displaystyle P (X) = \ sum _ {i = 1} ^ {k} A_ {i} { \ frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}}.}

Интерполяция Эрмита

Интерполяция Эрмита - это приложение китайской теоремы об остатках для одномерных многочленов, которое может быть модуля произвольной степени (интерполяция Лагранжа включает только модули первой степени).

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

Точнее, пусть $x 1,…, xk {\ displaystyle x_ {1}, \ ldots, x_ {k}}$ $x_ {1}, \ ldots, x_ {k}$ будет $k {\ displaystyle k}$ $k$ элементы земли field $K, {\ displaystyle K,}$ $K,$ и, для $i = 1,…, k, {\ displaystyle i = 1, \ ldots, k,}$ ${\ displaystyle i = 1, \ ldots, k,}$ пусть $ai, 0, ai, 1,…, ai, ri - 1 {\ displaystyle a_ {i, 0}, a_ {i, 1}, \ ldots, a_ {i, r_ {i} -1}}$ ${\ displaystyle a_ {i, 0}, a_ {i, 1}, \ ldots, a_ {i, r_ {i} -1}}$ быть значениями первых $ri {\ displaystyle r_ {i}}$ $r_ {i}$ производных искомого полинома в точке $xi {\ displaystyle x_ {i}}$ $x_ {i}$ (включая 0-ю производную, которая является величиной самого полинома). Проблема состоит в том, чтобы найти многочлен $P (X) {\ displaystyle P (X)}$ $P (X)$ такой, что его j-я производная принимает значение $ai, j {\ displaystyle a_ { я, j}}$ $a_{i,j}$ в $xi, {\ displaystyle x_ {i},}$ ${\ displaystyle x_ {i},}$ для $i = 1,…, k {\ displaystyle i = 1, \ ldots, k}$ $i = 1, \ ldots, k$ и $j = 0,…, rj. {\ displaystyle j = 0, \ ldots, r_ {j}.}$ ${\ displaystyle j = 0, \ ldots, r_ {j}.}$

Рассмотрим многочлен

P i (X) = ∑ j = 0 r i - 1 a i, j j! (Х - х я) j. {\ displaystyle P_ {i} (X) = \ sum _ {j = 0} ^ {r_ {i} -1} {\ frac {a_ {i, j}} {j!}} (X-x_ {i }) ^ {j}.}

{\ displaystyle P_ {i} (X) = \ sum _ {j = 0} ^ {r_ {i} -1} {\ frac {a_ {i, j}} {j!} } (X-x_ {i}) ^ {j}.}

Это многочлен Тейлора порядка $ri - 1 {\ displaystyle r_ {i} -1}$ ${\ displaystyle r_ {i} -1}$ at $xi {\ displaystyle x_ {i}}$ $x_ {i}$ неизвестного многочлена $P (X). {\ displaystyle P (X).}$ ${\ displaystyle P (X).}$ Следовательно, мы должны иметь

P (X) ≡ P i (X) (mod (X - x i) r i). {\ Displaystyle P (X) \ Equiv P_ {i} (X) {\ pmod {(X-x_ {i}) ^ {r_ {i}}}}.}

{\ displaystyle P (X) \ Equiv P_ {i} (X) { \ pmod {(X-x_ {i}) ^ {r_ {i}}}}.}

И наоборот, любой многочлен $P (X) {\ displaystyle P (X)}$ ${\ displaystyle P ( X)}$ , который удовлетворяет этим $k {\ displaystyle k}$ $k$ сравнение, в частности, проверяет, для любого $i Знак равно 1,…, К {\ displaystyle i = 1, \ ldots, k}$ ${\ displaystyle i = 1, \ ldots, k}$

P (X) = P i (X) + o (X - xi) ri - 1 {\ displaystyle P (X) = P_ {i} (X) + o (X-x_ {i}) ^ {r_ {i} -1}}

{\ displaystyle P ( X) = P_ {i} (X) + o (X-x_ {i}) ^ {r_ {i} -1}}

следовательно, $P i (X) {\ displaystyle P_ {i} (X)}$ ${\ displaystyle P_ {i} (X)}$ - его многочлен Тейлора порядка $ri - 1 {\ displaystyle r_ {i} -1}$ ${\ displaystyle r_ {i} -1}$ at $xi {\ displaystyle x_ {i}}$ $x_ {i}$ , то есть $P (X) {\ displaystyle P (X)}$ $P (X)$ решает исходную задачу интерполяции Эрмита. Китайская теорема об остатках утверждает, что существует одна многочлен степени меньше ров суммы $ri, {\ displaystyle r_ {i},}$ ${\ displaystyle r_ {i},}$ , который удовлетворяет этим $k {\ displaystyle k}$ $k$ сравнение.

Есть несколько способов вычисления решения $P (X). {\ displaystyle P (X).}$ ${\ displaystyle P (X).}$ Можно использовать метод, описанный в начале § над кольцами одномерных многочленов и евклидовыми областями. Можно также использовать конструкции, приведенные в § Существование (конструктивное доказательство) или § Существование (прямое доказательство).

Обобщение на не взаимно простые модули

Китайская теорема об остатках может обобщаться на непростые модули. Пусть $m, n, a, b {\ displaystyle m, n, a, b}$ ${\ displaystyle m, n, a, b}$ - любые целые числа, пусть $g = gcd (m, n) {\ displaystyle g = \ gcd (m, n)}$ ${\ displaystyle g = \ gcd ( m, n)}$ , и рассмотрим систему сравнений:

x ≡ a (mod m) x ≡ b (mod n), {\ displaystyle {\ begin {align} x \ Эквивалент a {\ pmod {m}} \\ x \ Equiv b {\ pmod {n}}, \ end {align}}}

{\ displaystyle {\ begin {align} x \ Equiv a {\ pmod {m}} \\ x \ Equiv b {\ pmod {n}}, \ end {выравнивается}}}

Если $a ≡ b (mod g) {\ displaystyle a \ Эквив b {\ pmod {g}}}$ ${\ displaystyle a \ Equiv b {\ pmod {g}}}$ , тогда эта система уравнений имеет единственное решение по модулю $lcm ⁡ (m, n) = mn / g {\ displaystyle \ operatorname {lcm} ( m, n) = mn / g}$ ${\ displaystyle \ operatorname {lcm} (m, n) = mn / g}$ . В противном случае у нее нет решений.

Если мы используем личность Безу для записи $g = um + vn {\ displaystyle g = um + vn}$ ${\ displaystyle g = um + vn}$ , то решение будет

х = ср + бумг. {\ displaystyle x = {\ frac {avn + bum} {g}}.}

{\ displaystyle x = {\ frac {avn + bum} {g}}.}

Определяет целое число, поскольку g делит и m, и n. В остальном доказательство очень похоже на доказательство для взаимно простых модулей.

Обобщение на произвольные кольца

Китайская теорема об остатках может быть обобщена на любое кольцо, используя взаимно простые идеалы (также называемые комаксимальными идеалы ). Два идеала I и J взаимно просты, если есть элементы $i ∈ I {\ displaystyle i \ in I}$ $i \ in I$ и $j ∈ J {\ displaystyle j \ in J}$ $j \ in J$ такое, что $i + j = 1. {\ displaystyle i + j = 1.}$ ${\ displaystyle i + j = 1.}$ Это отношение играет роль тождества Безу в доказательствах, связанных с этим обобщением., которые в остальном очень похожи. Обобщение можно сформулировать следующим образом.

Пусть I 1,..., I k будут двусторонними идеалами кольца $R {\ displaystyle R}$ $R$ и пусть я буду их пересечением. Если идеалы попарно взаимно просты, мы имеем изоморфизм :

R / I → R / I 1 × ⋯ × R / I kx mod I ↦ (x mod I 1,…, x mod I k), { \ displaystyle {\ begin {align} R / I \ to R / I_ {1} \ times \ cdots \ times R / I_ {k} \\ x {\ bmod {I}} \ mapsto (x {\ bmod { I}} _ {1}, \, \ ldots, \, x {\ bmod {I}} _ {k}), \ end {align}}}

{\ displaystyle {\ begin {align} R / I \ to R / I_ { 1} \ times \ cdots \ times R / I_ {k} \\ x {\ bmod {I}} \ mapsto (x {\ bmod {I}} _ {1}, \, \ ldots, \, x { \ bmod {I}} _ {k}), \ end {align}}}

между кольцом частных $R / I {\ displaystyle R / I}$ $R / I$ и прямое произведение из $R / I i, {\ displaystyle R / I_ {i},}$ ${\ displaystyle R / I_ {я},}$ где « $x mod I {\ displaystyle x {\ bmod {I}}}$ ${\ displaystyle x {\ bmod {I}}}$ » обозначает изображение элемента $x {\ displaystyle x}$ $x$ в кольце частных, определяемом идеалом $I. {\ displaystyle I.}$ ${\ displaystyle I.}$ Более того, если $R {\ displaystyle R}$ $R$ является коммутативным, то идеальное пересечение попарно взаимно простых идеалов равно их продукт ; то есть

I = I 1 ∩ I 2 ∩ ⋯ ∩ I k = I 1 I 2 ⋯ I k, {\ displaystyle I = I_ {1} \ cap I_ {2} \ cap \ cdots \ cap I_ {k } = I_ {1} I_ {2} \ cdots I_ {k},}

{\ displaystyle I = I_ {1} \ cap I_ {2} \ cap \ cdots \ cap I_ {k} = I_ {1} I_ {2} \ cdots I_ {k},}

, если I i и I j взаимно просты для i ≠ j.

Приложения

Нумерация последовательностей

Китайская теорема об остатках была использована для построения нумерации Гёделя для последовательностей, которая используется в доказательстве Теоремы Гёделя о неполноте.

Быстрое преобразование Фурье

Алгоритм БПФ с простым множителем (также называемый алгоритмом Гуда-Томаса) использует китайскую теорему об остатках для сокращения вычислений быстрое преобразование Фурье размера $n 1 n 2 {\ displaystyle n_ {1} n_ {2}}$ $n_ {1} n_ {2}$ к вычислению двух быстрых преобразований Фурье меньшего размера $n 1 {\ displaystyle n_ {1}}$ $n_ {1}$ и $n 2 {\ displaystyle n_ {2}}$ $n_ {2}$ (при условии, что $n 1 {\ displaystyle n_ {1}}$ $n_ {1}$ и $n 2 {\ displaystyle n_ {2}}$ $n_ {2}$ взаимно просты).

Шифрование

Большинство реализаций RSA используют китайскую теорему об остатках во время подписания сертификатов HTTPS и во время дешифрования.

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

Разрешение неоднозначности диапазон

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

Теорема Дедекинда

Теорема Дедекинда о линейной независимости характеров. Пусть M будет моноидом и k областью целостности, рассматриваемой как моноид рассмотрев умножение на k. Тогда любое конечное семейство (f i)i∈I различных гомоморфизмов моноидов f i : M → k линейно независимое. Другими словами, каждое семейство (α i)i∈I элементов α i ∈ k, удовлетворяющих

∑ i ∈ I α ifi = 0 {\ displaystyle \ sum _ {i \ in I} \ alpha _ {i} f_ {i} = 0}

\ sum_ {я \ in I} \ alpha_i f_i = 0

должен быть равен семейству (0) i∈I.

Доказательство. Предположим, что k является полем, иначе замените область целостности ее полем частных частных, и ничего не будет Мы можем линейно продолжить гомоморфизмы моноидов f i : M → k до гомоморфизмов k-алгебр F i : k [M] → k, где k [M] - моноидное кольцо из M над k. Тогда по линейности выполняется условие

∑ i ∈ I α ifi = 0, {\ displaystyle \ sum _ {i \ in I} \ alpha _ {i} f_ {i} = 0,}

\ sum_ {i \ in I} \ alpha_i f_i = 0,

дает

∑ я ∈ I α я F я знак равно 0. {\ displaystyle \ sum _ {i \ in I} \ alpha _ {i} F_ {i} = 0.}

\ sum_ {i \ in I} \ alpha_i F_i = 0.

Затем для i, j ∈ I; i ≠ j два k-линейных отображений F i : k [M] → k и F j : k [M] → k не пропорциональны друг другу. В случае f i и f j также могут быть пропорциональны и, следовательно, равны, поскольку моноидные гомоморфизмы они удовлетворяют: f i (1) = 1 = f j (1), что противоречит предположению, что они отчетливый.

Следовательно, ядра F i и Ker F j различны. K [M] / Ker F i ≅ F i (k [M]) = k - поле, Ker F i - максимальный идеал k [M ] для любого i ∈ I. Это они различны и максимальны, идеалы Ker F i и Ker F j взаимно просты, когда i ≠ j. Китайская теорема об остатке (для общих колец) дает изоморфизм:

ϕ: k [M] / K → ∏ i ∈ I k [M] / K er F i ϕ (x + K) = (x + K er F я) я ∈ I {\ Displaystyle {\ begin {align} \ phi: k [M] / K \ to \ prod _ {i \ in I} k [M] / \ mathrm {Ker} F_ {i} \ \\ phi (x + K) = \ left (x + \ mathrm {Ker} F_ {i} \ right) _ {i \ in I} \ end {align}}}

{\ begin {align} \ phi: k [M] / K \ to \ prod _ {{i \ in I}} k [M] / {\ mathrm {Ker}} F_ {i} \\\ phi (x + K) = \ left (x + {\ mathrm {Ker}} F_ {i} \ right) _ {{i \ in I}} \ end {align}}

где

K = I ∈ IK er F i = ⋂ i ∈ IK er F i. {\ displaystyle K = \ prod _ {i \ in I} \ mathrm {Ker} F_ {i} = \ bigcap _ {i \ in I} \ mathrm {Ker} F_ {i}.}

K = \ prod_ {i \ in I} \ mathrm {K эр} F_i = \ bigcap_ {i \ in I} \ mathrm {Ker} F_i.

Следовательно, карта

Φ: к [M] → ∏ i ∈ I К [M] / K er F i Φ (x) = (x + K er F i) i ∈ I {\ displaystyle {\ begin {align} \ Phi : k [M] \ to \ prod _ {i \ in I} k [M] / \ mathrm {Ker} F_ {i} \\\ Phi (x) = \ left (x + \ mathrm {Ker} F_ {i} \ right) _ {i \ in I} \ end {align}}}

{\ begin {align} \ Phi: k [M] \ to \ prod _ {{i \ in I}} k [M] / {\ mathrm {Ker}} F_ {i} \\\ Phi (x) = \ left (x + { \ mathrm {Ker}} F_ {i} \ right) _ {{i \ in I}} \ end {align}}

сюръективно. При изоморфизмах k [M] / Ker F i → F i (k [M]) = k, отображение Φ соответствует:

ψ: k [M] → ∏ я ∈ я К ψ (Икс) знак равно [F я (Икс)] я ∈ I {\ Displaystyle {\ begin {выровнено} \ psi: k [M] \ to \ prod _ {я \ in I} k \\ \ psi (x) = \ left [F_ {i} (x) \ right] _ {i \ in I} \ end {align}}}

{\ begin {align} \ psi : k [M] \ to \ prod _ {{i \ in I}} k \\\ psi (x) = \ left [F_ {i} (x) \ right] _ {{i \ in I} } \ end {align}}

Теперь

∑ i ∈ I α i F я знак равно 0 {\ displaystyle \ sum _ {я \ in I} \ alpha _ {i} F_ {i} = 0}

\ sum_ {i \ in I} \ alpha_i F_i = 0

дает

∑ я ∈ I α iui = 0 {\ displaystyle \ sum _ {i \ in I} \ alpha _ {i} u_ {i} = 0}

\ sum_ {i \ in I} \ alpha_i u_i = 0

для каждого вектора (u i)i∈I в изображении карты ψ. Времена ψ сюръективно, это означает, что

∑ i ∈ I α iui = 0 {\ displaystyle \ sum _ {i \ in I} \ alpha _ {i} u_ {i} = 0}

\ sum_ {i \ in I} \ alpha_i u_i = 0

для каждого облака

(ui) i ∈ I ∈ ∏ я ∈ I К. {\ Displaystyle \ left (u_ {i} \ right) _ {i \ in I} \ in \ prod _ {i \ in I} k.}

\ left (u_i \ right) _ {i \ in I} \ in \ prod_ {i \ in I} k.

Следовательно, (α i)i ∈I = (0) i∈I. QED.

См. Также

Примечания

Ссылки

Dauben, Joseph W. (2007), «Глава 3: Китайская математика», в Katz, Victor J. (ред.), Математика Египта, Месопотамии, Китая, Индии и ислама: Справочник, Princeton University Press, стр. 187–384, ISBN 978-0-691-11485-9
Денс, Джозеф Б.; Денс, Томас П. (1999), Элементы теории чисел, Academic Press, ISBN 9780122091308
Duchet, Pierre (1995), «Hypergraphs», в Graham, RL; Grötschel, M. ; Ловас, Л. (ред.), Справочник по комбинаторике, Vol. 1, 2, Амстердам: Elsevier, стр. 381–432, MR 1373663. См., В частности, раздел 2.5 «Собственность Хелли», стр. 393–394.
Гаусс, Карл Фридрих (1986), Disquisitiones Arithemeticae, перевод Кларк, Артур А. (Второй, исправленный ред.), Нью-Йорк: Springer, ISBN 978-0-387-96254-2
Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (2-е изд.), Springer-Verlag, ISBN 0-387-97329-X
Kak, Subhash (1986), «Вычислительные аспекты алгоритма Арьябхата» (PDF), Индийский журнал истории науки, 21 (1): 62–71
Кац, Виктор Дж.. (1998), История математики / Введение (2-е изд.), Эддисон Уэсли Лонгман, ISBN 978-0-321-01618-8
Либбрехт, Ульрих (1973), Китайская математика в тринадцатом веке: «Шу-шу Чиу-чан» Цинь Цзю-шао, Dover Publications Inc, ISBN 978-0-486 -44619-6
Ore, Oystein (1988) [1948], Теория чисел и ее история, Dover, ISBN 978-0-486-65620-5
Пизано, Леонардо (2002), Liber Abaci Фибоначчи, перевод Сиглера, Лоуренса Э., Спрингер-Верлаг, стр. 402–403, ISBN 0-387-95419-8
Розен, Кеннет Х. (1993), Элементарная теория чисел и ее приложения (3-е изд.), Аддис. он-Уэсли, ISBN 978-0201-57889-8

Дополнительная литература

Кормен, Томас Х. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press и McGraw-Hill, ISBN 0-262-03293-7. См. Раздел 31.5: Китайская теорема об остатках, стр. 873–876.
Дин, Цуньшэн; Пей, Динъи; Саломаа, Арто (1996), Китайская теорема об остатках: приложения в вычислениях, кодировании, криптографии, World Scientific Publishing, стр. 1-213, ISBN 981-02-2827-9
Хангерфорд, Томас У. (1974), Алгебра, Тексты для выпускников по математике, Vol. 73, Springer-Verlag, pp. 131–132, ISBN 978-1-4612-6101-8
Кнут, Дональд (1997), The Art of Компьютерное программирование, том 2: получисловые алгоритмы (третье изд.), Addison-Wesley, ISBN 0-201-89684-2. См. Раздел 4.3.2 (стр. 286–291), упражнение 4.6.2–3 (стр. 456).

Внешние ссылки

, Энциклопедия математики, EMS Press, 2001 [ 1994]
Вайсштейн, Эрик У. «Китайская теорема об остатках». MathWorld.
Китайская теорема об остатках на PlanetMath.org.
Полный текст Sun-tzu Suan-ching (китайский) - Китайский текстовый проект