Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Операции над вычетами

В криптографии наибольший интерес представляют три бинарные операции в приложении к множеству целых чисел. Для целых чисел определены три общие бинарные операции — сложение, вычитание и умножение.

Теорема 5.9

Для вычетов имеют место следующие утверждения:

  • 1) если а = Ь(тобт) ukeZ,mok?a = k? Ь(то6т);
  • 2) если к ? а = к ? ?(тос!т) и числа к, т взаимно просты, то а = /)(тос1т);
  • 3) если а = 6(тос1 т) икеМ,тока = к- Ь(то6к ? т);
  • 4) если к ? а = к • 6(тос1 к ? т) и к, т е N, то а = 6(тос1 т)
  • 5) если а = Ь(тодт)и с = с/(тос1т), то а ± с = Ь ± с/(тос1т);
  • 6) если а = Ь(тобт) и с = с/(тос1т), то а ? с = Ь ? д(тобт);
  • 7) если а = Ь(тодт)и п е Л^, тоап = Ь"(тобт).

Теорема 5.10

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

то

а + b = c(mod т), а = с - <6(mod т).

Теорема 5.11

В сравнениях по модулю т можно отбрасывать или добавлять слагаемые, делящиеся на число т, т.е. если, например, с:т и а = Z>(mod т), то а ± с = Z>(mod т) или а = b ± c(mod т).

Обратимые вычеты

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

Аддитивная инверсия

В Zn два числа а и b аддитивно инверсны друг другу, если Ь- п- а. Например, а + b = 0(mod/7).

В Zn аддитивная инверсия числу а может быть вычислена как Ь = п - а. Например, аддитивная инверсия 4 в Zl0 равна 10-4 = 6.

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

Задача 5.1

Найти все взаимно обратные пары по сложению в Z10.

Решение.

Даны шесть пар аддитивных инверсий — (0, 0), (1,9), (2, 8), (3, 7), (4, 6) и (5, 5). В этом списке 0 — инверсия самому себе; так же и 5. Обратите внимание: аддитивные инверсии обратны друг другу; если 4 — аддитивная инверсия числу 6, тогда 6 — также аддитивная инверсия числу 4.

Мультипликативная инверсия

В Zn два числа а и b мультипликативно инверсны друг другу, если а ? b = l(mod«).

Например, если модуль равен 10, то мультипликативная инверсия 3 есть 7. Другими словами, мы имеем (3 • 7)mod 10 = 1.

В модульной арифметике целое число может или не может иметь мультипликативную инверсию. Целое число и его мультипликативная инверсия сравнимы с единицей по модулю п.

Может быть доказано, что а имеет мультипликативную инверсию в Zn, если только NOD{n, а) = 1. В этом случае говорят, что awn взаимно простые.

Задача 5.2

Найти мультипликативную инверсию 8 в Z10.

Решение.

Мультипликативная инверсия не существует, потому что NOD(, 8) = 2 Ф 1. Другими словами, мы не можем найти число между 0 и 9 такое, что при умножении на 8 результат сравним с единицей по mod 10.

Задача 5.3

Найти все мультипликативные инверсии в Z10.

Решение.

Есть только три пары, удовлетворяющие условиям существования мультипликативной инверсии: (1, 1); (3, 7) и (9, 9). Числа 0, 2, 4, 5, 6 и 8 не имеют мультипликативной инверсии.

Мы можем проверить, что

(1 • l)mod 10 = 1(3 • 7)mod 10 = 1(9 • 9)mod 10 = 1.

Задача 5.4

Найти все мультипликативные обратные пары в Z11.

Решение.

Мы имеем следующие пары: (1, 1); (2, 6); (3, 4); (5, 9); (7, 8) и (10, 10). При переходе от Zl0 к Z, | число пар увеличивается. При Zx, NOD( 1, а) = 1 (взаимно простые) для всех значений а, кроме 0. Это означает, что все целые числа от 1 до 10 имеют мультипликативные инверсии.

Целое число а в Zn имеет мультипликативную инверсию тогда и только тогда, если NOD(n, а) = l(mod п).

 
<<   СОДЕРЖАНИЕ   >>