ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2019
Просмотров: 12429
Скачиваний: 24
106
Целые числа в наборе
[0]
все
дают остаток
0
при
делении
на
5
(сравнимы по модулю
5
). Целые числа в наборе
[1]
все дают
остаток
1
при делении на
5
(сравнимы по модулю
5
), и так далее. В каждом
наборе есть один элемент, называемый наименьшим (неотрицательным)
вычетом. В наборе
[0]
это элемент
0
; в наборе
[1]
—
1
, и так далее. Набор,
который показывает все наименьшие вычеты:
Z
5
= {0, 1, 2, 3, 4}
. Другими
словами, набор
Z
n
— набор всех
наименьших вычетов по модулю n
.
Круговая система обозначений
Понятие "сравнение" может быть лучше раскрыто при использовании
круга в качестве модели. Так же, как мы применяем линию, чтобы показать
распределение целых чисел в
Z
, мы можем использовать круг, чтобы
показать распределение целых чисел в
Z
n
.
banisi@mail.ru
Рис. 2.12.
Сравнение использования диаграмм для Z и Zn
позволяет сравнить два этих подхода. Целые числа
от
0
до
n–1
расположены
равномерно
вокруг
круга.
Все
целые
числа,
сравнимые по модулю
n
, занимают одни и те же точки в круге.
Положительные и отрицательные целые числа от
Z
отображаются в круге
одним и тем же способом, соблюдая симметрию между ними.
Пример 2.15
Мы пользуемся сравнением по модулю в нашей ежедневной жизни;
например, мы применяем часы, чтобы измерить время. Наша система часов
использует арифметику по модулю
12
. Однако вместо
0
мы берем отсечку
12
,
так что наша система часов начинается с
0
(или
12
) и идет до
11
. Поскольку
наши сутки длятся
24
часа, мы считаем по кругу два раза и обозначаем
первое вращение как утро до полудня, а второе — как вечер после полудня.
Операции в Zn
Три бинарных операции (
сложение, вычитание
и
умножение
),
которые мы обсуждали для
Z
, могут также быть определены для набора
Z
n
.
107
Результат, возможно, должен быть отображен в
Z
n
с использованием
операции по модулю, как это показано на
Рис. 2.13.
Бинарные операции в Zn
Фактически применяются два набора операторов: первый набор — один из
бинарных операторов
; второй — операторы по модулю. Мы должны
использовать круглые скобки, чтобы подчеркнуть порядок работ. Как показано на
, входы (
a
и
b
) могут быть членами
Z
или
Z
n
.
Пример 2.16
Выполните следующие операторы (поступающие от
Z
n
):
а. Сложение
7
и
14
в
Z
15
б. Вычитание
11
из
7
в
Z
13
в. Умножение
11
на
7
в
Z
20
Решение
Ниже показаны два шага для каждой операции:
(14+7) mod 15 -> (21) mod 15 = 6
(7–11) mod 13 -> (-4) mod 13 = 9
(7x11) mod 20 -> (77) mod 20 = 17
Пример 2.17
Выполните следующие операции (поступающие от
Z
n
):
a. Сложение
17
и
27
в
Z
14
b. Вычитание
43
из
12
в
Z
13
c. Умножение
123
на
-10
в
Z
19
Решение
Ниже показаны два шага для каждой операции:
(17 + 27) mod 14 -> (44) mod 14 = 2
(12 – 43) mod 13 -> (–31) mod 13 = 8
108
((123) x (–10)) mod 19 -> (–1230) mod 19 = 5
Свойства
Мы уже упоминали, что два входа для трех бинарных операторов в сравнении по
модулю могут использовать
данные
из
Z
или
Z
n
. Следующие свойства позволяют нам
сначала отображать два входа к
Z
n
(если они прибывают от
Z
) перед выполнением этих
трех бинарных операторов
. Заинтересованные читатели могут найти
доказательства для этих свойств в приложении Q.
Рис. 2.14.
Свойства оператора mod
Первое свойство
:
(a + b) mod n = [(a mod n) + (b mod n)] mod n
Второе свойство
:
(a – b) mod n = [(a mod n) - (b mod n)] mod n
Третье свойство
:
(a x b) mod n = [(a mod n) x (b mod n)] mod n
показывает процесс до и после применения указанных
выше свойств. Хотя по рисунку видно, что процесс с применением этих
свойств более длинен, мы должны помнить, что в криптографии мы имеем
дело с очень большими целыми числами. Например, если мы умножаем
очень большое целое число на другое очень большое целое число, которое
настолько большое, что не может быть записано в компьютере, то
применение вышеупомянутых свойств позволяет уменьшить первые два
операнда прежде, чем начать умножение. Другими словами, перечисленные
свойства позволяют нам работать с меньшими числами. Этот факт станет
понятнее при обсуждении экспоненциальных операций в последующих
лекциях.
Пример 2.18
Следующие примеры показывают приложение вышеупомянутых
свойств.
1.
2.
3.
109
Пример 2.19
В арифметике мы часто должны находить остаток от степеней
числа
10
при делении на целое число. Например, мы должны найти
10 mod
3
,
10
2
mod 3
,
10
3
mod 3
, и так далее. Мы также должны найти
10 mod
7
,
10
2
mod 7
,
10
3
mod 7
, и так далее. Третье свойство модульных операторов,
упомянутое выше, делает жизнь намного проще.
10
n
mod x = (10 mod x)
n
Применение третьего свойства n раз.
Мы имеем
10 mod 3 = 1 -> 10
n
mod 3 = (10 mod 3)
n
= 1
10 mod 9 = 1 -> 10
n
mod 9 = (10 mod 9)
n
= 1
10 mod 7 = 3 -> 10
n
mod 7 = (10 mod 7)
n
= 3
n
mod 7
Пример 2.20
Мы уже говорили, что в арифметике остаток от целого числа,
разделенного на
3
, такой же, как остаток от суммы деления его десятичных
цифр. Другими словами, остаток от деления
6371
равен остатку от деления
суммы его цифр
(17)
, на
3
. Мы можем доказать, что это утверждение
использует свойства модульного оператора. Запишем целое число как сумму
его цифр, умноженных на степени
10
.
a = a
n
10
n
+………+ a
1
10
1
+ a
0
10
0
Например: 6371 = 6 x 10
3
+ 3 x 10
2
+ 7 x 10
1
+ 1 x 10
0
Теперь мы можем применить модульную операцию к двум сторонам
равенства и использовать результат предыдущего примера, где
остаток
10
n
mod 3
равен
1
.
a mod 3 = (a
n
x 10
n
+…+ a
1
x 10
1
+ a
0
x 10
0
) mod 3
= (a
n
x 10
n
) mod 3 +…+ (a
1
x 10
1
) mod 3 + (a
0
x 10
0
mod 3) mod 3
= (a
n
mod 3) x (10
n
mod 3) +…+ (a
1
mod 3) x (10
1
mod 3) +
(a
0
mod 3) x (10
0
mod 3) mod 3
= ((a
n
mod 3) +…+ (a
1
mod 3) + (a
0
mod 3)) mod 3
= (a
n
+…+ a
1
+ a
0
) mod 3
4.3. Функция Эйлера
Функция Эйлера
, равна количеству
, который впервые использовал ее в своих работах по
Число 1 взаимно просто с любым числом. При этом считается, что
1
)
1
(
.
Если мы попробуем просто проверять все числа, меньшие
n
, на
взаимную простоту с
n
, то при больших
n
программа будет работать часами,
110
а то и сутками. Попробуем посмотреть на задачу внимательнее. Первое, что
мы заметим – это то, что простое число всегда взаимно просто со всеми
числами, меньше себя, значит, для простых
n
,
1
)
(
n
n
.
(1)
Такая операция гораздо легче, чем производить перебор. Далее можно
рассмотреть случай, когда
n
имеет единственный простой делитель
p
,
повторенный несколько раз, т.е.
k
p
n
(случай, рассмотренный выше, есть
частный случай данного, при
k
=1). Очевидно, что такое число будет взаимно
просто со всеми числами, меньше себя, кроме чисел, кратных
p
. Всего таких
чисел
1
k
k
p
p
.
1
)
(
k
k
k
p
p
p
Таким образом, мы можем обобщить выражение (1) для простых
p
:
1
)
(
k
k
k
p
p
p
. (2)
Заметим еще, что, если некоторые числа
p
и
q
взаимно просты, то
число
pq
будет взаимно просто со всеми числами, меньшими себя, кроме
тех, которые кратны хотя бы одному делителю
p
или хотя бы одному
делителю
q
. Отсюда имеем еще одно свойство функции Эйлера, а именно:
для взаимно простых
p
и
q
:
)
(
)
(
)
(
q
p
pq
. (3)
Предположим, что мы разложили
n
на простые множители и записали
в каноническом виде:
k
p
p
p
n
...
2
1
, где все
p
i
различные простые числа.
Тогда, применив (2) и (3), получаем, что при
k
p
p
p
n
...
2
1
, где
p
простые
числа,
)
)...(
)(
(
)
(
1
1
2
2
1
1
1
k
k
p
p
p
p
p
p
n
. (4)
Вычисление функции Эйлера
Пусть
представленное
в
виде
Тогда функция Эйлера может быть вычислена по формуле