[Paul Kellerman]

Пусть над простым полем Галуа GF(p) заданы два многочлена a(x) и b(x),
и определены операции сложения многолченов, умножения многочленов,
и вычисления остатка одного многочлена по модулю другого многочлена.

Тогда, насколько я помню в общем виде свертка многочленов выглядит:

c(x) = (a(x)*b(x)) mod g(x)

Если deg(g(x)) > deg(a(x)) + deg(b(x)), то имеем линейную свертку, кото-
рая по сути совпадает с произведением многочленов a(x) и b(x), если же
deg(g(x)) <= deg(a(x)) + deg(b(x)), то в случае если g(x) неприводим над
полем GF(p) то имеем полевую свертку, а если g(x) = x^r - 1, то свертка
называется циклической. Однако я нигде не нашел комментариев по по-
воду остальных случаев, когда g(x) не является неприводимым, но в то
же время он не выглядит как x^r - 1. Например, как называется свертка
вида (a(x)*b(x)) mod (x^r), которая легко получается путем вычисления
произведения многочленов a(x) и b(x) с последующим "отбрасыванием"
слагаемых со степенями выше r ? Усеченной сверткой или как-то еще?