Rio444 писал(а):Всё, что между ними - темный лес. Или я туплю, или авторы статей переписывают друг у друга однотипные фразы, не вникая в них.
Полиномы (они же многочлены) изучал ещё в ВУЗе.
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
Что означает "х"? При чем тут степени?
Каким образом итоговый код соотносится с делением на полином?
Кто-нибудь разобрался?
https://ru.wikipedia.org/wiki/Циклический_код
там всё понятно написано
(ну, правда, надо алгебру знать, чтоб прочитать)
если "на спичках", то полином -- это просто такая модель
// например, как ёмкость и индуктивность можно представить мнимой компонентой комплексного сопротивления
можете вместо полиномов использовать двоичные записи целых чисел -- наверное, так будет понятней и наглядней
// полиномы в этой теории появились только потому, что во времена, когда эту теорию изобрели, учёные знали, что такое полиномы, а вот двоичные числа пока ещё были не в тренде
"икс" тут вообще нипричём
считайте, что степень икса - это просто индекс при очередном коэффициенте (который 0 или 1)
суть - в коэффициентах
иксы тут это просто формальная переменная, в неё никто никогда ничего не подставляет
короче, проще и понятней работать не с полиномами, а с двоичными записями целых чисел
умножение полиномов == умножение двоичных чисел
разложение полинома на полиномы-сомножители == разложение целого числа на его множители, с представлением всех таких множителей в двоичной записи
"деление на полином" == деление на целое число
только здесь есть один нюанс, там на самом деле не "деление", а умножение на "обратную величину"
и это суть не то же самое
в некоторых множествах, например, у объекта может не существовать обратной величины (т.е. такой величины, которая при умножении на исходный объект даёт объект-единицу) -- тогда на такой объект "поделить" нельзя
и ещё один нюанс, все операции выполняются по модулю!
поэтому результат такого "деления по модулю" (а точнее "умножения по модулю на обратную величину") - это совсем не равно обычному делению
в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:
- найти такой полином B^-1, который является обратным данному полиному B по модулю P
- умножить полином A на полином B^-1 по модулю P
здесь вместо "полином" можно использовать "двоичное целое число"
пример (на числах):
- пусть P = 7 (двоичная запись 111)
- пусть A = 3 (двоичная запись 11)
- пусть B = 4 (двоичная запись 100)
- тогда (B^-1) mod P = "такое число, которое будучи умноженным на 4 по модулю 7, даст 1" = 2 --- т.е. B^-1 = 2 (двоичная запись 10)
// действительно (2*4) mod 7 = 8 - 7 = 1
!! короче, число 2 -- есть обратная величина (ну типа как 1/n) для числа 4 по модулю 7
- тогда (A / B) mod P =def= (A * (B^-1) mod P) mod P = (3 * 2) mod 7 = 6 (двоичная запись 110)
итак, мы получили, что 3 делённое на 4 по модулю 7 даёт 6
можно, кстати, проверить результат обратным умножением... т.е. 6 умноженное на 3 по модулю 7 должно дать 4 -- проверим...
... действительно (6*3) mod 7 = 18 - 7 - 7 = 4 ---- внезапно сошлось!
теперь от "чисел" перейдём к их двоичным записям...
получим: 11 делённое на 100 по модулю 111 даёт 110
а теперь перейдём к нашим полиномам...
получим:
полином (x+1) делённый на полином (x^2) по модулю (x^2 + x + 1) даёт полином (x^2 + x)
всё понятно?