Составители:
Рубрика:
22
При вычислении символа Якоби основное сведение выполняется на
основе закона взаимности:
()
()()
11/4
1,
mn
mn
nm
−−
=−
где m и n – нечетные числа большие 2.
Если не выполняется сравнение m ≡ n ≡ 3 mod 4, то
.
mn
nm
=
Если же это сравнение выполняется, то
.
mn
nm
=−
Пример. Определить, является ли число a = 369 квадратичным
вычетом или квадратичным невычетом по модулю 247?
369 ≡ 1 mod 4, поэтому можно вычислить
369 122 247 3 122 2
1.
247 247 122 122 3 3
======−
Таким образом, 369 является квадратичным невычетом по модулю
247.
Упражнения
Определить символы Якоби в следующих случаях
1815 361 2197
a
) б) в) .
1683 5515 625
Для криптографических систем представляет интерес случай, когда
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, то половина из
оставшихся чисел будет удовлетворять условию:
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
