Методы и средства защиты информации



              

Необходимые сведения из элементарной теории чисел


1. Простым числом называется натуральное число, имеющее только два неравных натуральных делителя.

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

3.     Наибольшим общим делителем двух целых чисел НОД(a,b) (или (a,b)) называется наибольшее целое, на которое без остатка делится как a, так и b.

4.     Пусть a > b и d = (a,b). Тогда существуют целые x и у, являющиеся решением уравнения xa + yb = d. Если d = 1, то a и b называются взаимно простыми.

5.     Наибольший общий делитель двух чисел можно найти с помощью алгоритма Эвклида. Для этого a делится с остатком на b, т.е. а = q1b + r1. Далее вместо a и b, рассматриваем соответственно b и r1: b = q2r1+ r2. На следующем шаге роль b и r1, играют r1 и r2: r1 = q3r2

+ r3 и т.д. Процесс заканчивается на некотором шаге k+1, для которого rk+1= 0. Тогда НОД(a,b) = rk. Рассмотрим пример.

Найти НОД(1547, 560)

1547 = 2 х

560 + 427

560 = 1 х 427 + 133

427 = 3 х 133 + 28

133 = 4 х 28 + 21

28 = 1 х 21 + 7

21 = 3 х 7 + 0

НОД(1547,560)=7

6.     Для решения уравнения xa + yb = d можно использовать данные, полученные в каждом шаге алгоритма Эвклида, двигаясь снизу вверх, с помощью выражения остатка через другие элементы, используемые в соответствующем шаге. Например, из r2 = q4r3

+ r4 следует r4 = r2 +q4r3. В последнем равенстве r3 можно заменить, исходя из соотношения r1

= q3r2 + r3, т.е. r4 = r2 – q4(q3r2

– r1). Поэтому r4 = (1 – q4q3)r2

+ q4r1. Таким образом, мы выразили r4 в виде целочисленной комбинации остатков с меньшими номерами, которые, в свою очередь, могут быть выражены аналогично. Продвигаясь “снизу вверх”, в конце концов, мы выразим r4 через исходные числа a и b. Если бы мы начали не с r4, а с rk, то получили бы rk

= xa + yb = d. Рассмотрим пример.

Решить 1547х + 560y = 7

7 = 28 – 1 х 21 = 28 – 1 х (133 — 4 х 28) = 5 х 28 - 1 х 1ЗЗ =



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