14.5.3.2. Как вычислить е

Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.5.3.2. Как вычислить е

Для вычисления е используется разновидность алгоритма Евклида вычисления НОД  и d. Сначала вычисляем последовательность значений x0, x1, х2, ..., где x0 =, x1= d, а хi+1= хi-1  по модулю xi, пока не будет получено xk = 0. Тогда НОД (x0, x1) = хk-1.  Для каждого xi  вычисляются числа аi и bi, при которых хi= аi x0 + bi x1 . Если xk-1= 1, то bk-1 мультипликативное обратное к х1по модулю х0. Если bk-1отрицательное число, решением является bk+1+.

Пример 14.5. Вычисление е с помощью d и

Для предыдущего примера, в котором р = 47, q = 59, п = 2773 и d выбрано равным 157, примените алгоритм Евклида для проверки, что е = 17.

Решение

i

xi

ai

bi

yi

0

2668

1

0

 

1

157

0

1

16

2

156

1

-16

1

3

1

-1

17

 

Здесь

Следовательно,

e = b3=17.









© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.
E-mail: formyneeds@yandex.ru