Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 11 янв 2018, 22:41 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2018, 22:26
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Стоит задача найти написать на c++ программу, находящую для полиномов над полем [math]\mathbb{F}_{2^m}[/math] корни полиномов. Никаких ограничений на сложность алгоритма нет, и так как времени особенно для того, чтобы возиться с задачей нет, то и нет особых причин разбираться и писать алгоритм Берлекэмпа, специально для этого предназначенный. Полагаю ,можно просто пробегаться по всем элементам поля Галуа и для каждого проверять, является ли он корнем полинома или нет. Сложность заключается в том, что я нигде не могу найти алгоритм поиска неприводимого многочлена над расширенным полем Галуа, который нужен, чтобы написать арифметику, необходимую программе. Про таблицы неприводимых многочленов знаю, но это немного не то, что нужно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 12 янв 2018, 15:15 
Не в сети
Мастер
Зарегистрирован:
14 дек 2017, 18:48
Сообщений: 252
Cпасибо сказано: 13
Спасибо получено:
69 раз в 67 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
Так сами напишите, перебирайте все многочлены пока не найдете неприводимый

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 12 янв 2018, 15:49 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2018, 22:26
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Slon писал(а):
Так сами напишите, перебирайте все многочлены пока не найдете неприводимый


Ну, честно говоря, я определённо не вполне понимаю, как конкретно это сделать. В смысле, может, фигню сейчас скажу, но как понял я, чтобы определить, является ли полином [math]p(x)\in\mathbb{F}_{2^m}[/math] примитивным по определению, нужно возводить его в степень [math]2^m[/math] раз, а для этого нам потребуется какой-то другой неприводимый полином, который, выходит, точно также придётся найти.

В общем, долго я искал нужный алгоритм на просторах интернета и в итоге нашёл, что если LFSR с коэффициентами [math]\alpha_1 ... \alpha_n[/math] соответствующими коэффициентам проверяемого полинома и ненулевым изначальным значением регистра выдаёт за один цикл все возможные значения [math]GF(2^m)[/math], кроме нуля, то наш полином является неприводимым в [math]GF(2^m)[/math]. Ну а зная это, да, можно перебирать или брать случайные - кому как удобно - пока не будет найден примитивный.
Математическое основание я этой штуки с LFSR пока не понимаю, но оно, наверное, очень простое и очевидное. Если кто-нибудь ткнёт меня в него носом, буду благодарен)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 12 янв 2018, 16:46 
Не в сети
Мастер
Зарегистрирован:
14 дек 2017, 18:48
Сообщений: 252
Cпасибо сказано: 13
Спасибо получено:
69 раз в 67 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
Я мог неправильно понять Ваш вопрос, если что-то не так из того, что ниже говорите:
1) У Вас есть конкретное m а значит и поле [math]F_{2^m}[/math], правда его еще нужно построить.
2) Затем у Вас будет многочлен над [math]F_{2^m}[/math] и Вам нужно посмотреть есть ли у него корень из [math]F_{2^m}[/math]
3) Единственная трудность построить [math]F_{2^m}[/math]

Ну вот не проблема, например (хотя это совсем не оптимально) Перебирать все полиномы f степеня m над [math]F_2[/math], все полиному меньшей степени g над [math]F_2[/math] и смотреть делиться ли f на g. Тут алгоритм Евклида вам даже остаток найдет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Slon "Спасибо" сказали:
lis96
 Заголовок сообщения: Re: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 12 янв 2018, 17:11 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2018, 22:26
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Slon писал(а):
Я мог неправильно понять Ваш вопрос, если что-то не так из того, что ниже говорите:
1) У Вас есть конкретное m а значит и поле [math]F_{2^m}[/math], правда его еще нужно построить.
2) Затем у Вас будет многочлен над [math]F_{2^m}[/math] и Вам нужно посмотреть есть ли у него корень из [math]F_{2^m}[/math]
3) Единственная трудность построить [math]F_{2^m}[/math]

Ну вот не проблема, например (хотя это совсем не оптимально) Перебирать все полиномы f степеня m над [math]F_2[/math], все полиному меньшей степени g над [math]F_2[/math] и смотреть делиться ли f на g. Тут алгоритм Евклида вам даже остаток найдет.


Ну, [math]m[/math] произвольное и выбирается на этапе выполнения написанной программы, но так-то да, действительно, вы совершенно правы. Это первое, что должно приходить в голову, создал проблему на пустом месте. Спасибо. Впрочем, я даже рад, что потратил время и нашёл алгоритм поиска примитивного полинома в поле характеристики 2 через использование LFSR. Там оказалось очень просто это реализовать программно, и алгоритм вычислительно куда более прост, чем решать в лоб.

Ещё раз спасибо, тему, полагаю, вполне можно закрывать.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Как вычислить степень полинома по модулю полинома?

в форуме Линейная и Абстрактная алгебра

Alex893

0

164

20 мар 2012, 16:16

Числовые методы и теория Галуа

в форуме Дискуссионные математические проблемы

timots

4

558

31 дек 2013, 02:02

Как Галуа создал свою теорию?

в форуме Линейная и Абстрактная алгебра

sfanter

5

157

26 авг 2016, 19:23

Анализ полинома

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

Lenar0809

1

186

17 окт 2015, 21:28

Доказательство степени полинома

в форуме Линейная и Абстрактная алгебра

Bonaqua

12

598

26 июн 2015, 10:32

Взятие полинома по модулю.

в форуме Линейная и Абстрактная алгебра

Alex893

2

246

20 мар 2012, 09:43

Вычесление полинома Жегалкина

в форуме Дискретная математика, Теория множеств и Логика

Dankyway

0

82

24 дек 2016, 01:14

Массив из значений полинома Лаггера

в форуме Информатика и Компьютерные науки

Zdrastes

4

548

08 окт 2013, 21:27

Найти кратность корня для полинома

в форуме Линейная и Абстрактная алгебра

Rostislav

1

369

18 май 2013, 14:42

Представить в виде полинома Жегалкина

в форуме Дискретная математика, Теория множеств и Логика

Alcantara

7

124

18 ноя 2016, 15:38


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved