Составители:
Рубрика:
23
1
a
n
=
,
а вторая половина будет удовлетворять условию
1
a
n
=−
.
Более того, из чисел a, удовлетворяющих условию
1
a
n
=
,
половина будет квадратичными вычетами, а именно такие числа a, для
которых
1
aa
pq
==
.
Другая половина, для которых
1
aa
pq
==−
,
будет квадратичными невычетами.
П р и м е р . Пусть p = 3, q = 5, тогда n = 15. Квадратичными выче-
тами по модулю 15 будут числа a = 1 и 4. Квадратичными невычетами
будут числа a = 2 и 8.
Если известно, что некоторое a является квадратичным вычетом по
модулю n = pq, но простые числа p и q неизвестны, то решение сравне-
ния (нахождение x из сравнения): x
2
≡ a mod n является важной, но очень
сложной задачей в криптографии с открытым ключом.
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
