Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 5 ] |
|
Автор | Сообщение | |
---|---|---|
lis96 |
|
|
|
||
Вернуться к началу | ||
Slon |
|
|
Так сами напишите, перебирайте все многочлены пока не найдете неприводимый
|
||
Вернуться к началу | ||
lis96 |
|
|
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 пока не понимаю, но оно, наверное, очень простое и очевидное. Если кто-нибудь ткнёт меня в него носом, буду благодарен) |
||
Вернуться к началу | ||
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. Тут алгоритм Евклида вам даже остаток найдет. |
||
Вернуться к началу | ||
За это сообщение пользователю Slon "Спасибо" сказали: lis96 |
||
lis96 |
|
|
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. Там оказалось очень просто это реализовать программно, и алгоритм вычислительно куда более прост, чем решать в лоб. Ещё раз спасибо, тему, полагаю, вполне можно закрывать. |
||
Вернуться к началу | ||
[ Сообщений: 5 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Корни полинома 4ой степени
в форуме Линейная и Абстрактная алгебра |
4 |
217 |
29 апр 2022, 09:10 |
|
Корни полинома 4 степени
в форуме Линейная и Абстрактная алгебра |
6 |
306 |
05 ноя 2019, 23:56 |
|
Найти кратные корни полинома, в зависимости от действительно
в форуме Алгебра |
11 |
658 |
02 янв 2023, 12:44 |
|
Найти кратные корни полинома, в зависимости от действительно
в форуме Алгебра |
6 |
281 |
14 июн 2022, 19:48 |
|
Как Галуа создал свою теорию?
в форуме Линейная и Абстрактная алгебра |
5 |
378 |
26 авг 2016, 18:23 |
|
Является ли структура полем Галуа?
в форуме Линейная и Абстрактная алгебра |
3 |
541 |
23 мар 2018, 15:39 |
|
Операция деления в полях Галуа | 0 |
207 |
13 июн 2021, 00:52 |
|
Анализ полинома
в форуме Функциональный анализ, Топология и Дифференциальная геометрия |
1 |
360 |
17 окт 2015, 20:28 |
|
Доказательство степени полинома
в форуме Линейная и Абстрактная алгебра |
12 |
1078 |
26 июн 2015, 09:32 |
|
Вычесление полинома Жегалкина | 0 |
281 |
24 дек 2016, 00:14 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |