Алгоритм Евклида

Алгоритм Евклида дает правила вычисления наибольшего общего делителя (НОД) 2-х натуральных чисел. (a,b)= d, где d – НОД

НОК – наименьшее общее кратное

[a,b] = k, где k – НОК

Наибольший общий делитель (НОД) чисел а и b - это наибольшее целое число d, на которое и а, и b делятся: d = НОД(а, b). Если НОД(а, b) = 1, то числа а и b взаимно простые.

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

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

a,b – N

Разложим большее через меньшее b< a

…………………….

и

Существует теорема что предпоследний остаток и есть НОД

т.е. – НОД

На основание теоремы сделаем вывод что

НОД необходим в шифрование.

Пример: a= 525, b= 231

		21 -	НОД

Пример2: a=1234, b= 54

1234= 54*22+46

54= 46*1+8

46= 8*5+6

8= 6*1+2

6=2*3+0

Расширенный алгоритм Евклида (РАЕ)

(a,b)=d

d можно разложить по формуле:

a x +b y =d

Дополнительно вычисляются коэффициенты x,y

При нахождение НОД с помощью РАЕ применяются обратные элементы.

, но обратные элементы не всегда существуют.

Пример: a=1234, b= 54

2=8-6*1=8-(46-8*5)=6*8-46=-6(54-46*1)-46 = 6*54-6*46-46=6*54-7*46=6*54-7*(1234-54*22)=6*54-7*1234

x=7; y= 160

Дата добавления: 2014-01-15