Телекоммуникационные технологии. Том 1



         

Системы шифрования - часть 5


За свою историю люди придумали достаточно большое число способов шифрования. Новейшие из них базируются на методиках, заимствованных из теории чисел. По этой причине, прежде чем переходить к следующему разделу, введем некоторые определения.

Конгруентность. a конгруентно b по модулю n (a є nb), если при делении на n a и b, получается идентичный остаток. Так 100 є 1134 (100 и 34 при делении на 11 дают остаток 1) и –6 є 810 (ведь –6 =8(-1)+2). Мы всегда имеем a є nb для некоторого 0 Ј bЈ n-1. Если a єnb и сє d, то справедливы равенства:

a +c є n(b + d) и ac єnbd

Аналогичная процедура для деления не всегда справедлива: 6є 1218 но 3№ 9. Приведенные здесь и далее математические определения и обоснования взяты из: http://lglwww.epfl.ch/~jkienzle/digital/node20.html.

Необходимо также вспомнить о знакомом всем со школьной скамьи понятии наибольшего общего делителя. Для a и b число (a,b) является наибольшим общим делителем, который делит a и b без остатка:

(56,98)=14; (76,190)=38

Теорема 1. Для любых a,b существуют целые числа x,y, для которых ax+by=(a,b). В данной статье не приводится доказательств представленных утверждений, их следует искать в книгах по дискретной математике.

В этом можно убедиться, решая уравнение 30x+69y=3 путем последовательных упрощающих подстановок (ищется целочисленное решение:

30x+69y=3

30x'+9y=3[x'=x+2y]
3x'+9y'=3[y'=y+3x']
3x"+0y'=3[x"=x'+3y']

Легко видеть, что x"=1, y'=0 является решением окончательного уравнения. Мы можем получить решение исходного уравнения путем обратной подстановки.

x'=x"-3y'=1 y=y'-3x'=-3 x=x'-1y=7

Мы можем решить уравнение вида 30x+69y=15 путем умножения нашего решения: y=-15, x=35. Должно быть ясно, что уравнение не будет иметь целочисленного решения, если 15 заменить на что-то некратное (30,69)=3.

Все другие целочисленные решения 30x+69y=15 могут быть получены, варьируя первое решение:

y=-15+(30/3)t x=35 –(69/3)t для целого t

Если мы проделаем то же для произвольного равенства ax+by=(a,b), мы возможно получим один из коэффициентов равным нулю, а другой – (a,b).


Содержание  Назад  Вперед