Рассмотрим полиномальную арифметику на классах вычетов:
каждый разряд отдельно в пределах поля S{n} = Zn без переноса для S{2} это {0,1} а операция XOR: (причем и для сложения и для вычитания). а для S{3} это {0,1,2} - будет сложение по модулю 3 (сложение и вычитание дают разные результаты). Например по модулю 2: X^3 + X^2 + X + 1 1111 + X^3 + 1 XOR 1001 ----------------------- ---- X^2 + X 110 X^3 + X^2 + X + 1 1111 - X^3 + 1 XOR 1001 ----------------------- ---- X^2 + X 0110 А теперь по модулю 3: X^3 + X^2 + X + 1 1111 + X^3 + 2X^2 + 1 + 1201 ------------------------- ---- 2X^3 + + X + 2 2012 X^3 + X^2 + X + 1 1111 - X^3 + 2X^2 + 1 - 1201 ------------------------- ---- 2X^2 + X 0210 Сложение
Умножение - как мы и умножали в школе полиномы (но с учетом правил сложения) A = a{i}*x^i + ... + a{1}*x^1 + a{0}*X^0 B = b{i}*x^i + ... + b{1}*x^1 + b{0}*X^0 A*B = SUM{i,j} ( a{i}b{j}*x^(i+j) ) Пример (X^2 + X + 1) * (X^2 + X + 1) = X^2 + X + 1 + X^3 + X^2 + X + X^4 + X^3 + X^2 = X^4 + (2*X^3) + (3*X^2) + 2*X +1 Если S{2} (1 mod 2)*X^4 + (2 mod 2)*X^3 + (3 mod 2)*X^2 + (2 mod 2)* X + 1 = = 1*X^4 + 0*X^3 + 1*X^2 + 0*X^2 + 1 = 1*X^4 + 1*X^2 + 1 = X^4 + X^2 + 1 111 * 111 ----- 111 + 111 111 ------ 10101 Если срубить по разрядной сетке: то X^2 + 1 (101) Если S{3} (1 mod 3)*X^4 + (2 mod 3)*X^3 + (3 mod 3)*X^2 + (2 mod 3)*X + 1 = = 1*X^4 + 2*X^3 + 0*X^2 + 2*X + 1 = X^4 + 2X^3 + 2X + 1 111 * 111 ------- 111 + 111 111 ------- 12021 Если срубить по разрядной сетке: то 2X + 1 (021) Частный пример: 2*X^2 + 1 201 * 2 * 2 ----------------- ------ X^2 + 2 102 Умножение
Остаток от деления на полином: например для S{2} есть полином X^2+1 (101) что такое арифметика по модулю этого полинома. Остаток должен иметь степень меньшую чем полином например X+1 11 так и будет 11 X^2 + X + 1 (111) будет 111 XOR 101 = 10 ---- 10 X^4 + X^3 + X (11010) 11010 101 111 101 100 101 --- 01 Теперь рассмотрим S{3}. Пусть есть полином 2X^2 + X + 2 (212) Остаток должен иметь степень меньшую чем полином например 2X + 1 (21) так и будет 21 а X^2 + X + 1 (111) будет 111 (212 * 2 = 121) -121 --- 20 = 20 X^4 + X^3 + 2*X^2 + X + 2 (11212) 11212 -121 ----- 211 -212 ----- 022 = 22 Для S{2} и S{3} - все ОК. Но попробуйте на S{4} по модулю 2X^2 + X + 3 (213) например представить X^2 + X + 1 (111) 213 * 1 = 213 213 * 2 = 022 -> от степени X^2 таким полиномом не избавимся. так что полином надо будет выбирать с коэффициентом 1 при старшей степени например X^2 + X + 3 (113) тогда X^2 + X + 1 (111) будет 02 по модулю X^2+X+3 S{4} 111 -113 --- 02 = 2 * X^0 a 3*X^2 + 2X + 3 (323) будет 323 - 331 (113 * 3 = 331) --- 32 = 3X + 2 Остаток от деления
Многочлен f(x) c коэффициентами из поля K называется НЕПРИВОДИМЫМ над K если не существует двух таких полиномов f1, f2 из К[x] степени не ниже первой таких что f = f1 * f2 ПРИМИТИВНЫЙ полином степени N - это неприводимый полином степени n, который делит X^k - 1, где k = p^n - 1 но не делит X^d - 1, для любого d, которое делит (p^n - 1) Такой полином что-то типа простого числа над полем полиномов. откуда берется примитивный полином: из малая теорема Ферма: a^(p-1) = 1 mod p X^(p^n - 1) = 1 это как раз оно для двоичных полиномов в литературе любят писать: x^k + 1, x^d + 1 на самом же деле это просто вырожденный случай - вычеты по 2 им все равно (-1 = 1), а уже начиная с троичного случая все по взрослому. А люди до конца не понимают принципов лежащих в основах. Примеры: Например возьмем степени 3 над полем вычетов по 2: -------------------- Полином Множители -------------------- -1000 = 10 * 100 -1001 = 111 * 11 -1010 = 101 * 10 1011 неприводимый -1100 = 11 * 100 -1110 = 111 * 10 -1111 = 11 * 101 -------------------- доказательство неприводимости: полином степени 3 = полином степени 3 * полином степени 0 полином степени 3 = полином степени 2 * полином степени 1 <- этот вариант полином степени 3 = полином степени 1 * полином степени 2 (см выше) полином степени 3 = полином степени 0 * полином степени 3 (см выше) полином степени 2 * полином степени 1 = --------------------- 1xx * 1xx Результат --------------------- 100 * 10 = 1000 100 * 11 = 1100 101 * 10 = 1010 101 * 11 = 1111 110 * 10 = 1100 110 * 11 = 1010 111 * 10 = 1110 111 * 11 = 1001 -------------------- все остальные полиномы очевидно - неприводимые. Рассмотрим наш неприводимый полином 1011: он делит X^[ p^n - 1 ] - 1 X^[ 2^3 - 1 ] - 1 X^[ 8 - 1] -1 X^7 - 1 X^7 + 1 10000001 X^7-1 1011 ------ 1100 1011 ----- 1110 1011 ----- 1011 ok 1011 ---- 0 (p^n - 1) = 7 - это простое число - у него нет делителей значит X^d - 1 рассматривать не надо. следовательно наш полином - 1011 - является примитивным. Некоторые Примитивные полиномы на S{2}: ------------------------------------ 1 X + 1 2 X^2 + X + 1 3 X^3 + X + 1 4 X^4 + X + 1 5 X^5 + X^2 + 1 6 X^6 + X + 1 7 X^7 + X^3 + 1 8 X^8 + X^4 + X^3 + X^2 + 1 9 X^9 + X^4 + 1 10 X^10 + X^3 + 1 11 X^11 + X^2 + 1 12 X^12 + X^6 + X^4 + X + 1 13 X^13 + X^4 + X^3 + X + 1 14 X^14 + X^10 + X^6 + X + 1 15 X^15 + X + 1 16 X^16 + X^12 + X^3 + X + 1 ------------------------------------ (в таблице представленны не все примитивные полиномы, для некоторых степеней их бывает больше 1). Неприводимые трехчлены и пятичлены ----------------------------------- n коэффициенты (кроме n и 0) ----------------------------------- 2 1 3 1 4 1 5 2 6 1 7 1 8 7,3,2 9 1 10 3 11 2 12 3 13 4,3,1 14 5 15 1 16 5,3,1 17 3 18 3 19 5,3,1 20 3 21 2 22 1 23 5 24 8,3,2 25 3 26 4,3,1 27 5,2,1 28 1 29 2 30 1 31 3 32 7,3,2 33 10 ----------------------------------- Например для 5й степени примитивные полиномы: ------------------------------------- 100101 X^5 + X^2 + 1 101111 X^5 + X^3 + X^2 + X + 1 110111 X^5 + X^4 + X^2 + X + 1 -------------------------------------- Неприводимые и примитивные полиномы.
А теперь степени 2 над полем вычетов по 3. ----------------------------- -100 = 10 * 10 101 неприводимый -102 = 21 * 22 = 11 * 12 -110 = 11 * 10 -111 = 12 * 12 112 неприводимый -120 = 12 * 10 -121 = 11 * 11 122 неприводимый = 211 * 2 -200 = 10 * 20 -201 = 21 * 11 = 22 * 12 202 неприводимый = 101 * 2 -210 = 21 * 10 211 неприводимый -212 = 22 * 11 -220 = 22 * 10 221 неприводимый -222 = 21 * 12 ----------------------------- доказательство неприводимости: полином степени 2 может получиться только как: полином степени 2 * полином степени 0 полином степени 1 * полином степени 1 -> нам нужен только этот случай полином степени 0 * полином степени 2 понятное дело нам нужны полиномы с ненулевым коэффициентом при 2 степени таким образом рассматриваем: 1x * 1x 1x * 2x 2x * 2x смотрим: 10 * 10 = 100 10 * 11 = 110 10 * 12 = 120 10 * 20 = 200 10 * 21 = 210 10 * 22 = 220 11 * 11 = 121 11 * 12 = 102 11 * 20 = 220 11 * 21 = 201 11 * 22 = 212 12 * 12 = 111 12 * 20 = 210 12 * 21 = 222 12 * 22 = 201 20 * 20 = 100 20 * 21 = 120 20 * 22 = 110 21 * 21 = 201 21 * 22 = 102 22 * 22 = 121 все остальные полиномы очевидно неприводимые (смотри таблицу выше). Теперь выберем примитивные полиномы из неприводимых: неприводимые полиномы: -------------------- 101 112 122 202 221 211 --------------------- неприводимый полином должен делить: X^[ p^n - 1] - 1 X^[ 3^2 - 1] - 1 X^[ 9 - 1] - 1 X^8 - 1 X^8 + 2 100000002 но не должен делить X^d - 1, где d делит (p^N - 1) = 8 8 делят 4 и 2. (2) X^2 - 1 имеет степень меньше 3 и его никто естественно не делит 101 (4) X^4 - 1 X^4 + 2 10002 Рассмотрим наши полиномы: [101] 100000002 101 ----- 200 202 ----- 100 101 ----- 202 202 --- 0 10002 101 ----- 202 делит - поэтому не примитивный 202 --- 0 [112] 100000002 112 ---- 210 221 --- 220 221 ----- 200 221 --- 120 112 ---- 112 112 --- 0 10002 112 ---- 210 221 --- 222 не делит - поэтому примитивный 221 --- 1 [122] 100000002 122 ---- 110 122 ---- 210 211 ----- 200 211 ---- 220 211 --- 122 122 --- 0 10002 122 --- 110 122 --- 212 211 --- не делит - значит примитивный 1 И Соответсвенно для сопряженных: (просто у нас троичный случай (в принципе он тоже вырожденный) и {2*P = -P}): 202 = 2 * 101 - непримитивный 211 = 2 * 122 - примитивный 221 = 2 * 112 - примитивный Поиск примитивных полиномов - такое же долгое занятие как и поиск простых чисел. А учитывая важность таких полиномов для криптографии - понятно почему не публикуют такие полиномы высоких степеней.