ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2019
Просмотров: 12426
Скачиваний: 24
96
поскольку результат деления
a
на
n
— это два целых числа,
q
и
r
. Мы будем
называть это
уравнением деления
.
Пример 2.2
Предположим, что
a = 255
, а
n = 23
. Мы можем найти
q = 11
и
r = 2
,
используя алгоритм деления, мы знаем из элементарной арифметики — оно
определяется, как показано на
Рис. 2.3.
Пример 2.2, нахождение частного и остатка
Большинство компьютерных языков может найти частное и остаток,
используя заданные языком операторы. Например, на языке C
оператор
"/"
может найти частное, а оператор
"%"
— остаток.
Два ограничения
Когда мы используем вышеупомянутое уравнение деления в
криптографии, мы налагаем два ограничения. Первое требование: чтобы
делитель был положительным целым числом (
n > 0
). Второе требование:
чтобы остаток был неотрицательным целым числом (
r > 0
показывает эти требования с двумя указанными ограничениями.
Рис. 2.4.
Алгоритм деления целых чисел
Пример 2.3
Предположим, мы используем компьютер или калькулятор,
а
r
и
q
отрицательны, при отрицательном
a
. Как можно сделать, чтобы
выполнялось ограничение, что число
r
должно быть положительным?
Решение простое: мы уменьшаем значение
q
на
1
и добавляем значение
n
к
r
,
чтобы
r
стало положительным.
Мы уменьшили (
–23
), получили (
–24
) и добавили
11
к (
–2
), чтобы
получить
+ 9
. Полученное равенство эквивалентно исходному.
Граф уравнения деления
97
Мы можем изобразить рассмотренные выше уравнения с двумя
ограничениями на
n
и
r
показывает случай, когда число
a
положительно;
второй — когда
отрицательно.
Рис. 2.5.
Граф алгоритма деления
Граф начинается с нуля и показывает, как мы можем достигнуть точки,
представляющей целое число
a
на линии. В случае положительного
a
мы
должны перемещаться на величину
направо и затем добавить
дополнительную
величину
r
в том же самом направлении. В случае
отрицательного
a
мы должны двигаться на величину
налево
(число
q
в этом случае отрицательно) и затем дополнять число
r
в
противоположном для указанного выше движения направлении. В обоих
случаях значение
r
положительно.
Теория делимости
Теперь кратко обсудим
теорию делимости
— тема, с которой мы часто
сталкиваемся в криптографии. Если
a
не равно нулю, а
r = 0
, в равенстве
деления мы имеем
a = q x n
Мы тогда говорим, что
a
делится на
n
(или
n
— делитель
a
). Мы можем
также сказать, что
a
делится без остатка на
n
. Когда мы не интересуемся
значением
q
, мы можем записать вышеупомянутые отношения как
n|a
. Если
остаток не является нулевым, то
n
не делится, и мы можем записать
отношения как
n†a
.
Пример 2.4
a. Целое число
4
делит целое число
32
, потому что
. Это
можно отобразить как
4|32
. Число
8
не
делит число
42
, потому
что
. В этом уравнении число
2
— остаток. Это можно
отобразить как
8†42
.
Пример 2.5
98
а. Отображение делимости
13|78
,
7|98
,
–6|24
,
4|44
, и
11 | (–33)
.
б. Отображение неделимости
13†27
,
7†50
, –
6†23
,
4†41
, и
11†(–32)
.
Свойства
Следующие несколько свойств теории делимости. Доказательства
заинтересованный читатель может проверить в приложении Q.
Свойство 1
: если
a|1
, то
a=±1
.
Свойство 2
: если
a|b
и
b|a
, то
a=±b
Свойство 3
: если
a|b
и
b|c
, то
a|c
Свойство 4
: если
a|b
и
a|c
, то
a|(m x b + n x c)
, где
m
и
n
—
произвольные целые числа.
Пример 2.6
а. Если
3|15
и
15|45
то, согласно третьему свойству,
3|45
.
б. Если
3|15
и
3|9
, то, согласно четвертому свойству,
,
что означает
3|66
.
Все делители
Положительное целое число может иметь больше чем один делитель.
Например, целое число
32
имеет шесть делителей:
1
,
2
,
4
,
8
,
16
и
32
. Мы
можем упомянуть два интересных свойства делителей положительных целых
чисел.
Свойство 1
: целое число
1
имеет только один делитель — само себя.
Свойство 2
: любое положительное целое число имеет по крайней мере
два делителя —
1
и само себя (но может иметь больше).
Наибольший общий делитель
Одно целое число, часто необходимое в криптографии, —
наибольший общий делитель
(
НОД
) двух положительных целых чисел.
Два положительных целых числа могут иметь много общих делителей, но
только один наибольший общий делитель. Например, общие делители
чисел
12
и
140
есть
1
,
2
и
4
. Однако наибольший общий делитель —
4
Рис. 2.6.
Общие делители двух целых чисел
99
Наибольший общий делитель (НОД) двух положительных целых чисел
— наибольшее целое число, которое делит оба целых числа.
Алгоритм Евклида
Нахождение
наибольшего общего делителя
двух положительных целых
чисел путем составления списка всех общих делителей непригодно для
достаточно больших чисел.
К счастью, больше чем 2000 лет назад математик по имени Эвклид
разработал алгоритм, который может найти наибольший общий делитель
двух положительных целых чисел.
Алгоритм Евклида
основан
на
следующих двух фактах (доказательство см. в приложении Q):
Факт 1
:
НОД (a, 0) = a
Факт 2
:
НОД (a, b) = НОД (b, r)
, где
r
— остаток от деления
a
на
b
Первый факт говорит, что если второе целое число —
0
, наибольший
общий делитель равен первому числу. Второй факт позволяет нам изменять
значение
a
на
b
, пока
b
не станет
0
. Например, вычисляя
НОД (36, 10)
, мы
можем использовать второй факт несколько раз и один раз первый факт, как
показано ниже.
НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)
Другими словами,
НОД (36, 10) = 2
,
НОД (10, 6) = 2
, и так далее. Это
означает, что вместо вычисления
НОД (36, 10)
мы можем найти
НОД (2,
0)
показывает, как мы используем вышеупомянутые два факта,
чтобы вычислить
НОД (a, b)
.
Рис. 2.7.
Алгоритм Евклида.
100
Для определения НОД мы используем две переменные,
r
1
и
r
2
, чтобы
запоминать изменяющиеся значения в течение всего процесса. Они имеют
начальное значение
a
и
b
. На каждом шаге мы вычисляем остаток от
деления
r
1
на
r
2
и храним результат в виде переменной
r
. Потом заменяем
r
1
на
r
2
и
r
2
на
r
и продолжаем шаги, пока
r
не станет равным
0
. В этот момент
процесс останавливается и
НОД (a, b)
равен
r
1
.
Пример 2.7
Нужно найти наибольший общий делитель
2740
и
1760
.
Решение
Применим вышеупомянутую процедуру, используя таблицу. Мы
присваиваем начальное значение
r
1
2740
и
r
2
значение
1760
. В таблице также
показаны значения
q
на каждом шаге. Мы имеем
НОД (2740, 1760) = 20
.
q
r
1
r
2
r
2
740
1
760
980
1
1
760
9
80
780
1
9
80
7
80
200
3
7
80
2
00
180
1
2
00
1
80
20
9
1
80
2
0
0
2
0
0
Расширенный алгоритм Евклида
Даны два целых числа
a
и
b
. Нам зачастую надо найти другие два
целых числа,
s
и
t
, такие, которые
s x a + t x b = НОД (a,b)
Расширенный алгоритм Евклида
может вычислить
НОД (a, b)
и в то
же самое время вычислить значения
s
и
t
. Алгоритм и процесс такого