Дискретная математика. Ерош И.Л - 129 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

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 лет назад теория чисел считалась одним из «чистых» разде
лов математики, «не запятнавших» себя какимилибо техническими
приложениями. Этот раздел математики изучался только на механи
коматематических факультетах университетов, в технических вузах

Страницы