Исследование алгоритма защиты информации RSA. Криптосистемы с открытым ключом. Алгоритм Евклида, страница 4

•  ш/2 кратно одному из двух чисел (р-1) или (q-1) ( для определенности положим р), но не кратно обоим этим числам ,В этом случае всегда выполняется сравнение _а""'^г ■ lmod р , но в 50% попытки сравнения по модулю q будут приводить к (-1).

•  ш/2 не кратно любому из двух чисел (р-1) или (q-1) В этом случае сравнения a^m/1*\mod р или q (««следовательно, п) выполняются в 25% попыток; сравнение a™'²»-lmodpили q выполняется в 25% попыток и в оставшиеся 50% выполняются сравнения а по модулю других простых чисел.

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

Наибольшим общим делителем (НОД) называется всякое целое, делящее одновременно  целые числа а,  Ь„..,1 Обозначается  наибольший  общий

делитель символом НОД(а, b....... 1). Для нахождения НОД чисел, а такж*

для нахождения обратного числа часто используется алгоритм Евклида. Его суть состоит в следующем.

Пусть а и b два положительных целых числа Ь "г а. Делитель а и b является также делителем а и (Ь-а), и наоборот, НОД (а, Ь) = НОД(а, Ь-а).

В свою очередь число b можно представить в следующем виде:

Ь- <;•« + г.    osrsi, таким образом, НОД (а, Ь) - НОД(г, а), если r«Q, то НОД (а, Ь) = а.

Алгоритм вычисления НОД

Пусть а и Ь - положительные целые. Тогда можно составить следующий ряд равенств:

«~bq,+r,,0<г₃<Ь,

b " rjqa +• гj,0<г₃<г₂,

h~ ГзЧз + U.0<Г4<г_э,

12

заканчивающийся, когда получаем некоторое г„ц-0. Рассматривая приведенные выше равенства, можно убедится, что общие делители чисел а и b одинаковы с общими делителями чисел Ь и   r_hдалее одинаковы с

общими делителями чисел г₃, г₃, чисел г₃, и....... чисел r„.i и r_q , наконец, с

делителем одного числа г„.

Отсюда следует, что совокупность общих делителей чисел а и b совпадает с совокупностью делителей их НО Д. Этот НОД равен г_а, т.е. последнему не равному нулю остатку алгоритма Евклида.

Для нахождения обратного числа алгоритм Евклида следует прочитать наоборот.

Пример. Используя алгоритм Евклида,найти обратное число 437'' по модулю 729. Предварительно применим алгоритм Евклида к числам 729 и 437.

729 = 437 + 292;

437 = 292+145;

292=2145+2;

145 = 72-2+1.

НОД(729,437)-1.

Для нахождения обратного числа применим следующую процедуру

1=145-72-2;

= 145-72(292-2145);

= 145-145-72-292;

= 145(437-292)-72-292,

= 145-437-217-292;

= 145-437-217(729-437);

13