А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

(1) m\a, b\m b\a.

Доказательство:

m\a a=ma₁;

b\m m=bm₁ a=bm₁a₁. Обозначив b₁=a₁m₁, получим a=bb₁, причем b\a.

□

(2) Если в равенстве вида k+l+…+n=p+q+…+s относительно всех членов кроме одного известно, что они кратны b, то и один оставшийся член тоже кратен b.

Доказательство:

Не нарушая общности, предположим, что таким членом (относительно кратности которого числу b ничего не известно) является k.

Тогда l₁, …, n₁, p₁, q₁, …, s₁: l=bl₁,…, n=bn₁, p=bp₁, q=bq₁, …, s=bs₁.

Тогда k=p+q+…+s–l–…–n=bp₁+bq₁+…+bs₁–bl₁–…–bn₁=b(p₁+q₁+…+s₁–l₁–…–n₁)

Обозначим k₁= p₁+q₁+…+s₁–l₁–…–n₁. Очевидно, k₁ – целое число, причем k=bk₁ Тогда, по определению делимости, b\k.

□

Кроме того, очевидны следующие свойства:

1) a\0, 1\a, a\a.

2) a\b, b\a a=±b.

3) a\b, a\c a\(bx+cy).

(Доказательство св-ва 3: b=ab₁, c=ac₁ bx+cy=ab₁x+ac₁y=a(b₁x+c₁y))

Теорема деления (теорема о делении с остатком)

единственная пара чисел 0 ≤ r < b: a=bq+r *

Доказательство:

Возьмем q: bq≤a, b(q+1)>a. Такое целое q, очевидно, существует r=a–bq является целым положительным числом как разность двух целых чисел, первое из которых больше второго. Причем выполняется . Построением такого r доказано существование разложения (*).

Теперь докажем единственность разложения (*): предположим, что кроме построенного выше, имеется еще одно разложение числа a:

a=bq₁+r₁, 0≤r₁<b.

Вычтем полученное равенство из равенства (*) почленно. Получим

0=b(q–q₁)+(r–r₁). **

Поскольку b\0, b\b(q–q₁), то по теореме 2, b\(r–r₁).

С другой стороны, 0≤r<b, 0≤r₁<b |r–r₁|<b. Отсюда и из того, что b\(r–r₁), следует, что r–r₁=0, и тогда r=r₁. Подставляя полученное равенство в (**), получаем 0=b(q–q₁).

Но по условию теоремы, b≠0 , тогда q–q₁=0 q=q₁.

Таким образом, оба построенных разложения числа a совпадают, а значит разложение (*) единственно.

□

В разложении (*) число q называются неполным частным, r – остатком от деления a на b.

1.2. Наибольший общий делитель.

Далее будем рассматривать лишь положительные делители чисел.

Общим делителем чисел a₁, a₂,…,a_n называется число d: d\a_i .

Наибольший из всех общих делителей чисел a₁, a₂,…,a_n называется их наибольшим общим делителем (НОД) и обозначается НОД(a₁, a₂,…,a_n) или (a₁, a₂,…,a_n).

Если (a₁, a₂,…,a_n)=1, то числа a₁, a₂,…,a_n называются взаимно простыми.

Если (a_i,a_j)=1 , i≠j , то числа a₁, a₂,…,a_n называются попарно простыми.

Утверждение

Если числа a₁, a₂,…,a_n – попарно простые, то они взаимно простые. (Очевидно.)

Теорема 1

Если b\a совокупность общих делителей a и b совпадает с совокупностью делителей b. В частности, (a,b)=b.

Доказательство:

b\a a=ba₁, тогда d: d\b справедливо d\a (т.е. любой делитель b является также делителем a).

Если l\a, но l не делит b, то l не является общим делителем a и b.

То есть совокупность общих делителей a и b совпадает с совокупностью делителей b. А поскольку наибольший делитель b есть b, и b\a , то (a,b)=b.

□

Теорема 2

Если a=bq+c, то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и c.

В частности, (a,b)=(b,c)

Доказательство:

Пусть m\a, m\b m\c (в силу a=bq+c и теоремы 2 п.1), а значит m – общий делитель b и c.

Пусть l\b, l\c l\a (в силу a=bq+c и теоремы 2 п.1), а значит l - общий делитель a и b.

Получили совпадение совокупности общих делителей a и b и общих делителей b и c.

Пусть теперь d=(a,b) d\a, d\b, а значит, по доказанному выше, d\c. В силу совпадения совокупностей общих делителей и того, что d – наименьший изо всех делителей a и b, не может существовать d₁: d₁>d, d₁\b, d₁\c. Поэтому d=(b,c) (a,b)= (b,c).

□

Алгоритм Евклида (отыскания НОД 2-х чисел)

Пусть a>b. Тогда в силу теоремы делимости находим ряд равенств:

a=bq₁+r₁, 0<r₁<b

b=r₁q₂+r₂, 0<r₂<r₁

r₁=r₂q₃+r₃, 0<r₃<r₂

...…………………

r_n-2=r_n-1q_n+r_n, 0<r_n<r_n-1

r_n–1=r_nq_n+1.

Получение последнего равенства (то есть равенства с разложением без остатка) неизбежно, т.к. ряд b, r₁, r₂, …. – ряд убывающих целых чисел, который не может содержать более b положительных чисел, а значит рано или поздно в этом ряду возникнет «0».

Видим, что общие делители a и b, b и r₁, r₁ и r₂,..., r_n–1 и r_n совпадают с делителями числа r_n (a,b)=(b,r₁)=(r₁,r₂)=…=(r_n-1,r_n)= r_n.

Таким образом, (a,b)=r_n.

Вышеизложенная идея нахождения НОД может быть реализована в виде алгоритма. Ниже приведены несколько вариантов реализации алгоритма Евклида.

Реализация алгоритма Евклида (вариант алгоритма с вычитанием)

Вход: a, b>0.

1. Если a>b Шаг 3

если a<b Шаг 2

если a=b Шаг 5 (выход)

1. Меняем местами a и b.

2. a:=a–b

3. Возвращаемся на Шаг 1.

5. Выход: a – НОД

Ниже приведен пример использования этой реализации алгоритма.

Пример

a=603, b=108

Преобразования алгоритма записаны в таблицу, верхняя строка которой содержит значение переменной a, нижняя – содержимое переменной b. Каждый столбец таблице соответствует состоянию процесса на отдельном шаге.

Ответ: НОД (603,108)=9.

Реализация алгоритма Евклида (вариант алгоритма с делением с остатком)

Вход: a, b >0.

1. Находим разложение a=bq+r, 0≤r<b

2. если r=0 Шаг 5 (выход)

3. a:=b; b:=r.

4. Возвращаемся на Шаг 1

5. Выход: b – НОД.

Пример

a=603, b=108

603=5·108+63

108=1·63+45

63=1∙45+27

45=1∙27+18

27=1∙18+9

18=2∙9+0

Ответ: НОД (603,108)=9.

Бинарный алгоритм Евклида

Этот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 2 или на любую степень двойки является весьма быстрой и простой операцией (в двоичной системе счисления операция деления на 2 есть всего лишь битовый сдвиг вправо).

Учтем, что (2^k∙a,2^s∙b)=2^min(k,s)(a,b).

Алгоритм:

Вход: a, b>0.

1. Представим a и b в виде: ; , где a₁, b₁ – нечетные числа.

k:=min(k₁,k₂).

1. Если a₁>b₁ Шаг 4

a₁< b₁ Шаг 3

a₁= b₁ Шаг 6

1. Меняем местами a₁ и b₁.

2. c:=a₁–b₁=2^s∙c₁ (c₁ - нечетное число)

(Заметим, что с обязательно будет четным, а значит )

5. a₁:= b₁ , b₁:=c₁ . Возвращаемся на Шаг 1.

6. Выход: (a,b)=2^k∙a₁ .

Пример

a=603, b=108

1. a₁=603, k₁=0; b=108=4∙27=2²∙27 k₂=2, b₁=27, k=0

2. a₁=603> b₁=27 Ш4

4. c=603-27=56=64∙9, c₁=9

5. a₁=27; b₁=9 Ш1

1. a₁=27; b₁=9

2. a₁> b₁ Ш4

4. c=a₁–b₁=18=2∙9, c₁=9

5. a₁=9, b₁=9

1. a₁=9, b₁=9, k=0

2. a₁= b₁ Ш6

6. (a,b) = 2º∙9=9

Для НОД справедливы следующие свойства:

1) (am,bm)=m(a,b)

Доказательство:

Доказательство строится, умножая почленно соотношения алгоритма Евклида на m.

2) d – общий делитель чисел a и b

(в частности, ).

Доказательство:

Учитывая, что и – целые числа, из свойства НОД №1 получаем соотношение , что и требовалось.

□

3) (a,b)=1 (ac,b)=(c,b)

Доказательство:

a, b, c выполняется (ac,b)\ac, (ac,b)\b (ac,b)\bc (ac,b)\(ac,bc).

По условию теоремы, в силу взаимной простоты a и b (ac,bc)=c, то есть получили (ac,b)\с.

Характеристики

Список файлов книги