Составители:
Рассмотрим пример из [17]. Выберем небольшие числовые
значения. Если n = 35 (n – произведение 5
⋅
7), то возможные
квадратичные вычеты будут следующими:
1: x
2
≡ 1 (mod 35) имеет решения: x = 1, 6, 29, 34;
4: x
2
≡ 4 (mod 35) имеет решения: х = 2, 12, 23, 33;
9: x
2
≡ 9 (mod 35) имеет решения: х = 3, 17, 18, 32;
11: x
2
≡ 11 (mod 35) имеет решения: х = 9, 16, 19, 26;
14: x
2
≡ 14 (mod 35) имеет решения: х = 7, 28;
15: x
2
≡ 15 (mod 35) имеет решения: х = 15, 20;
16: x
2
≡ 16 (mod 35) имеет решения: х = 4, 11, 24, 31;
21: x
2
≡ 21 (mod 35) имеет решения: х = 14, 21;
25: x
2
≡ 25 (mod 35) имеет решения: х = 5, 30;
29: x
2
≡ 29 (mod 35) имеет решения: х = 8, 13, 22, 27;
30: x
2
≡ 30 (mod 35) имеет решения: х = 10, 25.
Взаимно простыми с 35 не являются 14, 15, 21,25 и 30, поэтому
они не имеют обратных значений по модулю 35. Число
квадратичных вычетов по модулю 35, взаимно простых с n = p
⋅
q =
5
⋅
7 = 35 ( для которых НОД (х, 35) = 1), равно
(p – 1) (q – 1)/4 = (5 –1) (7 – 1)/4 = 6.
В табл. 4.3 представлены квадратичные вычеты по модулю 35, а
также обратные к
ним значения.
Пользователь А получает открытый ключ K, состоящий из
четырех значений V: {4, 11, 16, 29}, а также секретный ключ K
с
,
состоящий из следующих значений S: {3, 4, 9, 8}.
Таблица 4.3
V
V
-1
S =sqrt (V
-1
)
1 1 1
4 9 3
9 4 2
11 16 4
16 11 9
29 29 8
84
Страницы
- « первая
- ‹ предыдущая
- …
- 80
- 81
- 82
- 83
- 84
- …
- следующая ›
- последняя »
