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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 12 янв 2018, 14:15 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Корни полинома в расширенном поле Галуа
СообщениеДобавлено: 12 янв 2018, 14:49 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2018, 21:26
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
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, 15:46 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Я мог неправильно понять Ваш вопрос, если что-то не так из того, что ниже говорите:
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, 16:11 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2018, 21:26
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
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пасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Корни полинома 4ой степени

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

jeliza_rosa

4

217

29 апр 2022, 09:10

Корни полинома 4 степени

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

Avgust

6

306

05 ноя 2019, 23:56

Найти кратные корни полинома, в зависимости от действительно

в форуме Алгебра

roman666

11

658

02 янв 2023, 12:44

Найти кратные корни полинома, в зависимости от действительно

в форуме Алгебра

vilgeforc5

6

281

14 июн 2022, 19:48

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

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

sfanter

5

378

26 авг 2016, 18:23

Является ли структура полем Галуа?

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

carbtc

3

541

23 мар 2018, 15:39

Операция деления в полях Галуа

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

IDABSENT

0

207

13 июн 2021, 00:52

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

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

Lenar0809

1

360

17 окт 2015, 20:28

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

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

Bonaqua

12

1078

26 июн 2015, 09:32

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

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

Dankyway

0

281

24 дек 2016, 00:14


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



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

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


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

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

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

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