|
|
|
|
|
|
|
Построение корней из единицы в поле |
129 |
|||||||
Пусть задано поле Fq и первообразный элемент поля b. |
|
|
|
|
|||||||||||
При |
заданном |
y Fq* , |
найти |
целое |
x : |
0 ≤ x < q −1, |
такое, |
что |
|||||||
выполняется равенство y = bx . |
|
|
|
|
|
|
|
|
|
|
|
||||
Пример. Пусть |
q =17 , |
b =3. Элемент b - |
первообразный корень поля |
||||||||||||
вычетов по модулю 17. Очевидно, |
если |
q |
является |
простым |
числом, то |
||||||||||
уравнение y = bx |
в поле является сравнением вида y ≡bx |
modq . |
|
|
|
||||||||||
Число |
q −1 |
является |
гладким, |
т.к. |
q −1 = 24 , т.е. его |
единственный |
|||||||||
простой делитель |
p = 2 мал. |
|
|
|
|
|
|
|
|
|
|
|
|||
Пусть |
каноническое |
разложение |
q −1 |
имеет |
вид: |
q −1 =∏pa . |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p |
|
Обозначим количество различных простых в этом разложении через n . |
|
|
|||||||||||||
Пусть m- максимальное простое число в разложении q −1. Для удобства |
|||||||||||||||
записи введем также дополнительное обозначение u = q −1. |
|
|
|
|
|||||||||||
Мы постоянно будем пользоваться тем фактом, что любой ненулевой |
|||||||||||||||
элемент поля g F* |
удовлетворяет условию gq−1 |
=1, так что gu =1. |
|
|
|||||||||||
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
10.2. Построение корней из единицы в поле |
|
|
|
|
|
||||||||||
Построим таблицу R |
размером |
n×m , |
строкам |
которой |
присвоим в |
||||||||||
качестве меток простые числа |
p |
из разложения |
q −1. |
Заполним сначала ее |
|||||||||||
нулями. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В строку |
с |
меткой |
|
p |
поместим |
элементы |
поля |
|
r |
=b ju p , |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
p, j |
|
|
(j = 0,K, p −1).