Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
k 106 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Тогда 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 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 107 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 , 108 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ то 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 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 109 Пример 3.9.3. Выполним точные арифметические операции в Z 11 для вычисления x = 1/3 − 4/3. В этом примере априорная информация состоит в том, что результат ищется в симметричном множестве. Имеем x (mod 11) ≡ (1/3 + (−4)/3) (mod 11) ≡ (1/3 + 7/3) (mod 11) ≡ (1 · 3 −1 + 7 · 3 −1 ) (mod 11) ≡ (1 · 4+ + 7·4) (mod 11) ≡ 32 (mod 11). Отображая результат обратно в симметрич- ное множество, получаем правильный ответ x = −1. В приведенном примере res p = res, поскольку с самого начала известно, что res лежит в симметрич- ном множестве для Z 11 . ¤ Пример 3.9.4. Вычислим x = 1/2 − 2/3, пользуясь той же априорной информацией, что и в предыдущем примере. Имеем x (mod 11) ≡ (1/2 + (−2)/3) (mod 11) ≡ (1/2 + 9/3) (mod 11) ≡ ≡ (1 · 2 −1 + 9 · 3 −1 ) (mod 11) ≡ (1 · 6 + 9 · 4) (mod 11) ≡ 42 (mod 11) ≡ 9. Ес- ли мы отобразим результат в симметричное множество, то получим непра- вильный ответ: x = −2. Поэтому требуется дополнительная информация о том, что мы ищем рациональное число x (mod 11) ≡ (a/b) (mod 11), где b =НОК(2, 3). Тогда a = xb (mod 11) ≡ 9 · 6 (mod 11) ≡ 10 (mod 11) ≡ −1. Следовательно, x = (−1)/6, что является правильным ответом. ¤ Перейдем теперь к арифметике нескольких модулей. Использование этой арифметики позволяет естественно решать проблему компьютерного представления и работы с большими целыми числами, с которой мы сталки- ваемся в арифметике одного модуля: как мы видели, модуль m должен быть достаточно большим, чтобы результат res определялся однозначно по его остатку res m (m > res). Поэтому при работе с большим m мы используем несколько модулей, кодирующих целые числа x (0 6 x 6 m − 1) в соответ- ствии с китайской теоремой об остатках. Для вычисления заданного выражения f (i 1 , i 2 , . . . , i h ), зависящего от це- лочисленных аргументов i 1 , i 2 , . . . , i h , сначала вычисляем f m k (i 1k , i 2k , . . . , i hk ), где i jk — остаток от деления i j на m k (j = 1, 2, . . . , h, k = 1, 2, . . . , n) для ко- ротких модулей m k . При условии, что выражения f m k определены над Z m k , вычисляем их над Z m k и получаем эквивалентные результаты res m k , k = 1, 2, . . . , n. В завершение, пользуясь китайским алгоритмом, получаем окончательный результат res. Модули m k выбираются таким образом, чтобы m 1 · m 2 · . . . · m n > res. Если дана положительная оценка на res, то ищет- ся наименьшее неотрицательное решение системы уравнений по китайскому алгоритму, если же оценивается |res|, то ищется наименьшее по абсолютной 110 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Z Выражение (f ) −−−−→ Z m k Эквивалентное выражение (f m k ) y Вычисление над Z y Вычисление над Z m k Результат (res) ←−−−− Эквивалентный результат (res m k ) Рис. 3.4 величине решение. На рис. 3.4 представлена диаграмма, иллюстрирующая приведенный алгоритм. Рассмотрим более подробно арифметику нескольких модулей. Описанные в § 3.2 системы счисления являются линейными, позиционными и весовыми. Это означает, что всем позициям соответствуют веса, зависящие от одного основания P : P 0 , P 1 , P 2 и т. д. Вместо этого многомодульная система счис- ления использует взаимно простые позиционные основания, m 1 , m 2 , . . . , m n Это позволяет однозначно представлять m 1 · m 2 · . . . · m n различных чисел x в виде вектора остатков [a 1 , a 2 , . . . , a n ] относительно вектора оснований β = [m 1 , m 2 , . . . , m n ], где x ≡ a i (mod m i ), i = 1, 2, . . . , n. Как и в случае одного модуля, мы можем определить наименьшую неотрицательную чис- ловую систему (которую будем называть стандартным набором остат- ков) и при условии, что все модули нечетные, наименьшую по абсолютной величине числовую систему или симметричную систему остатков относи- тельно данного вектора оснований β. Если [a 1 , a 2 , . . . , a n ] — стандартный на- бор остатков числа x относительно вектора оснований β = [m 1 , m 2 , . . . , m n ], то запишем x (mod β) = [a 1 , a 2 , . . . , a n ]. Пример 3.9.5. Если n = 3, m 1 = 3, m 2 = 5, m 3 = 7, то в этой системе с помощью остатков можно представить 3· 5 · 7 = 105 различных чисел. Век- тор [2, 3, 1] однозначно определяет десятичное число 8 в неотрицательной системе остатков относительно вектора оснований β = [3, 5, 7]. В симмет- ричной системе число 8 представляется вектором [−1, −2, 1]. Имеем 8 (mod β) = [2, 3, 1]. ¤ Из китайской теоремы об остатках вытекает Теорема 3.9.1. Два целых числа n 1 и n 2 имеют одинаковые стандарт- ные наборы остатков относительно вектора оснований β = [m 1 , m 2 , . . . , m n ] тогда и только тогда, когда n 1 ≡ n 2 (mod m 1 m 2 . . . m n ). ¤ 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 111 Пример 3.9.6. Рассмотрим вектор оснований β = [3, 5, 7]. Так как 9 ≡ 114 (mod 3 · 5 · 7), то 9 (mod β) = [0, 4, 2] = 114 (mod β). ¤ Из теоремы 3.9.1 следует существование биекции между множествами Z β {k (mod β) | k ∈ Z} и Z M , где M = m 1 · m 2 · . . . · m n . Более того, из китайской теоремы об остатках следует Теорема 3.9.2. Алгебры hZ β ; +, ·i и hZ M ; +, ·i являются изоморфными конечными коммутативными кольцами. ¤ Следовательно, многомодульная арифметика hZ β ; +, ·i эквивалентна арифметике hZ M ; +, ·i по модулю M. Главное преимущество многомодульной числовой системы состоит в от- сутствии переносов при выполнении операций сложения и умножения. Ариф- метика замкнута в каждой позиции, т. е. арифметические действия выполня- ются покоординатно. Поэтому сложение и умножение длинных целых чисел можно выполнять так же быстро, как и коротких чисел. Для выполнения деления определим элемент b −1 (mod β), обрат- ный к элементу b = [b 1 , b 2 , . . . , b n ] по модулю вектора оснований β = [m 1 , m 2 , . . . , m n ], следующим образом: b −1 (mod β) = [b −1 1 (mod m 1 ), b −1 2 (mod m 2 ), . . . , b −1 n (mod m n )]. Теперь, если a = [a 1 , a 2 , . . . , a n ], то a b (mod β) = a · b −1 (mod β) = = [a 1 · b −1 1 (mod m 1 ), a 2 · b −1 2 (mod m 2 ), . . . , a n · b −1 n (mod m n )]. Как и в случае одного модуля, если b не делит a при соответствующей интерпретации в кольце целых чисел, то результат не может быть проин- терпретирован без дополнительной информации. Однако он допустим в ка- честве промежуточного результата. Основная трудность при работе с многомодульными числовыми систе- мами заключается в сравнении величины целых чисел. Конечно, можно ис- пользовать симметричную систему остатков, вычесть из одного числа другое и затем определить знак разности. К сожалению, проблема этим не решает- ся, поскольку остатки в симметричной системе не несут информации о знаке числа. Один из способов определения знака числа x состоит в обратном пре- образовании к обычному виду, что разрушает саму идею многомодульной |