Comments 22
Что будет именно в этой статье: коротко рассмотрим теорию... посмотрим как быстро вычислять... Спасибо за конструктивную критику.
Итог: коротко не не вышло, быстро не получилось.
Плюсы: кратко и ясно даны базовые понятия (поле, порождающий полином, ...).
Минусы: низкая структурированность плюс полотна текста, что совокупно порождает сложность следить за ходом мысли. Не многие "дожмут" статью до конца.
Как минимум спрячьте примеры и частности под кат. :)
PS Написание технических книг (статей) - своего рода умение. Есть руководства (втч. на Хабре), рекомендовал бы прочесть их. Ключевые слова: краткость, ясность, одно предложение - одна мысль.
Пример:
К сожалению функцию Эйлера можно использовать только для дополнительной проверки, конкретные полиномы при помощи данной функции не найдешь.
Должно быть:
"Функця Эйлера годна для дополнительной проверки. Конкретные полиномы ей не найти."
Искал когда-то такие полиномы. Вот есть тут немного:
https://andyplekhanov.narod.ru/science/galua.htm
Надо б мне это сохранить. Может, наконец осилю сделать коды Рида-Соломона для более чем первой степени от простого числа :)
Спасибо, когда я искал информацию по порождающим полиномам для конечных полей мне попадались статьи по кодам Рида-Соломона, я не стал глубоко разбираться в данном вопросе, потому что эти коды выходят за пределы моего текущего интереса.
Но у меня осталось четкое представление что порождающий полином для кодов Рида-Соломона строится по другому, зависит от таких параметров как: длина сообщения, количество ошибочных символов,... Могу ошибаться, поправьте если что.
Ну, чтобы понять, такой же он там или другой — мне надо понять, какой он тут, а я пока не осилил :)
Но в целом там алгоритм такой: берём такое простое число в такой степени, чтобы получить нужную длину сообщения. По факту все берут два в энной :) даже троичные MLC-флэшки никто не делает, хотя, казалось бы, сам Галуа велел в такой ситуации взять три в энной :) Строим для этого числа в этой степени поле Галуа, для чего нам нужен как раз полином (такой же или другой — см. выше мои сомнения :) но подозреваю, что такой же). Теперь у нас есть возможность закодировать сообщение, состоящее из допустимого набора значений, ну и длиной оно тоже равно то ли этому простому числу в энной степени, то ли то же самое минус единичка (не помню, давно было, был молодой и умный, и то осилил только первую степень, где всё элементарно).
А после этого мы уже не трогаем Галуа и начинаем мучить Фурье. Мы выделяем часть сообщения под коды коррекции ошибок, эти символы зануляем, остальные — забиваем инфой, делаем ЕМНИП обратное преобразование (при этом, естественно, вся арифметика у нас Галуа), выпуливаем в линию, принимаем на другом конце и пытаемся проделать ЕМНИП прямое преобразование Фурье (ну или наоборот, но вроде так). Если побилось не более 1/2 символов, выделенных под ККО — система уравнений имеет решение, и мы методом Берлекэмпа-Мэсси его таки находим. Вычитая найденную ошибку из сообщения, мы его восстанавливаем в изначальном виде.
Какой надо было иметь мозг, чтобы додуматься решать системы уравнений в полях Галуа — мне даже думать страшно. На уровне идеи всё понятно и ощущается гениально, но лезть в это… сверхлюди.
Так что количество контрольных символов очень вряд ли влияет на порождающий полином, а вот длина сообщения в целом… ну, как минимум, выбор степени, в которую мы возведём простое число — целиком на совести требуемых рамок длины этого сообщения.
Спасибо, очень интересно - руки чешутся попробовать разобраться
Ну там у меня более-менее комментарии есть, да и пример максимально упрощённый, да и плюс я тут — подскажу, если что :)
Не очень то я в плюсах :(
Почитал несколько статей про эти коды РС(Рида-Соломона) - что то как то "рыхло", куча способов реализации, в общем нарыл следующее - в кодах РС у понятия "порождающий полином" два разных применения:
"порождающий полином" для полей Галуа, полностью повторяет то, что я имею в виду в своей статье.
"порождающий полином" для кодов РС, используемый на этапе кодирования, в одной статье видел его название как "полином-генератор" (с англ. generator polynomial) так и буду в дальнейшем его называть, чтобы не путать с первым.
А в этой статье - это прямо видно, скрин привожу:
Добавляет непонятности, что использование порождающего ("неприводимого" как на скрине) полинома является необязательным. Например, если используется поле 
, так как результат можно получить по 
. Также, кажется и у Вас в проекте, дали подсказку - PrimeNumber^1
Еще в статье порождающий полином тоже не использовался, так как поле 
. В этой статье комментарии очень интересные.
Еще больше непонятности добавляет, что и "полином-генератор" (2-е применение) является кажется необязательным, привожу цитату из комментариев из выше приведенной статьи (поправил немножко):
... Ваш алгоритм похож на тот, который мы изучали. Методы, которые у нас были по кодированию:
1) чистое DFT;
2) несистематическое кодирование с g(x);
3) систематическое кодирование с g(x) и вычислением остатка;
4) систематическое кодирование с полиномом парности.
...
Таким образом, если нужно перейти на более чем первую степень, т.е. использовать поле 
, при 
, понадобится порождающий полином для полей Галуа.
Про "полином-генератор" (2-е применение) не буду говорить, так как не разбираюсь.
Вроде так
Спасибо, может быть, это мне поможет всё-таки со своей стороны одолеть Вашу половину этой математической хтони, а не подбрасывать Вам свою половину :-D
Почитал вики по РС - там действительно несколько порождающих многочленов. Приведу краткую выжимку. @NickDoom
Берём конечное поле F, размера q - это наши передаваемые символы, они же байты.
Сообщения для передачи разбиваются на блоки размера k. Каждый блок рассматривается как многочлены степени не выше k, над полем F. Иными словами, блоку сопоставляются многочлен m(x), где коэффициент перед x^i будет i-ым символом(байтом) в блоке.
Далее рассматривается кольцо P многочленов над F, по модулю x^n - 1. Элементами этого кольца являются многочлены степени не выше n. Множество сообщений вкладывается в это пространство.
Кодовые слова, они же - закодированные блоки, представляются в виде многочленов из P. При этом, в отличии от сообщений, не всякий многочлен степени n является кодовым словом (т.е. не все многочлены могут получиться при кодировании). Множество тех многочленов, которые могут получиться при кодировании называют C.
При довольно общих соображениях, можно показать, что C является главным идеалом. То есть, есть такой многочлен g(x) из P, который делит все кодовые слова.
Тогда процесс кодирования выполняется просто умножением на g(x). Пусть у нас есть блок m(x), мы хотим его закодировать и получить кодовое слово c(x). Тогда c(x) = m(x)g(x).
Теперь можно разобраться с порождающими многочленами. Дело в том, что у нас есть два вида многочленов здесь. С одной стороны, у нас есть кольцо P многочленов p(x), с другой стороны, у нас есть конечное поле F, которое строиться через многочлены f(u). То есть, поле F задаётся как многочлены f(u) по модулю a(u).
Итого, у нас есть:
Порождающий многочлен a(u) поля F
Порождающий многочлен g(x) для идеала C - он же порождает сам код РС.
(Не сильно важно, но ещё есть порождающий многочлен x^n - 1 кольца P).
P.S. Замечу, что озвученная выше теория не является специфичной для кодов РС. Она верна для гораздо более широкого класса кодов - циклических кодов. Конкретно коды РС определяются особенным способом построения многочленов g(x).
" Количество примитивных полиномов определяется функцией Эйлера " ..
Утверждение ложно . Например для поля F9 имеется 16 примитивных многочленов , а по вашей формуле получается 2...
Вывести можно лишь число нормированных неприводимых многочленов степени n , где участвует функция Мебиуса от делителей числа n , помноженная на степеня n по всем делителям и все это деленное на n .
Утверждение ложно . Например для поля F9 имеется 16 примитивных многочленов , а по вашей формуле получается 2...
Во-первых, формула подтверждается эмпирическим путем.
Во-вторых, Вы мне льстите - это не моя формула, если бы я имел отношение к данной формуле, я бы не преминул это указать.
Кстати, в самой статье я привел ссылку на статью где приведена данная формула, если не достаточно, вот еще.
А у Вас что-то с расчетом не то.
Я писал : количество примитивных многочленов в поле GF( 9 ) ...
Вопрос лишь в том , что такое примитивный многочлен степени m над полем GF( q ) , где q = p^m ( m = 1 - частный случай ) . И их количество не определяется функцией Эйлера....
С этим могу согласиться, смысла для поля 
искать порождающие полиномы нет. В статье так и написано:
Для
Единственное, у Вас неудачный пример с 
, так как 9 не простое число - мультипликативную группу по этому полю не построить, для 9 элементов нужно использовать поле 
Согласен, что поиск примитивных многочленов над не простым полем, то есть над полем GF(p^n) , задача “так себе” – представляет из себя чисто теоретический интерес . Но суть не в этом. У вас, во-первых, не совсем корректное определение примитивного многочлена над простым полем ( в частности ) .
Дело в том , что у вас путаница с понятием примитивный элемент и примитивный многочлен над конечным полем. Поэтому я привел не простое поле в качестве намека .
Например , вы пишите : “ … примитивный элемент может не определится …” Но дело в том , мультипликативная группа ненулевых элементов конечного поля GF(q) – циклична ( здесь q – не обязательно простое число ) , а ее образующий элемент называется примитивным элементом . Их , как известно , fi (q-1 ) , где ( у меня так обозначено ) fi – функция Эйлера . Подозреваю , вы путаете фактор -кольцо кольца целых чисел по главному идеалу ( или проще – кольцо классов вычетов ) , с фактор – кольцом кольца целых чисел по главному идеалу от простого числа , которое является полем – в нем обязательно будет примитивный элемент , так как это конечное поле . В любом поле , даже если его мультипликативная группа состоит из q элементов , где q – не простое число , всегда будет примитивный элемент и не всегда один . Точнее :
Мультипликативная группа ненулевых элементов конечного поля GF(q) – циклична ( здесь q – не обязательно простое число ) , а ее образующий элемент называется примитивным элементом . Их , как известно , fi (q-1 ) , где ( у меня так обозначено ) fi – функция Эйлера .
Поехали далее :
Есть такая теорема – если многочлен степени n - f(x) принадлежит GF(q)(x) и является неприводимым , то любой корень этого многочлена принадлежит полю GF(q^n) .Более того , его полем разложения над полем GF(q) является GF( q^m ) и поля любых двух разных неприводимых многочленов одной и той -же степени изоморфны друг другу .
Другими словами : Кольцо многочленов по модулю некоторого неприводимого в поле GF(q)
многочлена p(x) степени m является полем GF(q^m). Здесь везде q – не обязательно простое.
Далее , вы пишите : “…порождающий полином неприводим и примитивен …”
Как видно из вышеописанного – это неверно . Достаточно неприводимости . Я приводить пример не буду , вы его сами привели взяв порождающий многочлен x^2+1 для поля GF( 3^2) – очевидно , что этот многочлен не примитивен.
Так вот , одно из определений : порождающий многочлен , это такой неприводимый над полем многочлен , который имеет примитивный корень в расширенном поле , точнее – все его корни будут примитивными .
Теперь переходим к полю GF(p^n ) . Так как его мультипликативная группа циклична , то она состоит из всех корней многочлена x^q-1=0 , где q= p^n -1 .
Например :
GF(2^2) имеем : x^3-1=(x-1)(x^2+x+1 ) . Как видим – единственный примитивный многочлен это x^2+x+1 GF(2^3) имеем : x^7-1=(x-1)(x^3+ x^2 +1 )(x^3+x+1) . Как видим – два примитивных многочлена это x^3+x^2+1 и x^3+x+1 GF(3^2) имеем : x^8-1=(x^4+1)( x^2 +1 )(x-1)(x+1)=(x^2+x+2)(x^2+2x+2)(x^2+1)(x-1)(x-2) . Как видим – два примитивных многочлена это x^2+2x+2 и x^2+x+2
И вообще , есть такая теорема – если n не делится на характеристику поля GF(q) , то многочлен x^n -1 разлагается в произведение так называемых циклических многочленов Qd(x) над его простым полем , где произведение берется по всем делителям числа n .
Круговой многочлен Qd(x) = П ( x^(n/d)-1) ^ mu(d) , где произведение берется по всем делителям числа d числа n ( здесь mu – функция Мебиуса .
В частности :
Qp(x) ( p- простое ) = 1+ x+x^2+x^3+…x^(p-1)
Qp^k(x) ( p -простое )
=(x^p^k-1)/(x^p^(k-1)-1)= 1+x^p^(k-1) +x^(2p^(k-1))+ x^(3p^(k-1))+… x^((p-1)p^(k-1)) Например : Q3(x)=1+x+x^2 – сразу получаем примитивный многочлен для GF(2) Q5(x)=1+x+x^2+x^3+x^4 Q15(x)=x^8+x^7+x^5+x^4+x^3+x+1 И так как Q5(x+1)=x^4+x^3+1 ( для GF(2) ) – неприводимый многочлен в этом поле , то он делит Q15(x)= ( x^4+x^3+1)( x^4+x+1)
То есть получаем для GF(2^4) два примитивных многочлена x^4+x^3+1 и x^4+x+1 над полем GF(2)
Да , вы правы – формула верна . Я всегда был уверен , что она верна для простых полей . Сейчас освежил память , так как все это было очень-очень давно . И действительно – даже если в поле имеются не примитивные подполя , формула верна . Так что извиняюсь .
Только мне не понятно , зачем искать примитивные многочлены простым перебором . Можно сократить сильно поиски , используя например ( не залезая уж совсем в дебри алгебры ) круговые многочлены :
Пусть имеется поле GF(p^n) . Как известно , его мультипликативная группа состоит из q=p^n-1 элементов . Есть такая теорема :
Произведение всех неприводимых многочленов степени m ( обозначается I(q,m,x) ) равно произведению круговых многочленов Qk(x) , где произведение берется по таким k- делителям числа q , для которых m – минимальная степень p , такая что : p^m=1(mod(k)) .
Очевидно , что в этом произведении присутствует круговой многочлен Qq(x) и там , и только там присутствуют все примитивные элементы степени fi (q) , которых fi (q)/n .
Пример :
Пример GF(2^5)
x^31= Q1(x)* Q31(x)
Q1(x)=x-1
Q31(x)=(x^31-1)/(x-1)
I(2,5,x)= Q31(x) . То есть все неприводимые многочлены – примитивны . Так как многочлены 2 и 3 степени неприводимы над полем тогда и только тогда , когда у них нет корней в этом поле , то не трудно видеть , что такими многочленами являются x^2+x+1 , x^3+x+1 и x^3+x^2+1 . Исключая из произвольного многочлена 5 степени такие z : z^2=z+1 и z^3= z+1 и z^3=z^2+1 простым перебором , даже в ручную довольно быстро получаем все примитивные многочлены :
1+x^2+x^5
1+x+x^2+x^3+x^5
1+x^3+x^5
1+x+x^3+x^4+x^5
1+x^2+x^3+x^4+x^5
1+x+x^2+x^5+x^4
Пример GF(2^6)
x^63-1= Q1(x)* Q3(x)* Q7(x)* Q9(x)* Q21(x)* Q63(x)
Q1(x)=x-1
Q3(x)=x^2+x+1
Q7(x)=x^6+x^5+x^4+x^3+x^2+x+1
Q9(x)=x^6+x^3+1
Q21(x)=x^12+x^11+x^9+x^8+x^6+x^4+x^3+x+1=( x^6+x^4+x^2+x+1)*(x^6+x^5+x^4+x^2+1) =P1(x)*P2(x)
Q63(x)….
I(2,6,x)=Q9(x)Q21(x)Q63(x) . Как видим -Q7(x) не входит в это произведение ,а значит он разлагается . И действительно : Q7(x+1) = x^6+x^5+x^4+x^3+x^2=x^2(x^4+x^3+x^2+1) . То есть Q7(x)=(x^2+1)(x^4+x^3+1)
Так как Q9(x) ,P2(x)- неприводимыe многочлены , то не приводимые и
Q9 (x+1)= x^6+x^4+x^3+x+1
P2(x+1)= x^6+x^5+x^2+x+1
Так как только x^2+x+1, x^3 +x+1 и x^3+x^2+1 неприводимые многочлены степени не выше третей , то неприводимы и
x^6+x+1
(x^2+x+1)*x^4+x+1=x^6+x^5+x^4+x+1= P3(x)
P3(x+1)= x^6+x^5+1
Итак : f(x) = x^6+x^4+x^3+x+1 , x^6+x^5+x^2+x+1, x^6+x+1 , x^6+x^5+x^4+x+1 , x^6+x^5+1 – примитивные многочлены над GF(2) , а значит порождающие поле GF(2^6) . C ходу не получается найти лишь последний .
Только мне не понятно , зачем искать примитивные многочлены простым перебором . Можно сократить сильно поиски , используя например ( не залезая уж совсем в дебри алгебры ) круговые многочлены
Наверное в ваших рассуждениях есть смысл - попробуйте сами реализовать свою идею.
Я честно говоря уже "охладел" к конечным полям, на столе лежит другой проект.
существуют ли другие сервисы для определения порождающих полиномов?
Если я правильно понял суть статьи, то в Wolfram Mathematica есть функция PrimitivePolynomialQ.
Как сгенерировать порождающие полиномы для конечных полей