Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
az ≡ b (mod m). Напротив, если ax ≡ az ≡ b (mod m), то ax − az ≡ b − b ≡ 0 (mod m), и значит, m | a(x − z). Тогда m/d делит x − z, и следовательно, x ≡ z (mod m/d). ¤ Пример 3.8.1. Найдем решение уравнения 270x ≡ 36 (mod 342). По ал- горитму Евклида получим (−5) · 270 + 4 · 342 = 18 = (270, 342) и 18 | 36. По теореме 3.8.1 существует единственное решение данного уравнения по мо- дулю 19 = 342/18. Для нахождения этого решения умножим равенство (−5) · 270 + 4 · 342 = 18 на 2 = 36/18 и получим (−10) · 270 + 8 · 342 = 36, откуда следует, что (−10) — одно из решений уравнения по модулю 342. Так как 9 ≡ −10 (mod 19), то 9 — единственное решение по модулю 19. Общее решение уравнения представляется в виде x = 9 + 19k. ¤ Частным случаем теоремы 3.8.1 является Следствие 3.8.2. Уравнение ax ≡ 1 (mod m) тогда и только тогда имеет решение, когда (a, m) = 1. Решение a −1 (mod m) единственно по мо- дулю m и является обратным к a элементом по модулю m. ¤ Пример 3.8.2. Уравнение 2x ≡ 1 (mod 26) не имеет решений, поскольку (2, 26) = 2. ¤ Рассмотрим теперь задачу решения системы линейных уравнений по мо- дулю некоторого числа m. При этом возникает изоморфизм кольца Z M и декартова произведения колец Z m 1 , Z m 2 , . . ., Z m k , где M = m 1 m 2 . . . m k , (m i , m j ) = 1, i 6= j. Прежде чем формулировать изоморфизм в общем случае, рассмотрим следующий 3.8. ЛИНЕЙНЫЕ УРАВНЕНИЯ ПО МОДУЛЮ m 107 Пример 3.8.3. Кольцо Z 6 изоморфно декартову произведению колец Z 2 и Z 3 : Z 6 ∼ = Z 2 × Z 3 , M = 6, m 1 = 2, m 2 = 3. Шести элементам кольца Z 6 со- ответствуют пары (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2). Арифметическим опе- рациям в Z 6 соответствуют операции над парами, выполняемые покоорди- натно: (x 1 , x 2 ) + (y 1 , y 2 ) = (x 1 + y 1 , x 2 + y 2 ), (x 1 , x 2 ) · (y 1 , y 2 ) = (x 1 · y 1 , x 2 · y 2 ). Например, (0, 2)·(1, 2) = (0, 1), где умножение 0·1 выполняется по модулю 2, а умножение 2 · 2 — по модулю 3. ¤ Теорема 3.8.3 (китайская теорема об остатках). Пусть m 1 , m 2 , . . . , m k — попарно взаимно простые целые числа больше 1, M = m 1 m 2 . . . m k ; a 1 , a 2 , . . . , a k — целые числа, 0 6 a i < m i , i ∈ {1, 2, . . . , k}. Тогда существует единственное неотрицательное решение по модулю M следующей системы уравнений: x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), . . . , x ≡ a k (mod m k ). Отображение, которое каждому целому числу x (0 6 x 6 M − 1) ставит в соответствие строку (a 1 , a 2 , . . . , a k ), где x ≡ a i (mod m i ) (i = 1, 2, . . . , k), является изоморфизмом кольца Z M на кольцо Z m 1 × Z m 2 × . . . × Z m k . Доказательство. Нужно найти число x (0 6 x 6 M − 1), удовле- творяющее всем сравнениям x ≡ a i (mod m i ), i = 1, 2, . . . , k. Будем решать уравнения по два одновременно. Рассмотрим сначала первые два сравне- ния. Первое сравнение x ≡ a 1 (mod m 1 ) справедливо для всякого x вида x = a 1 + m 1 q, q ∈ Z. Для нахождения q подставим значение x во второе сравнение x ≡ a 2 (mod m 2 ). Имеем x = a 1 + m 1 q ≡ a 2 (mod m 2 ), откуда q ≡ (m 1 ) −1 (a 2 − a 1 ) (mod m 2 ). Таким образом, q = (m 1 ) −1 (a 2 − a 1 ) + rm 2 для некоторого r. Подставив значение q в выражение x = a 1 + m 1 q, получим, что решение x первых двух уравнений представляется в виде x = a 12 + r(m 1 m 2 ) для некоторого r. Теперь первые два сравнения можно заменить на од- но сравнение x ≡ a 12 (mod m 1 m 2 ). Применим описанную выше процедуру к сравнению x ≡ a 12 (mod m 1 m 2 ) и сравнению, которое первоначально было третьим, и будем повторять этот процесс, пока не найдем число x, удовле- творяющее всем сравнениям. Для доказательства единственности предположим, что существует x 0 (0 6 x 0 6 M − 1) такой, что x 0 ≡ a i (mod m i ) для любого i. Тогда x − x 0 ≡ 0 (mod m i ) для всех i, откуда следует, что m i | (x − x 0 ) для любого i. Тогда M | (x − x 0 ) и, поскольку |x − x 0 | < M , x = x 0 . ¤ 108 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Пример 3.8.4. Решим систему уравнений x ≡ 1 (mod 2), x ≡ 2 (mod 5), x ≡ 5 (mod 7). Из первого уравнения следует, что x = 1+2q. Чтобы вычислить q, подста- вим x во второе уравнение: 1 + 2q ≡ 2 (mod 5) или 2q ≡ (2 − 1) (mod 5). Так как 2 −1 ≡ 3 (mod 5), то q ≡ 2 −1 (2 − 1) (mod 5) ≡ 3 (mod 5) или q = 3 + 5r для некоторого r. Следовательно, решением первых двух уравнений явля- ется x = 1 + 2(3 + 5r) = 7 + 2 · 5r, т. е. x ≡ 7 (mod 2 · 5). Осталось решить систему уравнений x ≡ 7 (mod 2 · 5) и x ≡ 5 (mod 7). Имеем x = 7 + 2 · 5q ≡ 5 (mod 7) или 2 · 5q ≡ (5 − 7) ≡ −2 ≡ 5 (mod 7). Так как 10 −1 ≡ 3 −1 ≡ 5 (mod 7), то q ≡ 5 · 5 (mod 7) ≡ 4 (mod 7) или q = 4 + 7r для некоторого r. Следовательно, решением трех уравнений является число x = 7 + 2 · 5(4 + 7r) или x ≡ 47 (mod 2 · 5 · 7). Отметим, что 47 = 1 + 3 · (2) + 4 · (2 · 5), где коэффициенты 3 и 4 являются значениями q. Заметим также, что при изоморфизме Z 2·5·7 ∼ = Z 2 × Z 5 × Z 7 число 47 соответствует данной тройке (1, 2, 5). ¤ В общем случае решение системы k уравнений x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), . . . , x ≡ a k (mod m k ) представляется в виде x = q 1 + q 2 · m 1 + q 3 · (m 1 · m 2 ) + . . . + q k · (m 1 · m 2 · . . . · m k−1 ), где 0 6 q i < |m i |, q 1 — остаток от деления a 1 на m 1 Опишем применение китайского алгоритма к задаче о безопасном хране- нии ключа. Пусть K ∈ Z — ключ, который необходимо сохранить. При этом требуется, чтобы любые L человек из тех k (k > L), которые получили ин- формацию о ключе, могли бы вместе восстановить ключ, но ни одна группа из L − 1 человек или менее не могла этого сделать. Для решения этой задачи выберем такое множество целых чисел {p, d 1 , d 2 , . . . , d k }, что: 1) p > K; 2) d 1 < d 2 < . . . < d k ; 3) числа p, d 1 , d 2 , . . . , d k попарно взаимно просты; 4) d 1 · d 2 · . . . · d k > p · d k−L+2 · d k−L+3 · . . . · d k Пункт 4 означает, что произведение L наименьших чисел d i больше, чем произведение p и L − 1 наибольших чисел d i . Положим D d 1 · d 2 · . . . · d k 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 109 Тогда D/p больше, чем произведение любых L − 1 чисел d i . Выберем теперь целое число r ∈ [0, (D/p) − 1] так, чтобы число K 0 = K + r · p попало в интервал [D/p, D − 1]. Между разными людьми распределяются числа K i ≡ K 0 (mod d i ), i = 1, 2, . . . , k. Пример 3.8.5. Предположим, что требуется закодировать ключ K = 5 и при этом L = 2, k = 3, p = 7, d 1 = 11, d 2 = 13, d 3 = 17. Имеем D = d 1 · d 2 = 11 · 13 = 143 > 119 = 7 · 17 = p · d 3 , как и требуется. Выберем число r ∈ [0, (143/7) − 1] = [0, 19] так, что K 0 = K + r · p ∈ [D/p, D− 1], т. е. 5+ 7r ∈ [20, 142]. Возьмем, например, r = 3, тогда K 0 = 26. Распре- деляемые числа равны K 1 = 26 (mod 11) = 4, K 2 = 26 (mod 13) = 0, K 3 = 26 (mod 17) = 9. По любым двум из этих чисел можно восстановить K. Например, для K 1 и K 3 имеем K 0 ≡ 4 (mod 11), K 0 ≡ 9 (mod 17). Используя китайский алгоритм, находим K 0 = 26, откуда K = K 0 − r · p = 5. ¤ § 3.9. Точные вычисления, использующие модулярную арифметику Используя результаты предыдущих параграфов, опишем способ выпол- нения точных арифметических действий с (большими) целыми числами, при котором целые числа представляются в виде кортежей остатков от деления данных чисел на попарно взаимно простые модули, а выполнение арифме- тических операций сводится к выполнению соответствующих операций над остатками. Рассмотрим сначала случай одного модуля. Пусть дано выражение f (x 1 , x 2 , . . . , x h ), являющееся термом сигнатуры Σ = {+ (2) , − (1) , · (2) , (() −1 ) (1) }, и требуется вычислить значение f (i 1 , i 2 , . . . , i h ), где i 1 , i 2 , . . . , i h ∈ Z. Три- виальный подход состоит в непосредственном вычислении значения терма. Однако промежуточные результаты могут не быть целыми числами (напри- мер, 1/3 = 0.333 . . . = 0.(3)), и отбрасывание цифр или округление может привести к неточности окончательного результата. Во избежание этого со- поставим вычислению значения f (i 1 , i 2 , . . . , i h ) над Z соответствующее вы- числение значения f (i 0 1 , i 0 2 , . . . , i 0 h ) в поле Z m по обходному пути, показанному на рис. 3.2. Вместо вычисления f (i 1 , i 2 , . . . , i h ) над Z мы сначала получаем эквива- лентное выражение f m = f (i 0 1 , i 0 2 , . . . , i 0 h ) над Z m для некоторого простого m, где i 0 j ≡ i j (mod m), j = 1, 2, . . . , h. Затем вычисляем выражение f m над Z m 110 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Z Выражение (f ) −−−−→ Z m Эквивалентное выражение (f m ) y Вычисление над Z y Вычисление над Z m Результат (res) ←−−−− Эквивалентный результат (res m ) Рис. 3.2 и получаем эквивалентный результат res m , где res m ≡ res (mod m). В за- ключение отображаем res m обратно в множество целых чисел. Отметим, что отношение res ≡ res m (mod m) не определяет однозначно окончательный результат res. Например, условие x ≡ 7 (mod 13) означает, что x может быть равным 7, 20 и т. д. Однако если мы знаем, что 0 < x < 13, то x может быть равным только 7. Для того чтобы однозначно определить res, нужно иметь априорную оценку его величины. Эта оценка используется в качестве модуля m, и все операции выполняются в кольце Z m . Если име- ется оценка на величину res, то ищем наименьшее неотрицательное решение уравнения res ≡ res m (mod m). Если же мы имеем оценку на |res|, то ищем наименьшее по абсолютной величине решение. Сложности с данным методом возникают при выполнении операции деле- ния. Как уже отмечалось, в случае, когда p — простое число, кольцо hZ; +, ·i является конечным полем. Поскольку обратный элемент к любому ненуле- вому элементу всегда существует, деление по модулю p определяется следу- ющим образом: a b (mod p) = a · (b −1 (mod p)) (mod p), где b −1 (mod p) — элемент, обратный к элементу b по модулю p, который будет также обозначаться просто через b −1 . Частное двух целых чисел в Z p также является целым числом, даже если b не делит a в Z. Пример 3.9.1. 3/4 (mod 11) ≡ 3 · 4 −1 (mod 11) ≡ 3 · 3 (mod 11) ≡ 9. Таким образом, 3/4 ≡ 9 (mod 11). Число, полученное в этом примере и рас- сматриваемое как промежуточный результат, имеет смысл для дальнейших вычислений, поскольку (3/4) · 4 (mod 11) ≡ 9 · 4 (mod 11) ≡ 3 (mod 11). ¤ Предположим теперь, что модуль p ограничивает окончательный результат res. Если res не является целым числом, принадлежащим Z p , 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 111 то res p 6= res, и для того чтобы получить последнее число, требуется допол- нительная информация (которую мы проиллюстрируем ниже двумя при- мерами). Если res лежит в Z p , то res p = res. Таким образом, арифметика одного модуля может быть использована для выполнения последователь- ности точных арифметических операций над целыми числами в Z p , даже если эта последовательность включает операции деления. Трудности могут возникнуть лишь при интерпретации результатов. Если вычисляемое выражение может быть положительным или отри- цательным, необходимо использовать симметричную систему с носителем {− p−1 2 , . . . , −2, −1, 0, 1, 2, . . . , p−1 2 }, которая изоморфна неотрицательной си- стеме с носителем {0, 1, . . . , p − 1}. Изоморфизм ϕ между этими системами осуществляется по формуле ϕ(k) = ( k, если 0 6 k 6 p−1 2 , k + p, если − p−1 2 6 k < 0. Пример 3.9.2. На рис. 3.3 показано отображение ϕ при p = 11. Урав- нение x ≡ 17 (mod 11) имеет наименьшее неотрицательное решение x = 6 и наименьшее по абсолютной величине решение x = −5. ¤ При выполнении арифметических операций удобно сначала отобразить данные в неотрицательное множество, выполнить в нем все операции, а за- тем отобразить обратно в симметричное множество. ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ 0 1 2 3 4 5 6 7 8 9 10 -5 -4 -3 -2 -1 0 1 2 3 4 5 Неотрицательное множество множество Симметричное Рис. 3.3 |