В криптографии мы часто должны использовать четыре операции (сложение, вычитание, умножение и деление). Другими словами, мы должны использовать поля. Однако когда мы работаем с компьютерами, положительные целые числа сохраняются в компьютере как n -битовые слова, в которых n является обычно 8, 16, 32, 64, и так далее. Это означает, что диапазон целых чисел — 0 до 2n – 1. Модуль — 2n. Так что возможны два варианта, если мы хотим использовать поле.
1. Мы можем задействовать GF(p) с множеством Zp, где p — наибольшее простое число, меньшее, чем 2n. Но эта схема неэффективна, потому что мы не можем использовать целые числа от p до 2n- 1. Например, если n = 4, то наибольшее простое число, меньшее, чем 24, — это 13. Это означает, что мы не можем использовать целые числа 13, 14 и 15. Если n = 8, наибольшее простое число, меньшее, чем 28, — это 251, так что мы не можем использовать 251, 252, 253, 254 и 255.
2. Мы можем работать в GF(2n) и использовать множество 2n элементов. Элементы в этом множестве — n -битовые слова. Например, если n = 3, множество равно:
{000,001,010,011, 100,101,110,111}
Однако мы не можем интерпретировать каждый элемент как целое число от 0 до 7, потому что не могут быть применены обычные четыре операции (модуль 2n — не простое число). Мы должны определить множество слов по 2 бита и две новых операции, которые удовлетворяют свойствам, определенным для поля.
Пример 6.1
Определим GF(22) поле, в котором множество имеет четыре слова по 2 бита: {00, 01, 10, 11}. Мы можем переопределить сложение и умножение для этого поля таким образом, чтобы все свойства этих операций были удовлетворены, как это показано на рис. 6.1.
(рис 6.1) Пример поля GF(2 в степени 2)Каждое слово — аддитивная 00 ) имеет мультипликативную 01,01 ) и ( 10, 11 ). Сложение и умножение определено в терминах полиномиалов.
Хотя мы можем непосредственно определить правила для операций сложения и умножения слов из двух бит, которые удовлетворяют свойства в GF(2n), проще работать с полиномиальным степени n – 1 побитным представлением слов. Полиномиальное выражение степени n – 1 имеет форму
f(x) = an-1xn-1 + an-2xn-2 + …… + a1x1 + a0x0
где xi назван термином " i -тый элемент", а ai называется коэффициентом i - того элемента. Хотя мы знаем полиномы в алгебре, но при представлении n -битовых слов полиномами необходимо следовать некоторым правилам:
а. степень x определяет позицию бита в n -битовых слов. Это означает, что крайний левый бит находится в нулевой позиции (связан с x0 ), самый правый бит находится в позиции n–l (связан с xn-l );
b. коэффициенты сомножителей определяют значение битов. Каждый бит принимает только значение 0 или 1, поэтому наши полиномиальные коэффициенты могут иметь значение 0 или 1.
Пример 6.2
Использование полиномов для предоставления слова из 8 бит (10011001) показано на рис. 6.2.
(рис 6.2) Представление 8-ми битового слова полиномом Заметим, что элемент полностью пропущен, если его коэффициент равен 0, и пропущен только коэффициент, если это 1. Также заметим, что элемент x0 равен 1.
Пример 6.3
Чтобы найти слово на 8 битов, связанное с полиномом X5+ X2 + X, мы сначала восстановим пропущенные сомножители. Мы имеем n = 8, это означает 7. Расширенный
0X7 + 0X6 + 1X5 + 0X4 + 0X3 + 1X2 + 1X1 + 0X0
Он связан со словом на 8 битов 00100110.
Обратите внимание, что любая операция на полиномах фактически включает две операции: операции И коэффициентов двух полиномов. Другими словами, мы должны определить два поля: одно для коэффициентов и одно для полиномов. Коэффициенты равны 0 или 1 ; для этой цели мы можем использовать GF(2) -поле. Мы уже говорили о таком поле (см. пример 6.1). Для полиномов нам нужно поле GF(2n), которое мы коротко обсудим ниже.
Перед определением операций на полиномах мы должны поговорить о полиномах-модулях. Сложение двух полиномов никогда не создает n – 1. Это означает, что мы должны делить результат на модуль и сохранять только остаток, как мы сделали в модульной арифметике. Для множеств полиномов в GF(2n) группа полиномов степени n определена как модуль. Модуль в этом случае действует как полиномиальное простое число. Это означает, что никакие полиномы множества не могут делить этот n. Такие полиномы называются неприводимые полиномы. Таблица 6.1 показывает примеры полиномов 1-5 степеней.
Для каждого значения степени часто есть более чем один неразлагаемый GF(2n), мы должны объявить, какой неприводимый
| Степень | Неприводимый |
|---|---|
| 1 | (x+1)x |
| 2 | (x2+x+1) |
| 3 | (x3+x2+1)(x3+x+1) |
| 4 | (x4+x3+x2+x+1)(x4+x3+1)(x4+x+1) |
| 5 | (x5+x2+1)(x5+x3+x2+x+1)(x5+x4+x3+x+1)(x5+x4+x3+x2+1)(x5+x4+x2+x+1) |
Теперь определим операцию сложения для полиномов с коэффициентом в GF(2). Операция сложения очень простая: мы складываем коэффициенты соответствующих элементов полинома в поле GF(2). Обратите внимание, что сложение двух полиномов степени n – 1 всегда дает n – 1 — это означает, что мы не должны использовать вычитание из модуля их результата.
Пример 6.4
Произведем сложение $$({x^5} + {x^2} + x) \oplus ({x^3} + {x^2} + 1)$$ в GF(28). Мы используем символ $$\oplus$$ для обозначения полиномиального сложения. Ниже показана процедура
В упрощенном полиноме (показан справа) сохранены элементы с коэффициентом 1 и удалены элементы с коэффициентом 0. Кроме того, удалены совпадающие элементы обоих полиномов, а несовпадающие сохраняются. Другими словами, x5, x3, и x1 сохраняются, а x2, который является совпадающим в этих двух полиномах, удален.
Пример 6.5
Поскольку сложение в GF(2) означает операцию x5 + x2 + x есть 00100110, или x3 + x2 + 1 есть 00001101. Результат — 00101011 или, в полиномиальном обозначении, x5 + x3 + x + 1.
Аддитивный нейтральный элемент — тождество. Аддитивный нейтральный элемент полинома — нулевой
Аддитивная инверсия полинома с коэффициентами в GF(2) — сам
Сложение и операции вычитания на полиномах — та же самая операция.
Умножение в полиномах — сумма умножения каждого элемента одного полинома с каждым элементом второго полинома. Однако необходимо отметить три особенности.
Первая: умножение коэффициента проводится в поле GF(2).
Вторая: умножение xi на xj дает результат xi+j.
Третья: умножение может создать элементы со степенью большей, чем n–1, и это означает, что результат должен быть уменьшен с использованием полинома-модуля.
Сначала покажем, как умножить два полинома согласно вышеупомянутому определению. Позже будет дан более эффективный алгоритм, который может использоваться компьютерной программой.
Пример 6.6
Найдите результат $$(x^{5} + x^{2} + x)\otimes (x^{7} + x^{4}+ x^{3} + x^{2} +x)$$ в GF(28) с неразлагаемым полиномом (x8 + x4 + x3 + x + 1). Обратите внимание, что для обозначения умножения двух полиномов используется символ $$\otimes$$.
Решение
Сначала умножаем эти два полинома так, как мы это делали в обычной алгебре. Обратите внимание, что в этом процессе пара элементов с равной степенью удаляется. Например, результат x9 + x9 полностью удален, потому что он нулевой
Чтобы найти конечный результат, разделим 12 на 8 (модуль) и сохраним только остаток. Процесс деления тот же самый, что и в обычной алгебре, но мы должны помнить, что здесь вычитание то же самое, что и сложение. Рисунок 6.3 показывает процесс деления.
(рис 6.3) Полиномиальное деление с коэффициентами в поле GF (2).Мультипликативное тождество — всегда равно 1. Например, в GF(28) мультипликативная 00000001.
Мультипликативная инверсия. Поиск мультипликативной
Пример 6.7
В GF(24) найдите (x2 + 1) mod (x4 + x + 1).
Решение
Мы используем расширенный евклидов алгоритм, как это показано в таблице 6.2:
| q | rj | r2 | r | tj | t2 | t |
|---|---|---|---|---|---|---|
| x2+1 | (x4+x+1) | (x2+1) | (x) | (0) | (1) | (x2+1) |
| (x) | (x2+1) | (x) | (1) | (1) | (x2+1) | (x3+x+1) |
| (x) | (x) | (1) | (0) | (x2+1) | (x3+x+1) | (0) |
| (1) | (0) | (x3+x+1) | (0) |
Это означает, что (x2 + 1) -1 mod (x4 + x + 1) есть (x3 + x + 1). Ответ может быть проверен просто: надо перемножить эти два полинома и найти остаток. В этом случае результат деления на модуль равен
Пример 6.8
В GF(28) найдите (x5) mod (x8 + x4 + x3 + x + 1).
Решение
Будем использовать расширенный евклидов алгоритм, как это показано в Таблице 6.3:
| q | rj | r2 | r | tj | t2 | t |
|---|---|---|---|---|---|---|
| (x3) | (x8+x4+x3+x+1) | (x5) | (x4+x3+x2+x+1) | (0) | (1) | (x3) |
| (x+1) | (x5) | (x4+x3+x+1) | (x3+x2+1) | (1) | (x3) | (x4+x3+1) |
| (x) | (x4+x3+x+1) | (x3+x2+1) | (1) | (x3) | (x4+x3+1) | (x5+x4+x2+x) |
| (x3+x2+1) | (1) | (0) | (x4+x3+1) | (x5+x4+x2+x) | (0) | |
| (1) | (0) | (x5+x4+x2+x) | (0) |
Это означает, что (x5)-1 mod (x8 + x4 + x3 + x + 1) есть (x5 + x4 + x2 + x).
Результат может быть легко проверен умножением этих двух полиномов и определением остатка деления по модулю.
$$[(x^{5}) \otimes (x^{5}+x^{4}+x^{3}+x)] \mod (x^{8}+x^{4}+x^{3}+x+1) =$$Операция деления порождает проблему написания эффективной программы умножения двух полиномов. Лучший алгоритм для компьютерной реализации использует неоднократное умножение уменьшенного полинома на x. Например, вместо того чтобы находить результат $$({x^2} \otimes {P_2})$$, программа находит результат $$(x \otimes (x \otimes {P_2}))$$. Преимущества этой стратегии будет обсуждаться далее, но сначала рассмотрим пример, чтобы проиллюстрировать алгоритм.
Пример 6.9
Найдите результат умножения P1 = (x5 + x2 + x) на P2 = (x7 + x4 + x3 + x2 + x) в поле GF(28) с неприводимым полиномом (x8 + x4 + x3 + x + 1), используя алгоритм, изложенный выше.
Решение
Процесс показан в таблице 6.4. Мы сначала находим промежуточный результат умножения x0, x1, x2, x3, x4 и x5. Заметим, что необходимы только три составляющие произведения $${x^m} \otimes {P_2}$$ для m от 0 до 5, каждое вычисление зависит от предыдущего результата.
| Степень | Операция | Новый результат | Вычитание |
|---|---|---|---|
| x0 $$\otimes$$ P2 | x7+x4+x3+x2+x | НЕТ | |
| x1 $$\otimes$$ P2 | x $$\otimes$$ (x7+x4+x3+x2+x) | x5+x2+x+1 | ДА |
| x2 $$\otimes$$ P2 | x $$\otimes$$ (x5+x2+x+1) | x6+x3+x2+x | НЕТ |
| x3 $$\otimes$$ P2 | x $$\otimes$$ (x6+x3+x2+x) | x7+x4+x3+x2 | НЕТ |
| x4 $$\otimes$$ P2 | x $$\otimes$$ (x7+x4+x3+x2) | x5+x+1 | ДА |
| x5 $$\otimes$$ P2 | x $$\otimes$$ (x5+x+1) | x6+x2+x | НЕТ |
| P1 x P2 = (x6+x2+x)+(x6+x3+x2+x)+(x5+x2+x+1) = x5+x3+x2+x+1 | |||
Рассмотренный выше алгоритм имеет два преимущества. Первое — умножение полинома на x может быть выполнено простым сдвигом одного бита в n -битовом слове; операция может быть реализована на любом языке программирования. Второе — результат может быть использован, если максимальная степень полинома n–1. В этом случае сокращение может быть сделано просто с помощью применения операции 8. Мы можем разработать простой алгоритм для нахождения промежуточных результатов.
0, тогда надо сдвинуть предыдущий результат на один бит влево.1:
а. надо сдвинуть на один бит влево, и
б. применить к нему операцию Повторим пример 6.9 для двоичной последовательности размером 8 бит.
Пусть P1 = 00100110, P2 = 10011110, модуль = 100011010 (девять битов). Обозначим операцию
| Степень | ||
|---|---|---|
| x0 $$\otimes$$ P2 | 10011110 | |
| x1 $$\otimes$$ P2 | 00111100 | (00111100) $$\oplus$$ (00011010) = 00100111 |
| x2 $$\otimes$$ P2 | 01001110 | 01001110 |
| x3 $$\otimes$$ P2 | 10011100 | 10011100 |
| x4 $$\otimes$$ P2 | 00111000 | (00111000) $$\oplus$$ (00011010) = 00100011 |
| x5 $$\otimes$$ P2 | 01000110 | 01000110 |
| P1 $$\otimes$$ P2 = (000100110) $$\oplus$$ (01001110) $$\oplus$$ (01000110) = 00101111 | ||
В этом случае для умножения этих двух полиномов нам надо только пять операций левого сдвига и четыре n-1 необходимо максимально (n–1) операций левого сдвига и 2n операций
Пример 6.10
Поле GF(23) состоит из 8 элементов. Покажем умножение и сложение таблиц для этого поля, используя неприводимый x3+x2+1. Мы будем оперировать с трехбитовым словом и полиномом. Заметим, что имеется два полинома третьей степени (см. таблицу 6.1). Другой (x3 + x + 1) для умножения имеет таблицу, полностью отличающуюся от первой. Таблица 6.6 показывает сложение. Затемненные клетки (нулевые) дают обратные пары для сложения.
Таблица 6.7 показывает умножение. Затемненные клетки (единичные) дают обратные пары при умножении.
Иногда проще определить элементы поля GF(2n), используя генератор. В этом поле с неприводимым полиномом f(x) и элементом поля a нужно удовлетворить отношение f(а) = 0. В частности, если g — генератор поля, то f(g)=0. Тогда можно доказать, что элементы поля могут быть сгенерированы как
{0, g,g, g2,.... gn}, где N = 2n – 2
| $$\oplus$$ | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
|---|---|---|---|---|---|---|---|---|
| 000 (0) | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
| 001 (1) | 001 (1) | 000 (0) | 011 (x+1) | 010 (x2) | 101 (x2+1) | 100 (x2+x) | 111 (x2+x+1) | 110 (x2 + x) |
| 010 (x) | 010 (x) | 011 (x+1) | 000 (0) | 001 (1) | 110 (x2 + x) | 111 (x2+x+1) | 100 (x2+x) | 101 (x2+1) |
| 011 (x+1) | 011 (x+1) | 010 (x) | 001 (1) | 000 (0) | 111 (x2+x+1) | 110 (x2 + x) | 101 (x2+1) | 100 (x2) |
| 100 (x2) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) |
| 101 (x2+1) | 101 (x2+1) | 100 (x2) | 111 (x2+x+1) | 110 (x2 + x) | 001 (1) | 000 (0) | 011 (x+1) | 010 (x) |
| 110 (x2 + x) | 110 (x2 + x) | 111 (x2+x+1) | 100 (x2) | 101 (x2+1) | 010 (x) | 011 (x+1) | 000 (0) | 001 (1) |
| 111 (x2+x+1) | 111 (x2+x+1) | 110 (x2 + x) | 101 (x2+1) | 100 (x2) | 011 (x+1) | 010 (x) | 001 (1) | 000 (0) |
| $$\oplus$$ | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
|---|---|---|---|---|---|---|---|---|
| 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) |
| 001 (1) | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
| 010 (x) | 000 (0) | 010 (x) | 100 (x) | 110 (x2 + x) | 101 (x2+1) | 111 (x2+x+1) | 001 (1) | 011 (x+1) |
| 011 (x+1) | 000 (0) | 011 (x+1) | 110 (x2 + x) | 101 (x2+1) | 001 (1) | 010 (x) | 111 (x2+x+1) | 100 (x2) |
| 100 (x2) | 000 (0) | 100 (x2) | 101 (x2+1) | 001 (1) | 111 (x2+x+1) | 011 (x+1) | 010 (x) | 110 (x2 + x) |
| 101 (x2+1) | 000 (0) | 101 (x2+1) | 111 (x2+x+1) | 010 (x) | 011 (x+1) | 110 (x2 + x) | 100 (x2) | 001 (1) |
| 110 (x2 + x) | 000 (0) | 110 (x2 + x) | 001 (1) | 111 (x2+x+1) | 010 (x) | 100 (x2) | 011 (x+1) | 101 (x2+1) |
| 111 (x2+x+1) | 000 (0) | 111 (x2+x+1) | 011 (x+1) | 100 (x2) | 110 (x2 + x) | 001 (1) | 101 (x2+1) | 010 (x) |
Пример 6.11
Для генерирования элементов поля GF(24) используйте f(x) = x4 + x +1.
Решение
Элементы 0, g0, g 1, g2 и g3 могут быть сгенерированы достаточно просто, потому что в 4 -0, x0, x 1, x2 и x3 (не требуется деления на g4 до g14, которые представляют g4 до g14 от x4 до x14, нужно разделить на неприводимый f(g) = g4 + g +1 = 0. Применив это отношение, мы имеем g4 = –g–1. поскольку сложение полей и вычитание полей — та же самая операция, g4 = g + 1. Мы используем это отношение, чтобы найти значение всех элементов в виде 4 -битовых слов:
0 = 0 = 0 = 0 -> 0=(0000) g0 = g1 = g1 -> g1 = (0010) g2 = g2 = g2 -> g2 = (0100) g3 = g3 = g3 -> g3 = (1000) g4 = g4 = g + 1 -> g4 = (0011) g5 = g(g + 1) = g2 + g -> g5 = (0110) g6 = g(g2 + g) = g3 + g2 -> g6 = (1100) g7 = g(g3 + g) = g3 + g + 1 -> g7 = (1011) g8 = g(g3 + g + 1) = g2 + 1 -> g8= (0101) g9 = g(g2 + 1) = g3 + g -> g9 = (1010) g10 = g(g3 + g) = g2 + g + 1 -> g10 = (0111) g11 = g(g2 + g + 1) = g3 + g2 + g -> g11 = (1110) g12 = g(g3 + g2 + g) = g3 + g2 + g + 1 -> g12 = (1111) g13 = g(g3 + g2 + g + 1) = g3 + g2 + 1 -> g13 = (1101) g14 = g(g3 + g2 + 1) = g3 + 1 -> g14 = (1001)
Главная идея состоит в том, что вычисление элементов поля от g4 до g14 сводится к использованию соотношения g4 = g +1 и предыдущих вычислений. Например,
g12 = g(g11) =g(g3 + g2 + g) = g4 + g3 + g2 = g3 + g2 + g + 1
После сокращения можно просто преобразовать степени в n -битовое слово. Скажем, g3 + 1 эквивалентно 1001, потому что присутствуют элементы со степенью 0 и 3. Заметим, что элементы с одинаковой степенью при таком процессе вычисления отменяют друг друга. Например, g2 + g2 = 0.
Нахождение
Аддитивная g3 = g3.
Найти мультипликативную g3, как показано ниже:
Заметим, что в этом случае степень рассчитывается по модулю 2n – 1,
24 – 1 = 15.
Поэтому –3 mod 15 = 12 mod 15.
Можно легко доказать, что g3 и g12 есть инверсные (обратные числа), потому что g3 g12 = g15 = g0 = 1.
Сложение и вычитание — это одинаковые операции. Промежуточные результаты могут быть упрощены, как проиллюстрировано в следующем примере.
Пример 6.12
Этот пример показывает результаты операций сложения и вычитания:
a. $$\left( {{g^3} + {g^{12}} + {g^7}} \right) = {g^3} + \left( {{g^3} + {g^2} + g + 1} \right) + \left( {{g^3} + g + 1} \right) = {g^3} + {g^2} \to \left( {{\text{11}}00} \right)$$
b. $${g^3}-{g^6} = {g^3} + {g^6} = {g^3} + ({g^3} + {g^2}) = {g^2} \to \left( {0{\text{1}}00} \right)$$
Умножение есть сложение степени по модулю 2n – 1. Деление — это умножение, которое использует мультипликативную
Пример 6.13
Ниже показаны операции умножения и деления:
а. $${g^9} \times {g^{11}} = {g^{20}} = {g^{20\bmod 15}} = {g^5} = {g^2} + g \to \left( {0110} \right)$$
б. $${g^3}/{g^8} = {g^3} \times {g^7} = {g^{10}} = {g^2} + g + 1 \to \left( {0111} \right)$$
Конечное поле GP (2n) может использоваться для того, чтобы определить четыре операции — сложение, вычитание, умножение и деление n -битных слов. Только деление на нуль не определено. Каждое n -битовое слово может быть представлено как n – 1 с коэффициентами в GF(2), — это означает, что операции на n -битовых словах могут быть представлены как операции на этом полиноме. При умножении двух полиномов необходимо сделать эти операции операциями по модулю. Для этого мы должны определить неприводимый n. Чтобы найти мультипликативные
Нижеследующие книги и сайты обеспечивают более детальное рассмотрение понятий, обсужденных в этой лекции.
[Dur05], [Ros06J], [Bla03], [BW00] и [DF04] основательно рассматривают алгебраические структуры.
Нижеследующие сайты дают больше информации о темах, обсуждаемых в этой лекции.
H группы G — G, если само H является группой с соответствующими операциями на G. Если G и H соответственно |G| и |H|, тогда |H| делит |G|.a в группе — наименьшее положительное целое число n, такое, что an = e (единичному элементу).pn, где p — простое число, а n — положительное целое число. GF(pn) поля используется в операциях на n-битовых словах в криптографии.n -битовые слова, используются полиномы с коэффициентами в GF(2). Сложение и умножение n -битовых слов могут быть определены как сложение и умножение полиномов.
Иногда проще определить элементы GF(2n) -поля, используя генератор. Если g — генератор поля, то f(g) = 0. Нахождение G = <Z4, +>:3 + 2 и 3–2 в этой группе.[1 3 2], [3 2 1] и [2 1 3]. Покажите, как Боб может использовать только одну перестановку, чтобы изменить процесс на противоположный. Пользуйтесь таблицей 5.2.f(x) = x4 + x3 +1.f(x) = x4 + x3 +1.f(x) = x4 + x3 +1.GF(12)GF(13)GF(16)GF(17)n -битовых слов найдите полиномы, которые представляют эти слова.100101010000100011n -битовое слово, которое представлено каждым из следующих полиномов:x2 + 1 в GF(24)x2 + 1 в GF(25)x + 1 в GF(23)x7 в GF(28)GF(7) найдите результат следующих операций:5+35–4(x) и (x + 1) — неприводимые полиномы степени 1.(x2 + x + 1) — неприводимый 2.(x3 + x2 + 1) — неприводимый 3.2 -битовые слова, используя полиномы:(11) x (10)(1010) x (1000)(11100) x (10000)GF(22). (Заметим, что для этого поля есть только один модуль.)1xx + 1(x4 + x3 + 1) в GF(25), применяя модуль (x5 + x2 + 1).GF(24), используя (x4 + x3 + 1) как модуль.(x3 + x2 + x + 1) (x2 + 1) в GF(24), используя алгоритм, приведенный в таблице 6.5, и пользуясь (x4 + x3 + 1) как модулем.(10101) на (10000) в GF(25), используя алгоритм, приведенный в таблице 6.5, и пользуясь (x5 + x2 + 1) как модулем.В криптографии мы часто должны использовать четыре операции (сложение, вычитание, умножение и деление). Другими словами, мы должны использовать поля. Однако когда мы работаем с компьютерами, положительные целые числа сохраняются в компьютере как n -битовые слова, в которых n является обычно 8, 16, 32, 64, и так далее. Это означает, что диапазон целых чисел — 0 до 2n – 1. Модуль — 2n. Так что возможны два варианта, если мы хотим использовать поле.
1. Мы можем задействовать GF(p) с множеством Zp, где p — наибольшее простое число, меньшее, чем 2n. Но эта схема неэффективна, потому что мы не можем использовать целые числа от p до 2n- 1. Например, если n = 4, то наибольшее простое число, меньшее, чем 24, — это 13. Это означает, что мы не можем использовать целые числа 13, 14 и 15. Если n = 8, наибольшее простое число, меньшее, чем 28, — это 251, так что мы не можем использовать 251, 252, 253, 254 и 255.
2. Мы можем работать в GF(2n) и использовать множество 2n элементов. Элементы в этом множестве — n -битовые слова. Например, если n = 3, множество равно:
{000,001,010,011, 100,101,110,111}
Однако мы не можем интерпретировать каждый элемент как целое число от 0 до 7, потому что не могут быть применены обычные четыре операции (модуль 2n — не простое число). Мы должны определить множество слов по 2 бита и две новых операции, которые удовлетворяют свойствам, определенным для поля.
Пример 6.1
Определим GF(22) поле, в котором множество имеет четыре слова по 2 бита: {00, 01, 10, 11}. Мы можем переопределить сложение и умножение для этого поля таким образом, чтобы все свойства этих операций были удовлетворены, как это показано на рис. 6.1.
(рис 6.1) Пример поля GF(2 в степени 2)Каждое слово — аддитивная 00 ) имеет мультипликативную 01,01 ) и ( 10, 11 ). Сложение и умножение определено в терминах полиномиалов.
Хотя мы можем непосредственно определить правила для операций сложения и умножения слов из двух бит, которые удовлетворяют свойства в GF(2n), проще работать с полиномиальным степени n – 1 побитным представлением слов. Полиномиальное выражение степени n – 1 имеет форму
f(x) = an-1xn-1 + an-2xn-2 + …… + a1x1 + a0x0
где xi назван термином " i -тый элемент", а ai называется коэффициентом i - того элемента. Хотя мы знаем полиномы в алгебре, но при представлении n -битовых слов полиномами необходимо следовать некоторым правилам:
а. степень x определяет позицию бита в n -битовых слов. Это означает, что крайний левый бит находится в нулевой позиции (связан с x0 ), самый правый бит находится в позиции n–l (связан с xn-l );
b. коэффициенты сомножителей определяют значение битов. Каждый бит принимает только значение 0 или 1, поэтому наши полиномиальные коэффициенты могут иметь значение 0 или 1.
Пример 6.2
Использование полиномов для предоставления слова из 8 бит (10011001) показано на рис. 6.2.
(рис 6.2) Представление 8-ми битового слова полиномом Заметим, что элемент полностью пропущен, если его коэффициент равен 0, и пропущен только коэффициент, если это 1. Также заметим, что элемент x0 равен 1.
Пример 6.3
Чтобы найти слово на 8 битов, связанное с полиномом X5+ X2 + X, мы сначала восстановим пропущенные сомножители. Мы имеем n = 8, это означает 7. Расширенный
0X7 + 0X6 + 1X5 + 0X4 + 0X3 + 1X2 + 1X1 + 0X0
Он связан со словом на 8 битов 00100110.
Обратите внимание, что любая операция на полиномах фактически включает две операции: операции И коэффициентов двух полиномов. Другими словами, мы должны определить два поля: одно для коэффициентов и одно для полиномов. Коэффициенты равны 0 или 1 ; для этой цели мы можем использовать GF(2) -поле. Мы уже говорили о таком поле (см. пример 6.1). Для полиномов нам нужно поле GF(2n), которое мы коротко обсудим ниже.
Перед определением операций на полиномах мы должны поговорить о полиномах-модулях. Сложение двух полиномов никогда не создает n – 1. Это означает, что мы должны делить результат на модуль и сохранять только остаток, как мы сделали в модульной арифметике. Для множеств полиномов в GF(2n) группа полиномов степени n определена как модуль. Модуль в этом случае действует как полиномиальное простое число. Это означает, что никакие полиномы множества не могут делить этот n. Такие полиномы называются неприводимые полиномы. Таблица 6.1 показывает примеры полиномов 1-5 степеней.
Для каждого значения степени часто есть более чем один неразлагаемый GF(2n), мы должны объявить, какой неприводимый
| Степень | Неприводимый |
|---|---|
| 1 | (x+1)x |
| 2 | (x2+x+1) |
| 3 | (x3+x2+1)(x3+x+1) |
| 4 | (x4+x3+x2+x+1)(x4+x3+1)(x4+x+1) |
| 5 | (x5+x2+1)(x5+x3+x2+x+1)(x5+x4+x3+x+1)(x5+x4+x3+x2+1)(x5+x4+x2+x+1) |
Теперь определим операцию сложения для полиномов с коэффициентом в GF(2). Операция сложения очень простая: мы складываем коэффициенты соответствующих элементов полинома в поле GF(2). Обратите внимание, что сложение двух полиномов степени n – 1 всегда дает n – 1 — это означает, что мы не должны использовать вычитание из модуля их результата.
Пример 6.4
Произведем сложение $$({x^5} + {x^2} + x) \oplus ({x^3} + {x^2} + 1)$$ в GF(28). Мы используем символ $$\oplus$$ для обозначения полиномиального сложения. Ниже показана процедура
В упрощенном полиноме (показан справа) сохранены элементы с коэффициентом 1 и удалены элементы с коэффициентом 0. Кроме того, удалены совпадающие элементы обоих полиномов, а несовпадающие сохраняются. Другими словами, x5, x3, и x1 сохраняются, а x2, который является совпадающим в этих двух полиномах, удален.
Пример 6.5
Поскольку сложение в GF(2) означает операцию x5 + x2 + x есть 00100110, или x3 + x2 + 1 есть 00001101. Результат — 00101011 или, в полиномиальном обозначении, x5 + x3 + x + 1.
Аддитивный нейтральный элемент — тождество. Аддитивный нейтральный элемент полинома — нулевой
Аддитивная инверсия полинома с коэффициентами в GF(2) — сам
Сложение и операции вычитания на полиномах — та же самая операция.
Умножение в полиномах — сумма умножения каждого элемента одного полинома с каждым элементом второго полинома. Однако необходимо отметить три особенности.
Первая: умножение коэффициента проводится в поле GF(2).
Вторая: умножение xi на xj дает результат xi+j.
Третья: умножение может создать элементы со степенью большей, чем n–1, и это означает, что результат должен быть уменьшен с использованием полинома-модуля.
Сначала покажем, как умножить два полинома согласно вышеупомянутому определению. Позже будет дан более эффективный алгоритм, который может использоваться компьютерной программой.
Пример 6.6
Найдите результат $$(x^{5} + x^{2} + x)\otimes (x^{7} + x^{4}+ x^{3} + x^{2} +x)$$ в GF(28) с неразлагаемым полиномом (x8 + x4 + x3 + x + 1). Обратите внимание, что для обозначения умножения двух полиномов используется символ $$\otimes$$.
Решение
Сначала умножаем эти два полинома так, как мы это делали в обычной алгебре. Обратите внимание, что в этом процессе пара элементов с равной степенью удаляется. Например, результат x9 + x9 полностью удален, потому что он нулевой
Чтобы найти конечный результат, разделим 12 на 8 (модуль) и сохраним только остаток. Процесс деления тот же самый, что и в обычной алгебре, но мы должны помнить, что здесь вычитание то же самое, что и сложение. Рисунок 6.3 показывает процесс деления.
(рис 6.3) Полиномиальное деление с коэффициентами в поле GF (2).Мультипликативное тождество — всегда равно 1. Например, в GF(28) мультипликативная 00000001.
Мультипликативная инверсия. Поиск мультипликативной
Пример 6.7
В GF(24) найдите (x2 + 1) mod (x4 + x + 1).
Решение
Мы используем расширенный евклидов алгоритм, как это показано в таблице 6.2:
| q | rj | r2 | r | tj | t2 | t |
|---|---|---|---|---|---|---|
| x2+1 | (x4+x+1) | (x2+1) | (x) | (0) | (1) | (x2+1) |
| (x) | (x2+1) | (x) | (1) | (1) | (x2+1) | (x3+x+1) |
| (x) | (x) | (1) | (0) | (x2+1) | (x3+x+1) | (0) |
| (1) | (0) | (x3+x+1) | (0) |
Это означает, что (x2 + 1) -1 mod (x4 + x + 1) есть (x3 + x + 1). Ответ может быть проверен просто: надо перемножить эти два полинома и найти остаток. В этом случае результат деления на модуль равен
Пример 6.8
В GF(28) найдите (x5) mod (x8 + x4 + x3 + x + 1).
Решение
Будем использовать расширенный евклидов алгоритм, как это показано в Таблице 6.3:
| q | rj | r2 | r | tj | t2 | t |
|---|---|---|---|---|---|---|
| (x3) | (x8+x4+x3+x+1) | (x5) | (x4+x3+x2+x+1) | (0) | (1) | (x3) |
| (x+1) | (x5) | (x4+x3+x+1) | (x3+x2+1) | (1) | (x3) | (x4+x3+1) |
| (x) | (x4+x3+x+1) | (x3+x2+1) | (1) | (x3) | (x4+x3+1) | (x5+x4+x2+x) |
| (x3+x2+1) | (1) | (0) | (x4+x3+1) | (x5+x4+x2+x) | (0) | |
| (1) | (0) | (x5+x4+x2+x) | (0) |
Это означает, что (x5)-1 mod (x8 + x4 + x3 + x + 1) есть (x5 + x4 + x2 + x).
Результат может быть легко проверен умножением этих двух полиномов и определением остатка деления по модулю.
$$[(x^{5}) \otimes (x^{5}+x^{4}+x^{3}+x)] \mod (x^{8}+x^{4}+x^{3}+x+1) =$$Операция деления порождает проблему написания эффективной программы умножения двух полиномов. Лучший алгоритм для компьютерной реализации использует неоднократное умножение уменьшенного полинома на x. Например, вместо того чтобы находить результат $$({x^2} \otimes {P_2})$$, программа находит результат $$(x \otimes (x \otimes {P_2}))$$. Преимущества этой стратегии будет обсуждаться далее, но сначала рассмотрим пример, чтобы проиллюстрировать алгоритм.
Пример 6.9
Найдите результат умножения P1 = (x5 + x2 + x) на P2 = (x7 + x4 + x3 + x2 + x) в поле GF(28) с неприводимым полиномом (x8 + x4 + x3 + x + 1), используя алгоритм, изложенный выше.
Решение
Процесс показан в таблице 6.4. Мы сначала находим промежуточный результат умножения x0, x1, x2, x3, x4 и x5. Заметим, что необходимы только три составляющие произведения $${x^m} \otimes {P_2}$$ для m от 0 до 5, каждое вычисление зависит от предыдущего результата.
| Степень | Операция | Новый результат | Вычитание |
|---|---|---|---|
| x0 $$\otimes$$ P2 | x7+x4+x3+x2+x | НЕТ | |
| x1 $$\otimes$$ P2 | x $$\otimes$$ (x7+x4+x3+x2+x) | x5+x2+x+1 | ДА |
| x2 $$\otimes$$ P2 | x $$\otimes$$ (x5+x2+x+1) | x6+x3+x2+x | НЕТ |
| x3 $$\otimes$$ P2 | x $$\otimes$$ (x6+x3+x2+x) | x7+x4+x3+x2 | НЕТ |
| x4 $$\otimes$$ P2 | x $$\otimes$$ (x7+x4+x3+x2) | x5+x+1 | ДА |
| x5 $$\otimes$$ P2 | x $$\otimes$$ (x5+x+1) | x6+x2+x | НЕТ |
| P1 x P2 = (x6+x2+x)+(x6+x3+x2+x)+(x5+x2+x+1) = x5+x3+x2+x+1 | |||
Рассмотренный выше алгоритм имеет два преимущества. Первое — умножение полинома на x может быть выполнено простым сдвигом одного бита в n -битовом слове; операция может быть реализована на любом языке программирования. Второе — результат может быть использован, если максимальная степень полинома n–1. В этом случае сокращение может быть сделано просто с помощью применения операции 8. Мы можем разработать простой алгоритм для нахождения промежуточных результатов.
0, тогда надо сдвинуть предыдущий результат на один бит влево.1:
а. надо сдвинуть на один бит влево, и
б. применить к нему операцию Повторим пример 6.9 для двоичной последовательности размером 8 бит.
Пусть P1 = 00100110, P2 = 10011110, модуль = 100011010 (девять битов). Обозначим операцию
| Степень | ||
|---|---|---|
| x0 $$\otimes$$ P2 | 10011110 | |
| x1 $$\otimes$$ P2 | 00111100 | (00111100) $$\oplus$$ (00011010) = 00100111 |
| x2 $$\otimes$$ P2 | 01001110 | 01001110 |
| x3 $$\otimes$$ P2 | 10011100 | 10011100 |
| x4 $$\otimes$$ P2 | 00111000 | (00111000) $$\oplus$$ (00011010) = 00100011 |
| x5 $$\otimes$$ P2 | 01000110 | 01000110 |
| P1 $$\otimes$$ P2 = (000100110) $$\oplus$$ (01001110) $$\oplus$$ (01000110) = 00101111 | ||
В этом случае для умножения этих двух полиномов нам надо только пять операций левого сдвига и четыре n-1 необходимо максимально (n–1) операций левого сдвига и 2n операций
Пример 6.10
Поле GF(23) состоит из 8 элементов. Покажем умножение и сложение таблиц для этого поля, используя неприводимый x3+x2+1. Мы будем оперировать с трехбитовым словом и полиномом. Заметим, что имеется два полинома третьей степени (см. таблицу 6.1). Другой (x3 + x + 1) для умножения имеет таблицу, полностью отличающуюся от первой. Таблица 6.6 показывает сложение. Затемненные клетки (нулевые) дают обратные пары для сложения.
Таблица 6.7 показывает умножение. Затемненные клетки (единичные) дают обратные пары при умножении.
Иногда проще определить элементы поля GF(2n), используя генератор. В этом поле с неприводимым полиномом f(x) и элементом поля a нужно удовлетворить отношение f(а) = 0. В частности, если g — генератор поля, то f(g)=0. Тогда можно доказать, что элементы поля могут быть сгенерированы как
{0, g,g, g2,.... gn}, где N = 2n – 2
| $$\oplus$$ | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
|---|---|---|---|---|---|---|---|---|
| 000 (0) | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
| 001 (1) | 001 (1) | 000 (0) | 011 (x+1) | 010 (x2) | 101 (x2+1) | 100 (x2+x) | 111 (x2+x+1) | 110 (x2 + x) |
| 010 (x) | 010 (x) | 011 (x+1) | 000 (0) | 001 (1) | 110 (x2 + x) | 111 (x2+x+1) | 100 (x2+x) | 101 (x2+1) |
| 011 (x+1) | 011 (x+1) | 010 (x) | 001 (1) | 000 (0) | 111 (x2+x+1) | 110 (x2 + x) | 101 (x2+1) | 100 (x2) |
| 100 (x2) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) |
| 101 (x2+1) | 101 (x2+1) | 100 (x2) | 111 (x2+x+1) | 110 (x2 + x) | 001 (1) | 000 (0) | 011 (x+1) | 010 (x) |
| 110 (x2 + x) | 110 (x2 + x) | 111 (x2+x+1) | 100 (x2) | 101 (x2+1) | 010 (x) | 011 (x+1) | 000 (0) | 001 (1) |
| 111 (x2+x+1) | 111 (x2+x+1) | 110 (x2 + x) | 101 (x2+1) | 100 (x2) | 011 (x+1) | 010 (x) | 001 (1) | 000 (0) |
| $$\oplus$$ | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
|---|---|---|---|---|---|---|---|---|
| 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) | 000 (0) |
| 001 (1) | 000 (0) | 001 (1) | 010 (x) | 011 (x+1) | 100 (x2) | 101 (x2+1) | 110 (x2 + x) | 111 (x2+x+1) |
| 010 (x) | 000 (0) | 010 (x) | 100 (x) | 110 (x2 + x) | 101 (x2+1) | 111 (x2+x+1) | 001 (1) | 011 (x+1) |
| 011 (x+1) | 000 (0) | 011 (x+1) | 110 (x2 + x) | 101 (x2+1) | 001 (1) | 010 (x) | 111 (x2+x+1) | 100 (x2) |
| 100 (x2) | 000 (0) | 100 (x2) | 101 (x2+1) | 001 (1) | 111 (x2+x+1) | 011 (x+1) | 010 (x) | 110 (x2 + x) |
| 101 (x2+1) | 000 (0) | 101 (x2+1) | 111 (x2+x+1) | 010 (x) | 011 (x+1) | 110 (x2 + x) | 100 (x2) | 001 (1) |
| 110 (x2 + x) | 000 (0) | 110 (x2 + x) | 001 (1) | 111 (x2+x+1) | 010 (x) | 100 (x2) | 011 (x+1) | 101 (x2+1) |
| 111 (x2+x+1) | 000 (0) | 111 (x2+x+1) | 011 (x+1) | 100 (x2) | 110 (x2 + x) | 001 (1) | 101 (x2+1) | 010 (x) |
Пример 6.11
Для генерирования элементов поля GF(24) используйте f(x) = x4 + x +1.
Решение
Элементы 0, g0, g 1, g2 и g3 могут быть сгенерированы достаточно просто, потому что в 4 -0, x0, x 1, x2 и x3 (не требуется деления на g4 до g14, которые представляют g4 до g14 от x4 до x14, нужно разделить на неприводимый f(g) = g4 + g +1 = 0. Применив это отношение, мы имеем g4 = –g–1. поскольку сложение полей и вычитание полей — та же самая операция, g4 = g + 1. Мы используем это отношение, чтобы найти значение всех элементов в виде 4 -битовых слов:
0 = 0 = 0 = 0 -> 0=(0000) g0 = g1 = g1 -> g1 = (0010) g2 = g2 = g2 -> g2 = (0100) g3 = g3 = g3 -> g3 = (1000) g4 = g4 = g + 1 -> g4 = (0011) g5 = g(g + 1) = g2 + g -> g5 = (0110) g6 = g(g2 + g) = g3 + g2 -> g6 = (1100) g7 = g(g3 + g) = g3 + g + 1 -> g7 = (1011) g8 = g(g3 + g + 1) = g2 + 1 -> g8= (0101) g9 = g(g2 + 1) = g3 + g -> g9 = (1010) g10 = g(g3 + g) = g2 + g + 1 -> g10 = (0111) g11 = g(g2 + g + 1) = g3 + g2 + g -> g11 = (1110) g12 = g(g3 + g2 + g) = g3 + g2 + g + 1 -> g12 = (1111) g13 = g(g3 + g2 + g + 1) = g3 + g2 + 1 -> g13 = (1101) g14 = g(g3 + g2 + 1) = g3 + 1 -> g14 = (1001)
Главная идея состоит в том, что вычисление элементов поля от g4 до g14 сводится к использованию соотношения g4 = g +1 и предыдущих вычислений. Например,
g12 = g(g11) =g(g3 + g2 + g) = g4 + g3 + g2 = g3 + g2 + g + 1
После сокращения можно просто преобразовать степени в n -битовое слово. Скажем, g3 + 1 эквивалентно 1001, потому что присутствуют элементы со степенью 0 и 3. Заметим, что элементы с одинаковой степенью при таком процессе вычисления отменяют друг друга. Например, g2 + g2 = 0.
Нахождение
Аддитивная g3 = g3.
Найти мультипликативную g3, как показано ниже:
Заметим, что в этом случае степень рассчитывается по модулю 2n – 1,
24 – 1 = 15.
Поэтому –3 mod 15 = 12 mod 15.
Можно легко доказать, что g3 и g12 есть инверсные (обратные числа), потому что g3 g12 = g15 = g0 = 1.
Сложение и вычитание — это одинаковые операции. Промежуточные результаты могут быть упрощены, как проиллюстрировано в следующем примере.
Пример 6.12
Этот пример показывает результаты операций сложения и вычитания:
a. $$\left( {{g^3} + {g^{12}} + {g^7}} \right) = {g^3} + \left( {{g^3} + {g^2} + g + 1} \right) + \left( {{g^3} + g + 1} \right) = {g^3} + {g^2} \to \left( {{\text{11}}00} \right)$$
b. $${g^3}-{g^6} = {g^3} + {g^6} = {g^3} + ({g^3} + {g^2}) = {g^2} \to \left( {0{\text{1}}00} \right)$$
Умножение есть сложение степени по модулю 2n – 1. Деление — это умножение, которое использует мультипликативную
Пример 6.13
Ниже показаны операции умножения и деления:
а. $${g^9} \times {g^{11}} = {g^{20}} = {g^{20\bmod 15}} = {g^5} = {g^2} + g \to \left( {0110} \right)$$
б. $${g^3}/{g^8} = {g^3} \times {g^7} = {g^{10}} = {g^2} + g + 1 \to \left( {0111} \right)$$
Конечное поле GP (2n) может использоваться для того, чтобы определить четыре операции — сложение, вычитание, умножение и деление n -битных слов. Только деление на нуль не определено. Каждое n -битовое слово может быть представлено как n – 1 с коэффициентами в GF(2), — это означает, что операции на n -битовых словах могут быть представлены как операции на этом полиноме. При умножении двух полиномов необходимо сделать эти операции операциями по модулю. Для этого мы должны определить неприводимый n. Чтобы найти мультипликативные
Нижеследующие книги и сайты обеспечивают более детальное рассмотрение понятий, обсужденных в этой лекции.
[Dur05], [Ros06J], [Bla03], [BW00] и [DF04] основательно рассматривают алгебраические структуры.
Нижеследующие сайты дают больше информации о темах, обсуждаемых в этой лекции.
H группы G — G, если само H является группой с соответствующими операциями на G. Если G и H соответственно |G| и |H|, тогда |H| делит |G|.a в группе — наименьшее положительное целое число n, такое, что an = e (единичному элементу).pn, где p — простое число, а n — положительное целое число. GF(pn) поля используется в операциях на n-битовых словах в криптографии.n -битовые слова, используются полиномы с коэффициентами в GF(2). Сложение и умножение n -битовых слов могут быть определены как сложение и умножение полиномов.
Иногда проще определить элементы GF(2n) -поля, используя генератор. Если g — генератор поля, то f(g) = 0. Нахождение G = <Z4, +>:3 + 2 и 3–2 в этой группе.[1 3 2], [3 2 1] и [2 1 3]. Покажите, как Боб может использовать только одну перестановку, чтобы изменить процесс на противоположный. Пользуйтесь таблицей 5.2.f(x) = x4 + x3 +1.f(x) = x4 + x3 +1.f(x) = x4 + x3 +1.GF(12)GF(13)GF(16)GF(17)n -битовых слов найдите полиномы, которые представляют эти слова.100101010000100011n -битовое слово, которое представлено каждым из следующих полиномов:x2 + 1 в GF(24)x2 + 1 в GF(25)x + 1 в GF(23)x7 в GF(28)GF(7) найдите результат следующих операций:5+35–4(x) и (x + 1) — неприводимые полиномы степени 1.(x2 + x + 1) — неприводимый 2.(x3 + x2 + 1) — неприводимый 3.2 -битовые слова, используя полиномы:(11) x (10)(1010) x (1000)(11100) x (10000)GF(22). (Заметим, что для этого поля есть только один модуль.)1xx + 1(x4 + x3 + 1) в GF(25), применяя модуль (x5 + x2 + 1).GF(24), используя (x4 + x3 + 1) как модуль.(x3 + x2 + x + 1) (x2 + 1) в GF(24), используя алгоритм, приведенный в таблице 6.5, и пользуясь (x4 + x3 + 1) как модулем.(10101) на (10000) в GF(25), используя алгоритм, приведенный в таблице 6.5, и пользуясь (x5 + x2 + 1) как модулем.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.