Как найти примитивный элемент поля
Перейти к содержимому

Как найти примитивный элемент поля

  • автор:

VMath

Вспомогательная страница к пункту ☞ ПОЛИНОМЫ, НЕПРИВОДИМЫЕ ПО МОДУЛЮ. Содержание очень близко по смыслу к понятию первообразный корень из раздела ☞ ИНДЕКС (ДИСКРЕТНЫЙ ЛОГАРИФМ).

Примитивные элементы поля

В поле Галуа первообразным корнем степени n из единицы называется элемент $ \mathfrak a $, который удовлетворяет условиям $$ \mathfrak a^n=\mathfrak e \ , \mathfrak a^k \ne \mathfrak e \quad npu \quad k\in \ \ . $$ Будем также говорить, что $ \mathfrak a $ принадлежит показателю n.

Теорема 1. В поле Галуа $ \mathbf (p^m) $ существуют первообразные корни степени $ p^m-1 $ из единицы.

В поле $ \mathbf (p^m) $ первообразный корень степени $ p^m-1 $ из единицы называется примитивным элементом поля.

Лемма 1. Пусть $ \mathfrak a \in \mathbf (p^m), \mathfrak a \ne \mathfrak o $ — первообразный корень степени $ n_<> $ из единицы. Тогда $ p^m-1 $ делится на $ n_<> $.

Доказательство. Если $ p^m-1 $ не делится на $ n_<> $, т.е. $$ p^m-1 = nq+ r \quad npu \quad \ \subset \mathbb N \quad u \ 0< r< n \ , $$ то одновременно выполняется и $ \mathfrak a^n=\mathfrak e $ и $ \mathfrak a^=\mathfrak e $ ( обобщенная теорема Ферма ). Тогда $$ \mathfrak a^r=\mathfrak a^=\mathfrak a^ \cdot \left( \mathfrak a^ \right)^ = \mathfrak e \cdot \mathfrak e = \mathfrak e \ , $$ т.е. $ \mathfrak a $ является корнем из единицы степени меньшей $ n_<> $. ♦

Обозначим $ \psi (n) $ — число элементов поля $ \mathbf (p^m) $, принадлежащих показателю $ n_<> $. Согласно лемме 1, число $ n_<> $ должно быть делителем числа $ p^m-1 $. Кроме того, если $ \ $ — множество всех делителей числа $ p^m-1 $, то $$ \psi (1)+\psi(d_1)+\psi(d_2)+\dots+\psi(p^m-1) = p^m-1 \ , $$ поскольку любой элемент поля принадлежит одному и только одному показателю.

Лемма 2. Если $ \mathfrak a $ принадлежит показателю $ n_<> $ и число $ k_<> $ взаимно просто с $ n_<> $, то и $ \mathfrak a^k $ принадлежит показателю $ n_<> $.

Доказательство. В самом деле, $ \left( \mathfrak a^ \right)^n = \left( \mathfrak a^ \right)^k = \mathfrak e $. С другой стороны, при $ n_1 < n $ равенство $ \left( \mathfrak a^\right)^ = \mathfrak e $ невозможно. В самом деле, если оно все же выполнено при $ k_<> $ взаимно простом с $ n_<> $. Тогда, существуют целые числа $ u_<> $ и $ v_<> $, обеспечивающие выполнение равенства $ u\,k+v\, n =1 $. Возведем равенство $ \left( \mathfrak a^ \right)^ = \mathfrak a^ = \mathfrak e $ в степень $ u_<> $: $$ \mathfrak e = \mathfrak a^ = \mathfrak a^ \mathfrak a^ = \mathfrak a^ \mathfrak a^ = \mathfrak a^ \ , $$ т.е. $ \mathfrak a $ является корнем из единицы степени меньшей $ n_<> $. ♦

Итак, при любом $ k (k,n)=1 $, элементы $ \mathfrak a^k $ принадлежат показателю $ n_<> $, если $ \mathfrak a $ принадлежит этому показателю. С другой стороны, множество $$ \< \mathfrak a^k \ \mid \ k\in \, \ \operatorname (k,n)=1 \> $$ содержит все элементы, принадлежащие показателю $ n_<> $, поскольку множество $$ \ < \mathfrak a^k \ \mid \ k\in \\> $$ содержит все решения уравнения $ \mathfrak x^n= \mathfrak e $; а при условии $ \operatorname (k,n)>1 $ элемент $ \mathfrak a^k $ принадлежит показателю меньшему, чем $ n_<> $ (см. аналогию с первообразными корнями из единицы в поле комплексных чисел ). Число элементов в первом из этих множеств известно — оно равно значению функции Эйлера от числа $ n_<> $, т.е. $ \phi (n) $. Таким образом, для любого числа $ n \in \mathbb N $ будет либо $ \psi(n)=0 $, либо $ \psi(n) = \phi (n) $, т.е., в общем случае, $$ \psi(n) \le \phi(n) \ . $$

Лемма 3. Если $ p^m-1 $ делится на $ n_<> $, то $ \psi (n) = \phi (n) $.

Доказательство. Если $ \ $ — множество всех делителей числа $ p^m-1 $, то, с одной стороны, имеем выведенное выше равенство: $$ \psi (1)+\psi(d_1)+\psi(d_2)+\dots+\psi(p^m-1) = p^m-1 \ ; $$ с другой же стороны, для функции Эйлера справедливо аналогичное равенство $$ \phi (1)+\phi(d_1)+\phi(d_2)+\dots+\phi(p^m-1) = p^m-1 \ . $$ Вычитаем из второго первое: $$ \sum_ \left[ \phi (d) — \psi (d) \right] =0 \ , $$ где суммирование идет по всем числам $ d_<> $, являющимися делителями числа $ p^m-1 $. Каждое слагаемое — по неравенству, выведенному выше, — неотрицательно. Следовательно, оно должно равняться нулю. ♦

Доказательство теоремы 1 следует из леммы 3 при $ n=p^m-1 $. Фактически мы получили и точное значение для количества первообразных корней степени $ p^m-1 $ из единицы, т.е. для количества примитивных элементов поля $ \mathbf (p^m) $ — оно равно $$ \phi (p^m-1) \ . $$ ♦

Как найти примитивный элемент поля?

Воспользуемся аналогией этого объекта с первообразным корнем по модулю простого числа $ p_<> $ из раздела ☞ ИНДЕКС (дискретный логарифм).

Теорема 2. Если каноническое разложение числа $ p^m-1 $ имеет вид:

$$ p^m-1=p_1^<<\mathfrak m>_>p_2^<<\mathfrak m>_>\times \dots \times p_<\mathfrak r>^<<\mathfrak m>_<_<\mathfrak r>>> \ , $$ то для того чтобы элемент $ \mathfrak A \in \mathbf (p^m) $, был примитивным элементом этого поля, необходимо и достаточно, чтобы $$ \mathfrak A^ \not\equiv \mathfrak e \quad npu \quad \forall j\in \ \ . $$

Доказательство аналогично доказательству теоремы 5 из пункта ☞ ПЕРВООБРАЗНЫЙ КОРЕНЬ. ♦

Пример. Будет ли полином $ x^3+x^2 $ примитивным элементом поля $ \mathbf(16) $, если операция умножения в этом поле определена по двойному модулю $ 2, x^4+x^3+x^2+x+1 $?

Решение. Имеем $ 2^4-1=15=3\cdot 5 $. $$ (x^3+x^2)^ \equiv_ x^+x^+x^+x^ \equiv x^3+x^2+1 \not\equiv 1 \quad (\operatorname \ 2,x^4+x^3+x^2+x+1) ; $$ $$ (x^3+x^2)^ \equiv_ x^9+x^8+x^7+x^6 \equiv 1 \quad (\operatorname \ 2,x^4+x^3+x^2+x+1) . $$

Ответ. Нет.

Лемма 2 позволяет найти все семейство примитивных элементов поля, если один уже обнаружен.

Теорема 3. Если $ \mathfrak A \in \mathbf (p^m) $ — примитивный элемент поля, то $ \mathfrak A^k $ будет примитивным элементом поля тогда и только тогда, когда показатель $ k_<> $ взаимно прост с $ p^m-1 $: $ \operatorname (k,p^m-1)=1 $.

Пример. Определить все примитивные элементы поля $ \mathbf(16) $, если операция умножения в этом поле определена по двойному модулю $ 2, x^4+x^3+1 $.

Решение. С помощью теоремы 2 устанавливаем, что полином $ x_<> $ является примитивным элементом поля. Но тогда, в соответствии с теоремой 3, полиномы $$ x^2,x^4,\ x^7\equiv x^2+x+1,\ x^8\equiv x^3+x^2+x,\ x^ \equiv x^3+x^2+1,\ x^\equiv x^2+x,\ x^\equiv x^3+x^2 \quad (\operatorname \ 2,x^4+x^3+1) $$ также должны быть также примитивными элементами поля. Их (вместе с $ x_<> $) как раз $ \phi(15)=8 $ штук, так что больше примитивных корней нет. ♦

Будет ли полином $ x_<> $ примитивным элементом поля $ \mathbf(2^8) $, если операция умножения в этом поле определена по двойному модулю

a) $ 2, x^8+x^4+x^3+x^2+1 $;

b) $ 2, x^8+x^4+x^3+x+1 $?

Источник

Материалы этого пункта взяты (с незначительными модификациями) из
[1]. Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ.1934

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Поиск примитивного элемента поля Галуа

Поиск примитивного элемента поля Галуа
12.06.2008, 21:20

Подскажите пожалуйста алгоритм нахождения примитивного элемента поля Галуа GF(p), где p — простое. Под алгоритмом я имею в виду просто последовательность шагов и т.д. это необходимо для программной реализации. Теории на эту тематику я вроде начитался, но ничего конкретного не знаю, так что если можно — то поподробнее). Буду рад любой помощи (ссылки, название книг, авторов и т.д.) Заранее большое спасибо!

13.06.2008, 00:10
поле Галуа — это конечное поле $ \mathbb<F>_</p>
<p>$» /> характеристики <img decoding=

Берём $g(x) = (x^p-x)(x^<p^2>-x)\dots(x^>-x)$» />, где <img decoding=— степень расширения, подбираем $\theta$такое, что $g(\theta)\neq 0$. $\theta$— примитивный элемент.

13.06.2008, 06:33

Заслуженный участник

$\mod p$

Я так понял, что под примитивным элементом понимается первообразный корень .
P.S. Я быстрых алгоритмов не знаю. В Shoup V. — A computational introduction to number theory and algebra (Гл. 11) написано так:

Shoup писал(а):

$p-1$

There’s no efficient algorithm known for this problem, unless the prime factorization of is given, and even then we must resort to the use of a probabilistic algorithm.

13.06.2008, 07:26
Если знать факторизацию $p-1$, то легко проверить является ли конкретный элемент $x$примитивным:
$x$будет примитивным тогда и только тогда, когда $x^<\frac<p-1>>\not\equiv 1\pmod</p>
<p>$» /> для каждого простого <img decoding=.

Далее, как доказано Миллером, обобщенная гипотеза Римана влечет существование примитивного элемента меньшего $70\ln(p)^2$. Таким образом, если факторизация числа $p-1$известна, а обобщенная гипотеза Римана справедлива, то алгоритм нахождения минимального примитивного элемента является полиномиальным

17.06.2008, 22:36

оказалось все немного проще: в качестве входного агрумента — число P, которое в программе проверяется на простоту. Если р простое, то необходимо вывести все примитивные элементы поля GF(p), в то время как элементами поля являются числа от 0 до р-1. Примитивные элементы я вычислял тупо перебором, причем получилось так, что в маленьких полях (p<=19) примитивные элементы находяться нормально (проверено), однако дальше он ни к одному полю не находит ни одного примитивного элемента. Отсюда вопрос: в любом ли поле обязательно должен существовать хотя бя один примитивный элемент? Ну и интересно, есть ли какие-нибудь другие алгоритмы кроме перебора для нахождения примитивных элементов, в случае если элементами поля являются цифры от 0 до р-1.

17.06.2008, 22:50
kazachis4e писал(а):

оказалось все немного проще: в качестве входного агрумента — число P, которое в программе проверяется на простоту. Если р простое, то необходимо вывести все примитивные элементы поля GF(p)

$p-1$

Достаточно найти один, а дальше возводить его в степени взаимно простые с числом — так получатся все примитивные элементы.

kazachis4e писал(а):

Примитивные элементы я вычислял тупо перебором, причем получилось так, что в маленьких полях (p<=19) примитивные элементы находяться нормально (проверено), однако дальше он ни к одному полю не находит ни одного примитивного элемента. Отсюда вопрос: в любом ли поле обязательно должен существовать хотя бя один примитивный элемент?

$\varphi(p-1)$

Конечно должен, ведь мультипликативная группа поля циклична. Более того, количество различных примитивных элементов равно значению функции Эйлера (почему — см. выше). Так что, ищите ошибку в программе.

kazachis4e писал(а):

Ну и интересно, есть ли какие-нибудь другие алгоритмы кроме перебора для нахождения примитивных элементов, в случае если элементами поля являются цифры от 0 до р-1.

Алгоритм проверки на примитивность я описал в предыдущем сообщении. А искать можно по разному — последовательно перебирая элементы 2,3,4 и т.д. или случайным образом выбирая число из отрезка [2,p-1].

Конечные поля. Как найти примитивный элемент?

Здравствуйте. Имеется поле GF(5^2) и неприводимый многочлен над ним x^2+x+1.
Нужно найти примитивный элемент. Подскажите по какому алгоритму это можно сделать,
или лучше простенький пример приведите. Я пытался составить степени примитивного элемента
для a, и a+1 но на 20 степени получал единичку. Хотя элементов должно быть 24.

Лучший ответ

Надо найти, перебором к сожалению, элемент, 8-я и 12-я степень которого не равны единице. Есть утверждение про примитивный элемент.
Таких элементов должно быть несколько.
Т. е. надо для всех элементов, кроме 1, вычислить 4-е степени. А для них квадраты (8-я степень) .
Выкинуть элементы, дающие в 8 степени единицу. Для остальных посчитать 12 степень.
Не равные единице — примитивные.

Остальные ответы

Похожие вопросы

Как найти примитивный элемент поля

Здравствуйте, Аноним, Вы писали:

А>Забыл. Может есть где-нибудь большие простые числа и примитивные элементы?

За скромное вознаграждение могу сгенерить парочку. Вопрос в том, насколько скромным будет вознаграждение, и на сколько быстро это надо сделать

Re[3]: Примитивный элемент поля

От: Ivan Korotkov
Дата: 12.10.04 10:47
Оценка:

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Mab, Вы писали:

Mab>>Пусть нужно найти примитивный эелемент по модулю p (p — простое). Мультипликативная группа поля циклическая и имеет порядок p — 1, поэтому всего генераторов у нее phi(p — 1), то есть достаточно много. Насколько понимаю, поступают так: последовательно перебирают a = 2, 3 итд и проверяют, является ли данный вычет примитивным.

Mab>>Нужно проверить, что у a порядок не меньше p — 1, а для этого достаточно проверить, что a^ <> 1 (mod p) для всякого простого делителя q|p-1. Здесь нам потребуется знание разложения p — 1 на простые множители, поэтому p нужно подбирать так, чтобы это разложение было заранее известно.

А>А как тогда мне генерировать случайное p, чтобы знать разложение p-1 на простые множители(ну кроме 2 естественно)?

А можно использовать не простое р, а pq, где p и q — простые. Тогда phi(pq)=(p-1)(q-1). По-моему, алгоритм Эль-Гамаля не требует, чтобы n было простым. Просто надо исключить из 1..N больше чисел (все, кратные p и q), но вероятность того, что хэш документа попадет на них, очень мала.

Re[4]: Примитивный элемент поля

От: Ivan Korotkov
Дата: 12.10.04 10:49
Оценка:

Здравствуйте, Ivan Korotkov, Вы писали:

IK>А можно использовать не простое р, а pq, где p и q — простые. Тогда phi(pq)=(p-1)(q-1). По-моему, алгоритм Эль-Гамаля не требует, чтобы n было простым. Просто надо исключить из 1..N больше чисел (все, кратные p и q), но вероятность того, что хэш документа попадет на них, очень мала.

Пардон, меня че-то проглючило. Я забыл, что по-любому p-1 и q-1 разлагать придется.

Re[4]: Примитивный элемент поля

От: Аноним
Дата: 12.10.04 11:37
Оценка:

Здравствуйте, Вадим Никулин, Вы писали:

ВН>Здравствуйте, Аноним, Вы писали:

А>>Забыл. Может есть где-нибудь большие простые числа и примитивные элементы?

ВН>За скромное вознаграждение могу сгенерить парочку. Вопрос в том, насколько скромным будет вознаграждение, и на сколько быстро это надо сделать
Лучше расскажи как получать примитивный элемент, раз можешь его сгенерить парочку

Re[5]: Примитивный элемент поля

От: Вадим Никулин Здесь
Дата: 12.10.04 13:23
Оценка:

Здравствуйте, Аноним, Вы писали:

ВН>>За скромное вознаграждение могу сгенерить парочку. Вопрос в том, насколько скромным будет вознаграждение, и на сколько быстро это надо сделать
А>Лучше расскажи как получать примитивный элемент, раз можешь его сгенерить парочку

Макс все подробно описал. Я просто могу написать прогу (если время будет). Инструменты для определения простоты числа (читай для поиска простых чисел, сносно работает до 150-200 десятичных цифр) и для разложения на множители (есть прецеденты разложения 40-циферных чисел, но оптимизацией особо не занимался) у меня есть.

Re[6]: Примитивный элемент поля

От: TheBeard
Дата: 12.10.04 13:45
Оценка:

А если взять Maple (www.maplesoft.com), к примеру, и попробовать
тамошними инструментами? Он в Москве на рынках часто встречается.
Точность у него произвольная, вопрос исключительно во времени работы.

Вадим Никулин wrote:

> Инструменты для определения простоты числа (читай для поиска простых
> чисел, сносно работает до 150-200 десятичных цифр) и для разложения
> на множители (есть прецеденты разложения 40-циферных чисел, но
> оптимизацией особо не занимался) у меня есть.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *