Составители:
Каждое число от 1 до 10 может быть представлено как 2
x
(mod p).
Для значения p = 11 образующими являются числа 2, 6, 7 и 8.
Другие числа не являются образующими. Например, образующей
не является число 3, поскольку не существует решения 3
x
= 2 (mod
11). В общем случае, установить, является ли данное число
образующей, нелегко. Однако задача упрощается, если известно
разложение p - 1 на множители. Пусть q
1
, q
2
,…, q
n
– это простые
множители p - 1.
Чтобы проверить, является ли число g образующей по модулю p,
необходимо вычислить: g
(p-1)/q
mod p для всех значений q = q
1
, q
2
...,q
n
.
Если это число равно 1 для некоторого значения q, то g не является
образующей. Если для всех значений q рассчитанное значение не
равно 1, то g - образующая.
Пусть, например, р = 11. Простые множители p - 1 = 10 равны 2 и
5. Чтобы проверить, что число 2 - образующая, вычислим:
2
(11-1)/2
(mod 11) = 10, 2
(11-1)/5
(mod 11) = 4
Ни один из ответов не равен 1, поэтому 2 - это образующая. Теперь
проверим, является ли образующей число 3:
3
(11-1)/2
(mod 11) = 1, 3
(11-1)/5
(mod 11) = 9.
Следовательно, 3 — это не образующая.
П.6. Квадратичные вычеты
Если a - квадратичный вычет, то сравнение x
2
≡ a(mod p) имеет два
решения: +x и –x, т.е. a имеет два квадратичных корня по модулю p.
Все квадратичные вычеты [5,25] находят возведением в квадрат
элементов 1, 2, 3, …, (p - 1)/2.
Не все значения a < p являются квадратичными вычетами. Если a –
квадратичный вычет по модулю p, то a имеет два квадратных корня:
один
корень между 0 и (p - 1)/2, другой корень между
(p –1 )/2 и (p - 1). Если n – произведение двух простых чисел p и q, т.е.
существуют точно (p - 1)(q – 1)/4 квадратичных вычетов по модулю p,
164
Страницы
- « первая
- ‹ предыдущая
- …
- 160
- 161
- 162
- 163
- 164
- …
- следующая ›
- последняя »
