Полигон-2

Rio444 написал:

[q]

Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".

[/q]

Приоритет сложения в Си выше, наверно имеется ввиду
c = (x^8) + (x^4) + (x^2) + (x^1);

Это означает инвертирование бита3, потом 2, потом 1, потом 0 и сложение результатов (сам x при этом не меняется)

Те если например X = 1100 (двоичные)

0100 +
1000 +
1110 +
1101 +
100111 (0x27)

Вот здесь http://radiohlam.ru/?p=1406 немножко поподробнее и попонятнее.

petrenko написал:

[q]

Ну а в чём противоречие то ?

Вот ежели в десятичной позиционной системе цифра домножает-ся на (основание==[10dec])^N ,т.е. в степени N , равной позиции цифры
, то в двоичной позиционной отчего бы этому быть не так ?

[/q]

Так если бы было "2^8 + 2^2 + 2^1 + 2^0", то было бы вполне понятно.
Но

[q]

Что означает "х"? При чем тут степени?

[/q]

xoiss написал:

[q]

всё понятно?

[/q]

Спасибо, почти.

xoiss написал:

[q]

в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:

[/q]

Что такое разделить, понимаю.
Что значит "по модулю P"?

Rio444 написал:

[q]

Что такое разделить, понимаю.
Что значит "по модулю P"?

[/q]

множества чисел (или множества "объектов", в общем случае) бывают бесконечными и конечными
и те и другие — "мамы всякие нужны, мамы всякие важны"

арифметические операции на бесконечных множествах — это обычные сложение, умножение и пр.

на КОНЕЧНЫХ же множествах (на интервалах целых чисел, например) так вот просто операцию сложения не введёшь, т.к. результат может оказаться за пределами множества
// например, на множестве чисел 0..9 если сложить 5+5, то результат 10 не будет принадлежать этому множеству, хотя слагаемые принадлежат
такая "недоделанная" операция сложения на конечных множествах не имеет практического смысла

поэтому придумали операцию сложения по модулю — ну, а почему бы и не придумать
её основное свойство в том, что результат сложения-по-модулю всегда принадлежит тому же множеству
// обычную операцию сложения на бесконечных множествах можно, кстати, рассматривать как "сложение по модулю бесконечности"

короче, сложение-по-модулю — это как бы "просто сложение", но только на конечных множествах целых чисел
никакой особой супер магии в нём нет — просто это ЕДИНСТВЕННЫЙ вариант, как ещё адекватно прикрутить операцию сложения чисел к конечным множествам чисел

для множества { 0 ... (N-1) } сложение по модулю — это будет сложение по модулю N — ну, по определению
например, если N=12, а множество будет 0..11, то сложение по модулю (7 + 8) mod 12 = 3
// см. "остаток от деления" — это суть то же самое в данном случае

если на множестве (чисел, полиномов, объектов) определена операция сложения (сложения по модулю), то можно определить объект-ноль — это такой, который будучи прибавленным к любому объекту множества даёт тот же самый объект
// не каждое множество имеет объект-ноль... например, множество 2..9 не имеет

далее, на множестве можно определить операцию умножения по модулю
ну, она определяется, как и обычно, как многократное сложение по модулю

в множестве можно определить объект-единицу — это такой, который будучи умноженным на любой объект из множества даёт его же

// ... пытаюсь объяснять "на пальцах", поэтому не буду использовать мат.термины типа группы, кольца и пр. — но если есть желание, то посмотрите их сами
https://ru.wikipedia.org/wiki/Кольцо_(математика)

// понятно, что примеры с числами - это лишь частный случай

далее можно определить обратный элемент к данному — это такой, который будучи умноженным по модулю на данный элемент (на элемент, которому он обратен) даёт объект-единицу

умножение-по-модулю на обратный-по-модулю элемент к данному можно считать делением-по-модулю на данный элемент, в каком-то смысле
// один пример деления-по-модулю я приводил в пред. комменте
ещё раз обращаю внимание, что деление-по-модулю в общем случае даёт совсем не такой результат, как обычное деление

... далее... интересные свойства наблюдаются в том случае, если модуль N является простым числом — поэтому я и обозначил его P в пред. комменте
что за интересные свойства? ну, долго перечислять и даже не знаю, с чего начать — не столько интересные они, сколько полезные в плане массы практических приложений
например, там всегда существует объект, обратный к данному, — а значит вполне определена операция деления-по-модулю, что офигительно полезно в ряде прикладных задач теории чисел

ещё один пример деления по модулю:
пусть модуль будет P=13 (простое число)
множество тогда будет 0..12
поделим 6 на 3 по модулю 13 в этом множестве
для этого надо сначала найти элемент, обратный 3 по модулю 13
// сразу скажу, что (1) он существует, и (2) он определён единственным образом!
не вдаваясь в детали, элемент обратный 3 по модулю 13, — это 9 // проверим: (9*3) mod 13 = (27) mod 13 = 27-13-13 = 1 — действительно, получилась единица
теперь умножаем 6 на 9 по модулю 13: (6*9) mod 13 = (54) mod 13 = 54-13-13-13-13 = 2
итак, частное от деления 6 на 3 по модулю 13 равно, как ни странно, 2

другой пример:
пусть модуль будет P=13 (простое число)
множество тогда будет 0..12
поделим 5 на 3 по модулю 13 в этом множестве
ну, обратный элемент к 3 мы уже знаем — это 9
теперь умножаем 5 на 9 по модулю 13: (5*9) mod 13 = (45) mod 13 = 45-13-13-13 = 6
итак, частное от деления 5 на 3 по модулю 13 равно ... 6 --- внезапно

то есть вывод: деление по модулю на конечных множествах чисел (ну, не хочу я использовать официальные мат.термины) в общем случае даёт непривычные числовые результаты
ну, как прибили — так и держится, что тут скажешь ---- зато профит в том, что результат получается целым числом и никаких "остатков от деления"!!! (ну, если модуль P - это простое число)


стало ли хоть как-то понятней, что такое "модуль" ?
... и что такое "разделить по модулю" ??