Составители:
Рубрика:
129
369 122 247 3 122 122
1,
247 247 122 122 3 3
121212121212
3333334
565656565656
787878787878
т. е. 369 является квадратичным невычетом по модулю 247.
Упражнения.
Определить символы Якоби в следующих случаях:
a)
1815
;
1683
12
34
56
b)
361
;
5515
12
34
56
c)
2197
.
625
12
34
56
Для криптографических систем представляет интерес случай, ког
да n является произведением двух простых чисел p и q, т. е. n = pq.
Требуется определить, является ли некоторое число a квадратичным
вычетом или квадратичным невычетом по модулю n, т. е. существует
ли такое x, что выполняется сравнение x
2
º a mod n?
Некоторое число a будет квадратичным вычетом по модулю n = pq, если
и только если оно будет квадратичным вычетом как по модулю p, так и
по модулю q. Если рассмотреть множество чисел 1, 2, 3,..., n–1 и исклю
чить из него все числа, кратные p и (или) q, то в точности половина из
оставшихся чисел будет удовлетворять условию
1,
a
n
12
3
45
67
а вторая поло
вина будет удовлетворять условию
1.
a
n
12
34
56
78
Более того, из чисел a, удов
летворяющих условию 1,
a
n
12
3
45
67
половина будет квадратичными вычета
ми, а именно такие числа a, для которых
1.
aa
pq
1212
33
4545
6767
Другая половина,
для которых
1,
aa
pq
1212
334
5656
7878
будет квадратичными невычетами.
Пример. Пусть p = 3, q = 5, тогда n = 15. Квадратичными вычетами
по модулю 15 будут числа a = 1 и 4. Квадратичными невычетами будут
числа a = 2 и 8.
Если известно, что некоторое a является квадратичным вычетом по
модулю n = pq, но простые числа p и q неизвестны, то решение сравне
ния (нахождение x из сравнения) x
2
º a mod n является важной, но
очень сложной задачей в криптографии с открытым ключом.
6.2. Использование теории чисел в криптографии
и коррекции ошибок при передаче сообщений
Еще 50 лет назад теория чисел считалась одним из «чистых» разде
лов математики, «не запятнавших» себя какимилибо техническими
приложениями. Этот раздел математики изучался только на механи
коматематических факультетах университетов, в технических вузах
Страницы
- « первая
- ‹ предыдущая
- …
- 127
- 128
- 129
- 130
- 131
- …
- следующая ›
- последняя »