Уравнения по модулю некоторого числа m.

В заключение рассмотрим уравнения по модулю m и греко-китайский алгоритм. Заметим, что уравнение имеет решения , тогда как уравнение не имеет решений [попробуйте подставить ]. Следующая теорема говорит о том, в каких случаях можно решить такое уравнение.

Теорема 2.3.22. Уравнение имеет решение тогда и только тогда, когда . Если решение существует, то оно единственно по модулю где по модулю уравнение имеет d решений.

Доказательство. Целое число удовлетворяет уравнению тогда и только тогда, когда существует целое число у, такое, что . По теореме 2.2.4 уравнение имеет решения тогда и только тогда, когда Для доказательства второй части предположим, что удовлетворяет условию и пусть z сравнимо с по модулю где Тогда для некоторого w G Z, и таким образом, . Обратно, пусть . Тогда следовательно, . По теореме делит , и, значит,

Пример. Найдем решения уравнения . Применяя расширенный алгоритм Евклида, получим, что По теореме 2.3.22 это уравнение имеет решение, единственное по модулю . Для нахождения этого решения умножим равенство на и получим откуда следует, что — одно из решений уравнения по модулю 342. По модулю 19 это единственное решение, равное 9, поскольку Другими решениями по модулю 342 являются числа 9, 28, 47, 66, 85, 104, 123, 142 и так далее.

Частным случаем теоремы 2.3.22 является следующее утверждение.

Следствие 2.3.23. Уравнение имеет решение тогда и только тогда, когда Решение единственно по модулю 771 и является мультипликативным обратным к а элементом по модулю .

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

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

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

Например, поскольку . Это означает, что мы должны рассматривать пары , где ; например, шести элементам кольца соответствуют пары (0,0), (0,1), (0,2), (1,0), (1,1), (1,2). Арифметические операции выполняются покомпонентно: если обозначить значком одну из операций или то где операция выполняется в (арифметика по модулю 2), а операция — в (арифметика по модулю 3); например, , где умножение выполняется по модулю 3. Справедлива следующая теорема.

Теорема 2.3.24 (греко-китайская теорема об остатках). Пусть — попарно взаимно простые целые числа и пусть . Тогда существует единственное неотрицательное решение по модулю М следующей системы уравнений:

Другими словами, отображение, которое каждому целому числу ставит в соответствие строку , где является биекцией кольца на

Доказательство. Дадим конструктивное доказательство этой теоремы. Нужно найти число удовлетворяющее одновременно всем сравнениям Будем решать уравнения по 2 одновременно.

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

процедура MODINV.) Таким образом, для некоторого . Подставив значение q в выражение получим, что решение первых двух уравнений представляется в виде для некоторого .

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

Для доказательства единственности предположим, что существует такой, что для любого . Тогда для всех i, откуда следует, что для любого i. Но тогда и, поскольку

Интересно отметить, что если в теореме 2.3.24 модули не являются взаимно простыми, то решение существует тогда и только тогда, когда для всех пар . Если решение существует, то оно единственно по модулю наименьшего общего кратного чисел см. также упр. 10 к этому разделу.

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

В соответствии с процедурой, описанной в доказательстве теоремы 2.3.24, мы видим, что первое уравнение выполняется для . Чтобы вычислить q, подставим во второе уравнение; получим или Затем вычислим мультипликативный обратный элемент к который равен 3, и, таким образом, или для некоторого . Следовательно, решением первых двух уравнений является , т.е. .

Теперь нам нужно ешить систему двух уравнений Имеем или Мультипликативный обратный элемент к 10 по модулю 7 совпадает с обратным к 3 по модулю 7,

который равен 5. Далее получаем или для некоторого . Следовательно, решением трех уравнений является число или

Отметим, что где коэффициенты 3 и 4 являются значениями

Перед тем как описать греко-китайский алгоритм, основанный на теореме 2.3.14, мы приведем две близкие к ней теоремы.

Теорема 2.3.25. Пусть . Тогда функция, которая каждому ставит в соответствие строку , где , является кольцевым изоморфизмом (т.е. взаимно однозначным гомоморфизмом на) кольца и кольца строк где для . Более того, если обозначить через любую из операций или имеем , где знак в правой части равенства обозначает соответствующую операцию в .

Доказательство. Доказательство вытекает непосредственно из теоремы 2.3.24 и оставляется читателю в качестве упражнения.

Разложение, указанное в теореме 2.3.25, записывается как Это разложение колец индуцирует разложение групп их обратимых элементов

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

Пример. Для имеем сумма этих чисел равна последняя пара представляет число 13. Что можно сказать об их произведении?

Заметим, что по паре (1,3) можно найти соответствующее целое число с помощью либо греко-китайского алгоритма, который будет описан ниже, либо специальных таблиц.

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

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

Теорема 2.3.26. Натуральное число свободно от квадратов тогда и только тогда, когда существует (которое будет определено ниже), такое, что для любого целого числа 6 выполняется сравнение . А именно, если Для различных простых чисел для произвольного натурального А, то для любых .

Доказательство, Предположим, что то свободно от квадратов, т.е. для различных простых чисел. Тогда из утверждения о единственности в греко-китайской теореме об остатках мы получаем, что для произвольного и любого сравнение выполняется тогда и только тогда, когда для всех . Пусть где либо любое другое общее кратное чисел Это означает, что для любого и некоторого поэтому Если то по теореме Ферма в противном случае . В любом случае мы получаем для всех и, следовательно, .

Предположим теперь, что то не свободно от квадратов, т.е. где для некоторого Найдем с помощью греко-китайской теоремы об остатках решение системы сравнений Получим, что то не делит 6, поскольку не делит 6, но делит для любого Таким образом, сравнение не выполняется ни для какого

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

Рассмотрим сначала систему из двух уравнений:

Эта система решается методом, описанным в доказательстве теоремы 2.3.24. Мы также будем использовать процедуру MODINV, которая вычисляет (наименьший неотрицательный) обратный элемент по модулю к элементу (см. упр. 2 по программированию к этому разделу). Оформив описанный метод в виде алгоритма, получим GCRA2. Греко-китайский алгоритм для двух сравнений (Greek-Chinese Remainder Algorithm-2 congruences)

Вход: такие, что где — целые числа одинарной точности, такие, что оба

Выход: — единственное наименьшее неотрицательное решение по модулю системы сравнений.

1. [Если то ничто не меняется]

2. [Вычисление ]

3. [Вычисление ]

4. [Выход] Вернуть (поскольку то возвращаемое значение удовлетворяет неравенствам ).

Анализ времени работы алгоритма GCRA2. Заметим, что шаги 1 и 2 выполняются за время поскольку мы работаем с короткими целыми числами (используя расширенный алгоритм Евклида для вычисления мультипликативного обратного). На шаге 3 мы выполняем умножение и деление, на шаге 4 — только одно умножение. Время выполнения каждой из этих операций доминируется временем вычисления произведения (проверьте это), и, следовательно,

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

Идея состоит в том, чтобы использовать GCRA2 для последовательного решения пар уравнений. На первом шаге мы получаем решение первых двух уравнений, где наименьшее неотрицательное решение по модулю На следующем шаге мы получаем решение по модулю пары уравнений

и так далее. Получаем следующий алгоритм.

GCRAk. Греко-китайский алгоритм для к сравнений (Greek-Chinese Remainder Algorithm-k conqruences)

Вход: Пары такие, что ; каждое является коротким целым числом, для

Выход: — единственное наименьшее неотрицательное решение по модулю системы из к уравнений.

1. [Инициализация]

2. [Применение в цикле GCRA2] Для t от 1 до выполнять

3. [Вычисление ]

4. [Выход] Вернуть

Анализ времени работы алгоритма GCRAk. Ясно, что время работы алгоритма GCRAk доминируется временем выполнения второго шага, на котором в цикле выполняется GCRA2. Если , то выполнение тела цикла требует времени Поэтому в целом цикл, состоящий из () шага, выполняется за время (напомним, что функция L ведет себя как логарифм) и мы имеем

Пример, иллюстрирующий работу этого алгоритма, был приведен непосредственно после теоремы 2.3.24. Читатель может попробовать применить этот алгоритм для системы единственным решением которой по модулю 840 является алгоритм формирует ответ в виде

В общем случае, если мы имеем к уравнений, то ответ представляется в виде

где каждое неотрицательно и меньше соответствующего модуля

Мы закончим этот раздел описанием применения греко-китайского алгоритма к задаче о безопасном хранении ключа (Asmuth, С., Bloom, J.: A modular approach to key safeguarding. Mathematics Department, Texas A and M University, College Station, TX, 77844).

Пусть К — ключ, который нужно сохранить. При этом требуется, чтобы любые L человек из тех , которые получили «информацию» о ключе, могли бы вместе восстановить ключ, но никакая группа из человек или менее не могла этого сделать. Информация, передаваемая различным людям, будет описана ниже.

Для решения этой задачи выберем множество целых чисел такое, что

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

Пример. . Далее, как и требуется. Выберем случайное число в интервале например 2. Имеем

Распределяемые числа равны

По любым двум из этих чисел можно восстановить К. Например, для имеем

Применив греко-китайский алгоритм, получим откуда .