Комментарии 18
Что будет именно в этой статье: коротко рассмотрим теорию... посмотрим как быстро вычислять... Спасибо за конструктивную критику.
Итог: коротко не не вышло, быстро не получилось.
Плюсы: кратко и ясно даны базовые понятия (поле, порождающий полином, ...).
Минусы: низкая структурированность плюс полотна текста, что совокупно порождает сложность следить за ходом мысли. Не многие "дожмут" статью до конца.
Как минимум спрячьте примеры и частности под кат. :)
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-е применение) не буду говорить, так как не разбираюсь.
Вроде так
" Количество примитивных полиномов определяется функцией Эйлера " ..
Утверждение ложно . Например для поля 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 ходу не получается найти лишь последний .
Только мне не понятно , зачем искать примитивные многочлены простым перебором . Можно сократить сильно поиски , используя например ( не залезая уж совсем в дебри алгебры ) круговые многочлены
Наверное в ваших рассуждениях есть смысл - попробуйте сами реализовать свою идею.
Я честно говоря уже "охладел" к конечным полям, на столе лежит другой проект.
Как сгенерировать порождающие полиномы для конечных полей