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

[kazachis4e]

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

[Таня Тайс]

поле Галуа - это конечное поле

$$ \mathbb{F}_{p}$$

характеристики

$$p>0$$

?

[Echo-Off]

Берём $g(x) = (x^p-x)(x^{p^2}-x)\dots(x^{p^{n-1}}-x)$, где $n$ - степень расширения, подбираем $\theta$ такое, что $g(\theta)\neq 0$. $\theta$ - примитивный элемент.

[RIP]

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

Shoup писал(а):

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

[maxal]

Если знать факторизацию $p-1$, то легко проверить является ли конкретный элемент $x$ примитивным:
$x$ будет примитивным тогда и только тогда, когда $x^{\frac{p-1}{q}}\not\equiv 1\pmod{p}$ для каждого простого $q|(p-1)$.

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

[kazachis4e]

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

[maxal]

kazachis4e писал(а):

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

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

kazachis4e писал(а):

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

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

kazachis4e писал(а):

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

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

[bot]

maxal писал(а):

последовательно перебирая элементы 2,3,4

4 не надо
Вообще все квадратичные вычеты не надо.