[AHTOXA 15]

Так а как раскодировать, если для двух разных данных может быть одинаковая CRC? Как принять решение, какое из этих двух данных корректное?

Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Поэтому в качестве закодированных данных подходит любая последовательность, которая даёт нужную CRC.

[SM 0]

Очевидно,

Это не доказательство. Вот для арифметического деления, доказательство четкое (математически), что однозначности нет. По причине того, что число G, выступающее в роли делителя, больше, чем 2^(N-1), где N - разрядность числа. И, поэтому, остатки от деления DATA mod G, большие, либо равные, чем 2^(N-1), зацикливаются внутри байта из-за отбрасывания старшего бита. Было бы логично распространить это и на полиномы. Потому, что там аналогия полная - полином на 1 разряд больше, чем CRC, поэтому результат от деления полиномов должен бы также зацикливаться внутри этого числа разрядностью на 1 меньше, чем полином, приводя к дублям.

 

"Очевидно" - нет такого термина. Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010" , что соответствует полиному x^4+x - остаток от деления на x^4+x^1+1 будет равен x^4+x, что соответствует числу 2, если оставить 4 бита. Проверяем - 0*(x^4+x^1+1) + (x^4+x) = x^4+x - проверка показала, в делении не ошиблись, остаток именно такой. И, одновременно, для данного "0000 0010", что соответствует полиному x^1, остаток от деления на x^4+x^1+1 равен x^1, что также соответствует четырехбитному числу 2. Проверяем - 0*(x^4+x^1+1) + x^1 = x^1. Проверка опять показала, что поделено правильно, и остаток именно такой.

 

Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование.

 

Вопрос - как при помощи некой функции закодировать данные так, чтобы они раскодировались методом подсчета CRC. Я не уверен в том, что существует такая функция в принципе (то есть, математически, является функцией, сопоставляя каждому аргументу из ее области определения единственное значение результата). То, что можно подобрать такой поток данных, чтобы на выходе получить требуемую последовательность - да с этим никто не спорит ни разу!

[ViKo 1]

Насколько я понял, раскодирование заключается в вычислении CRC. Это однозначное преобразование. Поэтому в качестве закодированных данных подходит любая последовательность, которая даёт нужную CRC.

Раскодировать нужно не в одно число, а весь массив. Слово за словом, используя аппаратный блок CRC. Задача, что подсунуть этому блоку, чтобы после каждого вычисления CRC получался исходный код.

В интернете это называется reversing CRC.

http://stackoverflow.com/questions/1514040/reversing-crc32

Вижу, математики запутали своим полиномиальным делением. Куда логичнее по-инженерному пользоваться регистрами сдвига и исключающим ИЛИ. Не вижу препятствий написать реверсивный алгоритм CRC, двигая данные в регистре в обратную сторону. :rolleyes: XOR, естественно, тоже ... тоже что-то с ними сделать. :rolleyes:

 

Мне вот, очевидно, что для CRC4 будет для входных данных "0001 0010"...

Это уже пара данных, требующая в данной задаче двух выходных CRC.

[SM 0]

Это уже пара данных, требующая в данной задаче двух выходных CRC.

Так и речь именно о паре (или больше). Что при одном четырехбитном данном при инициализации нулями будет однозначность, это, вроде, вопрос бесспорный. С арифметическим аналогом тоже самое - при начальном значении, меньшим, чем делитель-256, тоже все однозначно для одного байта. Неоднозначности начинаются, когда байт больше, или начальное значение больше определенного. Просто, я неудачную пару данных привел, наоборот, когда для двух разных начальных значений будет одинаковый код на выходе для одинаковых данных. Подобрать наоборот? Чтобы для одного начального значения и двух разных данных получился одинаковый полином?

[ViKo 1]

Полином CRC известен, он не от балды берется. x^4 + x^1 + 1. Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число (от предыдущего расчета) - это к вопросу о начальном значении. Не подберете. :)

 

Давайте так.

Я могу подобрать некое 32-битовое число, которое после вычисления CRC-32, инициализированной нулями, даст на выходе нужное мне значение? Да.

Я могу подобрать некое 32-битовое число, которое после вычисления CRC-32, инициализированной неким известным числом, даст на выходе нужное мне значение? Да.

[SM 0]

Полином CRC известен, он не от балды берется. x^4 + x^1 + 1. Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число (от предыдущего расчета) - это к вопросу о начальном значении. Не подберете. :)

 

0x35. 0011 0101 - это x^5+x^4+x^2+1. Делим на x^4+x+1. Получаем частное (x+1), остаток 0 (обрезав до 4 бит, тоже ноль). Проверяем (x+1)*(x^4+x+1) = x^5+x^2+x+x^4+x+1 = x^5+x^4+x^2+1 - сходится.

0x36. 0011 0110 - это x^5+x^4+x^2+x. Делим на x^4+x+1. Получаем частное (x), остаток x^4 (обрезав до 4 бит, тоже ноль). Проверяем x*(x^4+x+1)+x^4 = x^5+x^2+x+x^4 = x^5+x^4+x^2+x - сходится.

 

Для чисел 0x30...0x3F полные остатки от деления, не обрезая до 4 бит, затем, в скобках, частное, и, в конце, остаток, обрезая до 4-х бит:

 

30 mod 13 = 05 (div=03) => 5

31 mod 13 = 04 (div=03) => 4

32 mod 13 = 07 (div=03) => 7

33 mod 13 = 06 (div=03) => 6

34 mod 13 = 12 (div=02) => 2

35 mod 13 = 00 (div=03) => 0

36 mod 13 = 10 (div=02) => 0

37 mod 13 = 11 (div=02) => 1

38 mod 13 = 0D (div=03) => D

39 mod 13 = 0C (div=03) => C

3A mod 13 = 0F (div=03) => F

3B mod 13 = 0E (div=03) => E

3C mod 13 = 09 (div=03) => 9

3D mod 13 = 08 (div=03) => 8

3E mod 13 = 0B (div=03) => B

3F mod 13 = 0A (div=03) => A

 

нет такого числа, чтобы получить с тройкой в старшем полубайте число три на выходе. Зато ноль можно получить двумя способами. Проверить многочлены перемножением можно все - я ради проверки это сам проделал для всех приведенных чисел ручкой на бумаге. Проверки для двух нулей привел выше. UPD: до числа 0x35 - обратимость присутствует везде. И, далее, тоже не все "приписки" необратимы.

 

А вот, если "переделить" - то есть, продолжать деление, если в остатке присутствует x^4, но остаток уже меньше, чем полином-делитель (то есть, деление по факту уже закончено, так как остаток УЖЕ меньше, чем делитель, и он ну никак не может больше делиться на него, но, все равно, тупо и нагло выполнить итерацию), то обратимость появится, и при этом тоже проверка будет сходиться:

 

30 mod 13 = 05 (div=03)

31 mod 13 = 04 (div=03)

32 mod 13 = 07 (div=03)

33 mod 13 = 06 (div=03)

34 mod 13 = 01 (div=03)

35 mod 13 = 00 (div=03)

36 mod 13 = 03 (div=03)

37 mod 13 = 02 (div=03)

38 mod 13 = 0D (div=03)

39 mod 13 = 0C (div=03)

3A mod 13 = 0F (div=03)

3B mod 13 = 0E (div=03)

3C mod 13 = 09 (div=03)

3D mod 13 = 08 (div=03)

3E mod 13 = 0B (div=03)

3F mod 13 = 0A (div=03)

[ViKo 1]

Могу только повторить - 0x30...0x3F не укладываются в диапазон, который дает однозначное соответствие остатка от деления исходному числу. В данном случае CRC 4-битовая, значит, и числа должны быть 4-битовые.

Ага, значит, приписали к 0..F впереди 3... сейчас...

неправильно поделили, остаток от деления 0x36 на 0x13 будет 1 (5 вышло, промахнулся). 0x37 mod 0x13 = 6.

 

Для 0x30 mod 0x13 я получил частное 0x35 и остаток 0xF.

 

0x30 / 0x13 = 0x35, 0xF

0x31 / 0x13 = 0x34, 0xC

0x32 / 0x13 = 0x37, 0x9

0x33 / 0x13 = 0x36, 0xA

0x34 / 0x13 = 0x31, 0x3

0x35 / 0x13 = 0x30, 0x0

0x36 / 0x13 = 0x33, 0x5

0x37 / 0x13 = 0x32, 0x6

0x38 / 0x13 = 0x3C, 0x4

0x39 / 0x13 = 0x3D, 0x7

0x3A / 0x13 = 0x3E, 0x2

0x3B / 0x13 = 0x3F, 0x1

0x3C / 0x13 = 0x38, 0x8

0x3D / 0x13 = 0x39, 0xB

0x3E / 0x13 = 0x3A, 0xE

0x3F / 0x13 = 0x3B, 0xD

 

 

Методика деления описана в статье http://www.info-system.ru/library/algo/crc1.pdf

 

upd. Исправляю остатки - выбрасываю старший 0. Тогда CRC от последовательности исходного числа и остатка даст 0. Это связано с разрядностью используемых чисел, в данном случае 4.

Для проверки в CRC калькуляторе нужно задавать 30F0.

[SM 0]

Могу только повторить - 0x30...0x3F

 

И я могу только повторить. Что 0x30 - это пара 4-битных чисел. Сначала 3, потом 0. И даже Вашу же просьбу процитировать:

 

Вы подберите два разных 4-битовых числа, которые при делении на 10011 дадут одинаковый результат - остаток. Перед числами можете приписать в старших разрядах любое одно и то же число

 

Вот я и приписал 0x3 к паре чисел, 0x5 и 0x6. Получилось 0х35 и 0х36.

 

0x37 mod 0x13 = 6.

 

Извините, ошибочка у Вас. А частное сколько? Пробуем проверить для x и для (x+1). 6 - это 0110 - это x^2+x

 

(x+1)*(x^4+x+1) + (x^2+x) = x^5+x^2+x+x^4+x+1+x^2+x = x^5+x^4+x+1 - это 0x33, а никак не 0x37. (что и подтверждается у меня, собственно, 0x33 mod 13 = 6)

x*(x^4+x+1)+(x^2+x) = x^5+x^2+x+x^2+x = x^5 - это, вообще, 0x20, далеко от темы (и опять, у меня подтверждается, ниже запостил весь список).

 

Считайте лучше! Тоже касается и 36 mod 13 = 1 - Вы хоть сами бы проверили умножением, прежде чем сюда то писать.

 

Для 0x30 mod 0x13 я получил частное 0x35 и остаток 0xF.

А проверить????

0x35 - x^5+x^4+x^2+1, 0x0F - x^3+x^2+x^1+1

(x^5+x^4+x^2+1)*(x^4+x+1) + (x^3+x^2+x^1+1) - это уже имеет член x^9, которого близко не было! Для этого третий полубайт нужен!

 

0x31 / 0x13 = 0x34, 0x0C

Заканчивайте писать лажу, ПРОВЕРЯЙТЕ УМНОЖЕНИЕМ!!!! Должно сходиться div*(x^4+x+1)+mod = исходное число! У Вас и близко не сходится.

 

Вот результат (ПРОВЕРЕННЫЙ УМНОЖЕНИЕМ!!!!) для всех пар 4-битных чисел :

00 mod 13 = 00 (div=00)
01 mod 13 = 01 (div=00)
02 mod 13 = 02 (div=00)
03 mod 13 = 03 (div=00)
04 mod 13 = 04 (div=00)
05 mod 13 = 05 (div=00)
06 mod 13 = 06 (div=00)
07 mod 13 = 07 (div=00)
08 mod 13 = 08 (div=00)
09 mod 13 = 09 (div=00)
0A mod 13 = 0A (div=00)
0B mod 13 = 0B (div=00)
0C mod 13 = 0C (div=00)
0D mod 13 = 0D (div=00)
0E mod 13 = 0E (div=00)
0F mod 13 = 0F (div=00)
10 mod 13 = 10 (div=00)
11 mod 13 = 11 (div=00)
12 mod 13 = 12 (div=00)
13 mod 13 = 00 (div=01)
14 mod 13 = 07 (div=01)
15 mod 13 = 06 (div=01)
16 mod 13 = 05 (div=01)
17 mod 13 = 04 (div=01)
18 mod 13 = 0B (div=01)
19 mod 13 = 0A (div=01)
1A mod 13 = 09 (div=01)
1B mod 13 = 08 (div=01)
1C mod 13 = 0F (div=01)
1D mod 13 = 0E (div=01)
1E mod 13 = 0D (div=01)
1F mod 13 = 0C (div=01)
20 mod 13 = 06 (div=02)
21 mod 13 = 07 (div=02)
22 mod 13 = 04 (div=02)
23 mod 13 = 05 (div=02)
24 mod 13 = 02 (div=02)
25 mod 13 = 03 (div=02)
26 mod 13 = 00 (div=02)
27 mod 13 = 01 (div=02)
28 mod 13 = 0E (div=02)
29 mod 13 = 0F (div=02)
2A mod 13 = 0C (div=02)
2B mod 13 = 0D (div=02)
2C mod 13 = 0A (div=02)
2D mod 13 = 0B (div=02)
2E mod 13 = 08 (div=02)
2F mod 13 = 09 (div=02)
30 mod 13 = 05 (div=03)
31 mod 13 = 04 (div=03)
32 mod 13 = 07 (div=03)
33 mod 13 = 06 (div=03)
34 mod 13 = 12 (div=02)
35 mod 13 = 00 (div=03)
36 mod 13 = 10 (div=02)
37 mod 13 = 11 (div=02)
38 mod 13 = 0D (div=03)
39 mod 13 = 0C (div=03)
3A mod 13 = 0F (div=03)
3B mod 13 = 0E (div=03)
3C mod 13 = 09 (div=03)
3D mod 13 = 08 (div=03)
3E mod 13 = 0B (div=03)
3F mod 13 = 0A (div=03)
40 mod 13 = 0C (div=04)
41 mod 13 = 0D (div=04)
42 mod 13 = 0E (div=04)
43 mod 13 = 0F (div=04)
44 mod 13 = 08 (div=04)
45 mod 13 = 09 (div=04)
46 mod 13 = 0A (div=04)
47 mod 13 = 0B (div=04)
48 mod 13 = 04 (div=04)
49 mod 13 = 05 (div=04)
4A mod 13 = 06 (div=04)
4B mod 13 = 07 (div=04)
4C mod 13 = 00 (div=04)
4D mod 13 = 01 (div=04)
4E mod 13 = 02 (div=04)
4F mod 13 = 03 (div=04)
50 mod 13 = 0F (div=05)
51 mod 13 = 0E (div=05)
52 mod 13 = 0D (div=05)
53 mod 13 = 0C (div=05)
54 mod 13 = 0B (div=05)
55 mod 13 = 0A (div=05)
56 mod 13 = 09 (div=05)
57 mod 13 = 08 (div=05)
58 mod 13 = 07 (div=05)
59 mod 13 = 06 (div=05)
5A mod 13 = 05 (div=05)
5B mod 13 = 04 (div=05)
5C mod 13 = 10 (div=04)
5D mod 13 = 11 (div=04)
5E mod 13 = 12 (div=04)
5F mod 13 = 00 (div=05)
60 mod 13 = 0A (div=06)
61 mod 13 = 0B (div=06)
62 mod 13 = 08 (div=06)
63 mod 13 = 09 (div=06)
64 mod 13 = 0E (div=06)
65 mod 13 = 0F (div=06)
66 mod 13 = 0C (div=06)
67 mod 13 = 0D (div=06)
68 mod 13 = 02 (div=06)
69 mod 13 = 03 (div=06)
6A mod 13 = 00 (div=06)
6B mod 13 = 01 (div=06)
6C mod 13 = 06 (div=06)
6D mod 13 = 07 (div=06)
6E mod 13 = 04 (div=06)
6F mod 13 = 05 (div=06)
70 mod 13 = 09 (div=07)
71 mod 13 = 08 (div=07)
72 mod 13 = 0B (div=07)
73 mod 13 = 0A (div=07)
74 mod 13 = 0D (div=07)
75 mod 13 = 0C (div=07)
76 mod 13 = 0F (div=07)
77 mod 13 = 0E (div=07)
78 mod 13 = 12 (div=06)
79 mod 13 = 00 (div=07)
7A mod 13 = 10 (div=06)
7B mod 13 = 11 (div=06)
7C mod 13 = 05 (div=07)
7D mod 13 = 04 (div=07)
7E mod 13 = 07 (div=07)
7F mod 13 = 06 (div=07)
80 mod 13 = 0B (div=09)
81 mod 13 = 0A (div=09)
82 mod 13 = 09 (div=09)
83 mod 13 = 08 (div=09)
84 mod 13 = 0F (div=09)
85 mod 13 = 0E (div=09)
86 mod 13 = 0D (div=09)
87 mod 13 = 0C (div=09)
88 mod 13 = 10 (div=08)
89 mod 13 = 11 (div=08)
8A mod 13 = 12 (div=08)
8B mod 13 = 00 (div=09)
8C mod 13 = 07 (div=09)
8D mod 13 = 06 (div=09)
8E mod 13 = 05 (div=09)
8F mod 13 = 04 (div=09)
90 mod 13 = 08 (div=08)
91 mod 13 = 09 (div=08)
92 mod 13 = 0A (div=08)
93 mod 13 = 0B (div=08)
94 mod 13 = 0C (div=08)
95 mod 13 = 0D (div=08)
96 mod 13 = 0E (div=08)
97 mod 13 = 0F (div=08)
98 mod 13 = 00 (div=08)
99 mod 13 = 01 (div=08)
9A mod 13 = 02 (div=08)
9B mod 13 = 03 (div=08)
9C mod 13 = 04 (div=08)
9D mod 13 = 05 (div=08)
9E mod 13 = 06 (div=08)
9F mod 13 = 07 (div=08)
A0 mod 13 = 0D (div=0B)
A1 mod 13 = 0C (div=0B)
A2 mod 13 = 0F (div=0B)
A3 mod 13 = 0E (div=0B)
A4 mod 13 = 09 (div=0B)
A5 mod 13 = 08 (div=0B)
A6 mod 13 = 0B (div=0B)
A7 mod 13 = 0A (div=0B)
A8 mod 13 = 05 (div=0B)
A9 mod 13 = 04 (div=0B)
AA mod 13 = 07 (div=0B)
AB mod 13 = 06 (div=0B)
AC mod 13 = 12 (div=0A)
AD mod 13 = 00 (div=0B)
AE mod 13 = 10 (div=0A)
AF mod 13 = 11 (div=0A)
B0 mod 13 = 0E (div=0A)
B1 mod 13 = 0F (div=0A)
B2 mod 13 = 0C (div=0A)
B3 mod 13 = 0D (div=0A)
B4 mod 13 = 0A (div=0A)
B5 mod 13 = 0B (div=0A)
B6 mod 13 = 08 (div=0A)
B7 mod 13 = 09 (div=0A)
B8 mod 13 = 06 (div=0A)
B9 mod 13 = 07 (div=0A)
BA mod 13 = 04 (div=0A)
BB mod 13 = 05 (div=0A)
BC mod 13 = 02 (div=0A)
BD mod 13 = 03 (div=0A)
BE mod 13 = 00 (div=0A)
BF mod 13 = 01 (div=0A)
C0 mod 13 = 07 (div=0D)
C1 mod 13 = 06 (div=0D)
C2 mod 13 = 05 (div=0D)
C3 mod 13 = 04 (div=0D)
C4 mod 13 = 10 (div=0C)
C5 mod 13 = 11 (div=0C)
C6 mod 13 = 12 (div=0C)
C7 mod 13 = 00 (div=0D)
C8 mod 13 = 0F (div=0D)
C9 mod 13 = 0E (div=0D)
CA mod 13 = 0D (div=0D)
CB mod 13 = 0C (div=0D)
CC mod 13 = 0B (div=0D)
CD mod 13 = 0A (div=0D)
CE mod 13 = 09 (div=0D)
CF mod 13 = 08 (div=0D)
D0 mod 13 = 04 (div=0C)
D1 mod 13 = 05 (div=0C)
D2 mod 13 = 06 (div=0C)
D3 mod 13 = 07 (div=0C)
D4 mod 13 = 00 (div=0C)
D5 mod 13 = 01 (div=0C)
D6 mod 13 = 02 (div=0C)
D7 mod 13 = 03 (div=0C)
D8 mod 13 = 0C (div=0C)
D9 mod 13 = 0D (div=0C)
DA mod 13 = 0E (div=0C)
DB mod 13 = 0F (div=0C)
DC mod 13 = 08 (div=0C)
DD mod 13 = 09 (div=0C)
DE mod 13 = 0A (div=0C)
DF mod 13 = 0B (div=0C)
E0 mod 13 = 12 (div=0E)
E1 mod 13 = 00 (div=0F)
E2 mod 13 = 10 (div=0E)
E3 mod 13 = 11 (div=0E)
E4 mod 13 = 05 (div=0F)
E5 mod 13 = 04 (div=0F)
E6 mod 13 = 07 (div=0F)
E7 mod 13 = 06 (div=0F)
E8 mod 13 = 09 (div=0F)
E9 mod 13 = 08 (div=0F)
EA mod 13 = 0B (div=0F)
EB mod 13 = 0A (div=0F)
EC mod 13 = 0D (div=0F)
ED mod 13 = 0C (div=0F)
EE mod 13 = 0F (div=0F)
EF mod 13 = 0E (div=0F)
F0 mod 13 = 02 (div=0E)
F1 mod 13 = 03 (div=0E)
F2 mod 13 = 00 (div=0E)
F3 mod 13 = 01 (div=0E)
F4 mod 13 = 06 (div=0E)
F5 mod 13 = 07 (div=0E)
F6 mod 13 = 04 (div=0E)
F7 mod 13 = 05 (div=0E)
F8 mod 13 = 0A (div=0E)
F9 mod 13 = 0B (div=0E)
FA mod 13 = 08 (div=0E)
FB mod 13 = 09 (div=0E)
FC mod 13 = 0E (div=0E)
FD mod 13 = 0F (div=0E)
FE mod 13 = 0C (div=0E)
FF mod 13 = 0D (div=0E)

 

Методика деления описана

Любая методика, которая не подтверждается проверкой умножением, некорректная.

частное * делитель + остаток = делимое, если нет - то методика неверная. Извините, но это аксиома. Точнее, определение деления.

[ViKo 1]

Любая методика, которая не подтверждается проверкой умножением, некорректная.

частное * делитель + остаток = делимое, если нет - то методика неверная. Извините, но это аксиома. Точнее, определение деления.

Мы говорим о полиномиальном делении?

[SM 0]

Мы говорим о полиномиальном делении?

Да, в GF(2). Особенностью которого является 1+1 = 0, x+x = 0, x^4+x^4 = 0, ну и т.д.

 

Потренируйтесь, для начала, с умножением полиномов. Оно проще. И нужно, чтобы результаты деления проверять.

[ViKo 1]

Да, в GF(2). Особенностью которого является 1+1 = 0, x+x = 0, x^4+x^4 = 0, ну и т.д.

Потренируйтесь, для начала, с умножением полиномов. Оно проще. И нужно, чтобы результаты деления проверять.

Я уже натренирован. Мои расчеты показаны выше. И они полностью соответствуют моим предположениям.

А вы умножаете неправильно. x^9 там, действительно, быть никак не может.

[SM 0]

А вы умножаете неправильно. x^9 там, действительно, быть никак не может.

Ну что тут поделать... Могу посоветовать лишь подучить математику... Чтобы вспомнить, что x^5 * x^4 = x^9. Даже в GF(2).

 

Повторю проверку Вашего ошибочного расчета на всякий случай, чтобы остальные, желающие разобраться в сути, поняли, еще раз.

 

Ошибочный результат:

0x30 / 0x13 = 0x35, 0x0F

 

Проверка:

1) частное, 0x35, это 0011 0101 , в полиномиальном виде x^5+x^4+x^2+1.

2) остаток, 0x0F, это 0000 1111, в полиномиальном виде x^3+x^2+x+1

3) вычисляем произведение 0x35 на порождающий полином 0x13, в полиномиальном виде x^4+x+1:

(x^5+x^4+x^2+1)*(x^4+x+1) = (x^9+x^6+x^5)+(x^8+x^5+x^4)+(x^6+x^3+x^2)+(x^4+x+1) = x^9 + x^8 + (x^6+x^6) + (x^5 + x^5) + (x^4+x^4) + x^3 + x^2 + x + 1 = x^9+x^8+x^3+x^2+x+1

умножение делается так. Каждый член первого множителя умножается на каждый член второго множителя, и все произведения суммируются. Это видно в первой операции - в каждой из скобок произведение второго множителя на каждый из членов первого. Члены с одинаковой степенью группируются (вторая операция), и если их четное количество, то они уничтожаются (коэффициент при члене=0), если нечетное, то остаются (коэффициент при члене=1). Это уже правила сложения в GF(2): 0+0=0; 1+0=1; 0+1=1; 1+1=0;

4) Прибавляем к произведению остаток от деления.

(x^9+x^8+x^3+x^2+x+1) + (x^3+x^2+x+1) = x^9 + x^8 + (x^3+x^3) + (x^2+x^2) + (x+x) + (1+1) = x^9 + x^8.

5) проверяем: x^9 + x^8 это 0011 0000 0000 = 0x300. Что, никак не соответствует исходному 0x30 аккурат на 4 порядка.

то есть, правильный результат, 0x300 / 0x13 = 0x35, 0x0F

 

 

Теперь, алгоритм деления, который реально проходит проверку умножением, то есть, после него всегда исполняется условие "частное*полином+остаток == делимое", рассчитанный на 8-битные данные:

делимое = данное;
делитель = полином

остаток = делимое;
сдвигатель = делитель << 8;
маска = 0x80 << 8;
частное = 0;
цикл ( 8 раз) {
   сдвигатель >>= 1;
   маска >>=1
   частное <<= 1;
   если (остаток >= делитель И (остаток & маска) != 0) {
     остаток ^= сдвигатель;
     частное |= 1;
  }
}

[ViKo 1]

А вы замените умножение последовательными сложениями, и вспомните, что в данной математике переносы не распространяются.

[SM 0]

А вы замените умножение последовательными сложениями, и вспомните, что в данной математике переносы не распространяются.

Это некорректно. Читайте про умножение полиномов в GF в учебнике. Ну, хотя бы, тут - http://habrahabr.ru/post/212095/

До первого примера умножения, остальное нас не интересует, так как у нас поле простое, GF(2^m) с m=1, а остальное касается m>1, когда надо приводить результат.

[ViKo 1]

http://depa.usst.edu.cn/chenjq/www2/softwa...calculation.htm