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

2. Кольцо многочленов. Примитивные элементы.

Построение GF(q), . Конечные поля можно строить из колец многочленов таким же образом, как были построены поля из кольца целых чисел. Пусть имеем кольцо многочленов над полем P. Так же как были построены классы вычетов для кольца Z, можно построить и кольца классов вычетов для кольца . Для этого достаточно выбрать в произвольный многочлен и определить классы вычетов, используя многочлен в качестве модуля при выполнении операций сложения и умножения классов вычетов. В результате будет построено фактор-кольцо . Это фактор-кольцо состоит из классов вычетов по модулю , представителями которых в данном случае выступают всяческие остатки от деления многочленов на p(x), то есть все многочлены из , степени которых не превышают .

Для того чтобы фактор-кольцо ) было полем по аналогии с требованиями Теоремы 2 в этом случае многочлен должен быть простым 3 ) (см. Л-15, ТГКП), то есть неприводимым. Для неприводимого многочлена степени n

над полем P, то есть многочлена с коэффициентами , мы приходим к полю, элементами которого являются кортежи из n чисел , одним из вариантов представления которых и является использование многочленов степени n  1 с коэффициентами  элементами поля GF(p). Напомним здесь, что в соответствии с теоремой 1, Л-1, РПЭК (поле , образованное из поля присоединением корня неприводимого над полем многочлена n-й степени состоит из всех чисел вида , где произвольные числа из поля ) элементами поля фактически выступают не сами многочлены, а числа, получающиеся при подстановке в многочлены корня неприводимого многочлена (элементы поля выражаются через базисы, построенные на основе использования корня неприводимого над исходным полем многочлена).

Полученное поле содержит все константы где (все элементы поля P), и потому является р а с ш и р е н и е м поля P. Число элементов (порядок) построенного рассмотренным способом поля есть степень некоторого натурального простого числа p, которое является характеристикой этого поля (множество элементов этого поля есть декартовое произведение n множеств из p элементов каждое). Мы далее покажем, что для любого натурального простого p и любого натурального n существует (и единственно с точностью до изоморфизма) поле из элементов. Оно обозначается , или и также . Поле содержит как подполе поле GF(p m ) в том и только в том случае, когда m делится на n. В частности, в любом поле содержится поле GF(p), которое мы назвали ранее простым полем характеристики p. Подробное обоснование этих и ряда других положений мы выполним отдельно.

Мы в дальнейшем сосредоточимся на рассмотрении, прежде всего, конечных полей. Ограничимся также рассмотрением только приведенных (нормированных) многочленов, так как это ограничение снимает ненужную неопределенность в рассуждениях.

Рассмотренный подход к построению расширения поля GF(p) зафиксируем в виде теоремы, которую мы докажем строго позднее.

Теорема 3. Если  неприводимый над полем GF(p) многочлен степени n, то множество всех многочленов от x степеней с коэффициентами из поля GF(p), операции над которыми выполняются по модулю многочлена , образует поле порядка .

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

Определение 2. Примитивным элементом поля GF(q) называется такой элемент , что все элементы поля, за исключением нуля, могут быть представлены в виде степени элемента .

Например, в поле GF( ) примитивным элементом является многочлен первой степени . Действительно, для неприводимого многочлена имеем:

Примитивные элементы очень полезны при построении полей, так как если один из них найден, то, перемножая степени примитивного элемента, можно построить таблицу умножения в поле.

Мы сейчас докажем, что каждое поле содержит хотя бы один примитивный элемент.

Поле образует абелевую группу двумя способами. Множество всех элементов поля образует абелевую группу по сложению, и множество всех элементов поля за исключением нуля, образует абелевую группу по умножению.

Сейчас нас будет интересовать группа по умножению. Как известно порядок этой группы делится на порядок любого ее элемента.

Теорема 4. Пусть  ненулевые элементы поля GF(q); тогда , то есть ненулевые элементы поля GF(q) являются корнями обобщенного многочлена .

Д о к а з а т е л ь с т в о. Множество ненулевых элементов поля GF(q) образует конечную группу по умножению. Пусть  любой ненулевой элемент из GF(q), и пусть  порядок этого элемента по умножению. Тогда соответственно теореме Лагранжа делит . Следовательно,

Таким образом, является корнем многочлена , то есть . При выполнении последнего равенства говорят, что является корнем степени из единицы, если это степень является максимальной (и тогда является примитивным элементом поля GF(q)). Вообще говоря, может оказаться и корнем более низкой степени, если выполняется равенство для степени s, которая делит (например, степени ).

Итак, для поля GF(q) справедливо разложение

где пробегает все элементы поля (разные элементы).

Для простого поля GF(p) это разложение имеет вид

Теорема 5. Группа ненулевых элементов поля GF(q) по умножению является циклической

Д о к а з а т е л ь с т в о. Если число простое, утверждения тривиальное, так как в соответствии со следствием 2 теоремы Лагранжа, Л-5 (каждая конечная группа G, порядок которой оказывается простым числом, является циклической) порядок любого элемента группы, за исключением нуля и единицы, равняется , и, итак, каждый такой элемент примитивный. Доказательство надо выполнить только для случая, когда число составное.

Рассмотрим разложение числа на простые множители

Так как GF(q)  поле, то среди ненулевых элементов должен обнаружиться хотя бы одним, что не является корнем многочлена , поскольку этот многочлен может иметь не больше чем корней. Итак, для каждого i можно найти такой ненулевой элемент поля GF(q), что . Пусть и пусть . Докажем, что порядок элемента b равняется , и, соответственно, группа является циклической.

Шаг 1. Порядок элемента равняется . Доказательство. Очевидно, что , так что порядок элемента делит . Он равняется числу вида . Если меньше , то . Но , и, следовательно, порядок элемента равняется .

Шаг 2. Порядок элемента равняется . Доказательство. Предположим, что . Покажем сначала, что из этого следует равенство для всех . Действительно, для каждого i можно записать

Заменим теперь на и используем равенство . В результате получим . Но же для каждого i и потому

Поскольку являются разными простыми числами, то для каждого i. Итак, . Теорема доказана.

Следствие (Теорема Ферма). Каждый элемент поля GF(q) удовлетворяет равенству , или эквивалентно, является корнем уравнения .

Теорема 5 дает также важнейший ключ к пониманию структуры полей Галуа, а именно она позволяет утверждать такое.

Теорема 6. В каждом поле GF(q) имеется примитивный элемент..

Д о к а з а т е л ь с т в о. Так как ненулевые элементы поля GF(q) образуют циклическую группу, то среди них имеется элемент порядка . Этот элемент и является примитивным по определению.

Использование примитивного элемента для умножения в поле иллюстрируется следующими примерами:

Выше был рассмотрен пример построения поля GF(8) = . Порядок циклической (мультипликативной) группы равен этого поля равен простому числу 7, и, следовательно, каждый элемент, за исключением нуля и единицы, имеет порядок, который равняется 7, а, значит, является примитивным. С использованием представления элементов поля, приведенным выше, умножение выполняется совсем легко; например, для примитивного элемента имеем  (( )x ). Очевидно также, что  (1( ) ).

Порядок каждого элемента в поле GF(16) = делит 15. Элемент может иметь порядок 1, 3, 5 или 15. Поле GF(16) можно построить с помощью многочлена и примитивного элемента ; имеем:

При таком представлении поля умножения снова оказывается простым; например, .

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

Определения 3. Примитивным многочленом над полем GF(q) называется простой многочлен над полем GF(q), такой, что в расширении поля, построенном по модулю , соответствующий многочлену x элемент поля является примитивным.

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

1 ) Галуа (Galois) Эварист (1811-32), французский математик. Труды по теории алгебраических уравнений положили начало развития современной алгебры. С идеями Г. связаны такие ее важнейшие понятия, как группа, поле и др. Научное наследие Г.  небольшое число очень кратко написанных робот, которые из за новизны идей не были понятыми при жизни Г.

2 ) При изложении этого раздела использованы материалы монографии Р. Блейхута. Теория и практика кодов, контролирующих ошибки. Под редакцией К. Щ. Зигангирова. М:, Мир, 1986, Стр 88-110.

3 ) Термин простой элемент используется как общий для произвольного кольца, для кольца многочленов P[x] употребляется также и термин неприводимый многочлен.

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

В силу аксиом поля, элементы конечного поля образуют конечные абелевы группы относительно операций поля (см. параграф 1.1). При этом каждый элемент поля (за исключением нуля) имеет некоторый порадок относительно обеих операций (см. параграф 1.1). Порядок элемента относительно операции сложения называется аддитивным порядком, а относительно умножения — мультипликативным порядком. Нас будет интересовать только мультипликативный порядок элементов поля.

Порядком (ненулевого) элемента конечного поля далее будем называть мультипликативный порядок рассматриваемого элемента.

Таким образом, для любого ненулевого элемента GF[q) справедливо равенство а° — 1, где с — порядок элемента. При этом любой ненулевой элемент а порядка с поля GF(q) является корнем двучленах 0 -1 и уравнениях 0 -1 = 0.

В общем случае различные элементы поля GF(q) могут иметь различные порядки. Однако при этом очевидно, что максимально возможный порядок элемента поля GF(q) имеет значение q — 1. Очевидно также, что существование такого элемента означает, что все ненулевые элементы поля можно представить в виде степеней одного элемента порядка q — 1.

Читать:

Как найти средний рост учеников

Предположим, что это не так. Тогда все множество элементов поля GF(q) образовано степенями некоторых двух элементов а и Ь порядков т и к соответственно [т h , h h — 1, и условие принадлежности элемента Ь множеству своих степеней нарушается. Равенство b = a h — 1 означает, что множество степеней элемента Ь, по сути, образовано степенями элемента а.

Таким образом, все ненулевые элементы поля соответствуют степеням некоторого элемента поля. Указанный элемент образует циклическую группу относительно операции умножения, элементами которой являются все ненулевые элементы поля.

Элемент поля, степени которого образуют все ненулевые элементы поля, называется примитивным элементом.

Очевидно, что порядок примитивного элемента поля GF(q) всегда имеет значение q-1.

Забегая вперед, отметим, что примитивных элементов в общем случае может быть несколько. Однако к этому вопросу мы вернемся позже (см. подпараграф 1.6.1). Пока же обозначим то, что мы уже сейчас можем сказать о примитивных элементах поля на основе ранее установленных свойств поля.

В любом поле GF(q) существует как минимум один примитивный элемент, степени которого образуют все q — 1 ненулевых элементов поля. Так как порядок примитивного элемента GF всегда равен q- 1, то примитивный элемент этого поля всегда является корнем двучлена х9

1 -1 и уравнения:

Пример 1.4.4. Рассмотрим циклическую группу, образованную элементом 3 поля GF(5). Согласно правилам умножения элементов в поле GF(5), 3 1 = 3, З 2 =

= 3-3 = 4, З 3 = 3 2 -3 = 4-3 = 2, З 4 = 3 3 -3 = 2-3 = 1, З 5 = 3 4 -3 = 1-3 = 3, З 6 = 3 5 -3 = 3-3 = = 4, З 7 = 3 6 -3 = 4-3 = 2, и так далее. Таким образом, последовательность степеней будет повторяться, начиная с пятой степени. То есть порядок элемента 3 в данном случае равен четырем и все ненулевые элементы поля GF(5) могут быть представлены в виде степени элемента 3. Иными словами, в этом случае элемент 3 соответствует определению примитивного элемента. То же самое справедливо для элемента 2.

Следует понимать, что соответствие всех ненулевых элементов поля степеням примитивного элемента вовсе не означает равенство порядков всех элементов поля. Поскольку q — простое и, следовательно, нечетное число, то число q -1 всегда четно и, следовательно, имеет как минимум два простых делителя. В общем случае разложение числа q-1 соответствует разложению (1.2).

Пусть число с — некоторый простой делитель числа q — 1. Тогда (q — 1 )lc = h и для элемента a h поля GF(q) справедливо: (a h ) c = a hc = а^

1 = 1, и элемент a h одновременно является корнем уравнения (1.28) и уравнения:

Таким образом, в поле GF[q), помимо примитивных элементов порядка q — 1, также должны существовать элементы, порядки которых являются делителями числа q-1.

Пример 1.4.5. Рассмотрим поле GF(5). Делителем числа q — 1 = 4 в этом случае является только простое число к = 2. При этом h = (q-‘)lk = 4/2 = 2. Примитивными элементами поля GF(5), как мы видели выше, являются элементы 2 и 3. Степень /7 = 2 примитивных элементов 2 и 3 равна элементу 4. Рассмотрим ряд степеней элемента 4: 4° = 1,4 1 = 4,4 2 = 1. Следовательно, порядок элемента 4 поля GF(5) равен двум.

Сказанное о примитивном элементе простого поля GF(q) справедливо также для примитивного элемента поля расширения. Поскольку число ненулевых элементов GF(Q) как расширения GF(q m ) поля GF(q) имеет значение Q — 1 = q m — 1, то порядок примитивного элемента поля GF(q m ) также должен иметь значение q m —1, а примитивный элемент поля GF(q m ) должен удовлетворять уравнению:

Условимся далее примитивные элементы полей расширения обозначать буквой а. При этом элементы полей расширения, о примитивности которых заранее не известно, условимся обозначать другими (произвольными) буквами греческого алфавита.

Уравнению (1.30) удовлетворяет не только примитивный, но и любой другой ненулевой элемент поля GF(q m ). К этому вопросу мы вернемся чуть позже в этой главе (см. подпараграф 1.6.3).

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

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

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

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

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

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

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

Берём $$g(x) = (x^p-x)(x^<p^2>-x)\dots(x^<p^<n-1>>-x)$» />, где <img decoding=$ — степень расширения, подбираем $\theta$ такое, что $g(\theta)\neq 0$ . $\theta$ — примитивный элемент.
Я так понял, что под примитивным элементом понимается первообразный корень $\mod p$ .
P.S. Я быстрых алгоритмов не знаю. В Shoup V. — A computational introduction to number theory and algebra (Гл. 11) написано так:
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.
Если знать факторизацию , то легко проверить является ли конкретный элемент примитивным:
будет примитивным тогда и только тогда, когда $$x^<\frac<p-1><q>>\not\equiv 1\pmod</p> <p>$» /> для каждого простого <img decoding=$ .

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

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

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

PARI/GP: вычисления в конечных полях. Часть 1

PARI/GP — это система компьютерной математики с собственным C-подобным интерпретируемым языком, ориентированная на вычислительную теорию чисел. Система пользуется популярностью в научной среде: согласно Google Scholar только за 2014 год порядка 100 тематических статей, использующих PARI/GP, были опубликованы в реферируемых журналах/конференциях.

В моём диссертационном исследовании мне требовалось часто решать традиционные задачи линейной алгебры (например, для матрицы большой размерности вычислить её ядро и ранг), но только над конечными полями (например, или ). Если бы у нас были просто комплексные матрицы, то эффективно справились бы все хоть сколько-нибудь известные системы символьной математики: например, в любимой мною Wolfram Mathematica достаточно использовать функции NullSpace и MatrixRank соответственно. Вот было бы здорово, если эти же функции враз заработали и для матриц над конечными полями, пусть и с потерей в производительности из-за неэффективности общих алгоритмов линейной алгебры для них… Увы, я получил экспоненциальный рост (вплоть до часов на моём бедном нетоповом ноутбуке) времени вычислений от размерности матриц (см. мой вопрос на профильном форуме по Wolfram Mathematica). Правда, справедливости ради, это было вызвано не столько проблемами реализации алгоритмов линейной алгебры, сколько проблемами самого процессора символьных вычислений.

К моей великой радости PARI/GP предназачается именно для расчётов в различных алгебраических системах (кольцах, полях), оперируя их элементами как «атомарными» числами, а не как символьными структурами над встроенными типами. По моему эмпирическому наблюдению, PARI/GP имеет непревзойдённую скорость таких вычислений. К тому же есть возможность трансляции интерпретируемого кода в чистый C.

Основные функции для работы в конечных полях

Функция ffinit(q, n, ) вычисляет нормированный неприводимый над простым полем многочлен f(v) степени n от переменной v (необязательный параметр, по умолчанию многочлен будет от аргумента x). Например: вызов ffinit(2, 3, x) вернёт примитивный многочлен , а ffinit(2, 4, x) — уже просто неприводимый многочлен . Теперь мы можем задать расширение конечного поля классически, как фактор-кольцо .

Корень неприводимого многочлена f(x) как объект PARI/GP создается при помощи функции ffgen(f, x). Другими словами, вызов g = ffgen(f, x) возвращает объект g, отождествлённый с классом эквивалентности [x] — элементом фактор-кольца . Теперь поле , рассматриваемое как линейное пространство над , можно построить (его таблицы сложения и умножения) с помощью порождающего множества .

Найти примитивный элемент поля можно с помощью функции ffprimroot(g). Эта функция вычисляет случайный элемент порядка (n — 1) в мультипликативной группе конечного поля, которое задано объектом g.

С помощью функции minpoly(a) можно найти минимальный многочлен элемента a конечного поля. Например, вызов p = minpoly(a) вернет . Другими словами, найдя примитивный элемент поля , поле можно представить в традиционном виде , где p — его примитивный многочлен.

Жизненный пример

Предварительная справка

Все объекты в PARI/GP создаются на его внутреннем стеке. По умолчанию, внутренний стек занимает 3.8Мб (4 миллиона байт) динамической памяти компьютера. Чтобы его расширить, используется функция allocatemem(s), где s — это запрашиваемое количество байт.

Разделитель «;» в конце строки используется для запрета вывода результата на печать.

По умолчанию, любой идентификатор является переменной для многочленов. Можно использовать перед идентификатором апостроф, который указывает, что перед нами именно переменная для многочленов, а не какой-то объект. Например,

Сам пример

Конфигурация моего ноутбука — Intel Core(TM) i7-4702M CPU @ 2.20GHz 2.20GHz, 32kB L1 cache, 8Gb DDR3. Использовался PARI/GP 2.7.2 (32bit, single thread) — это последний на момент публикации этого текста релиз, «работающий из коробки» под ОС Windows.