2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 
Сообщение13.06.2008, 00:10 
Аватара пользователя
поле Галуа - это конечное поле $$ \mathbb{F}_{p}$$ характеристики $$p>0$$?

 
 
 
 
Сообщение13.06.2008, 02:57 
Аватара пользователя
Берём $g(x) = (x^p-x)(x^{p^2}-x)\dots(x^{p^{n-1}}-x)$, где $n$ - степень расширения, подбираем $\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 писал(а):
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.

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

Далее, как доказано Миллером, обобщенная гипотеза Римана влечет существование примитивного элемента меньшего $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].

 
 
 
 
Сообщение18.06.2008, 14:17 
Аватара пользователя
maxal писал(а):
последовательно перебирая элементы 2,3,4

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group