Оглавление
Изделие без необходимости переноски
-
Произведение двоичных чисел без переноса
- Результат умножения двух двоичных чисел без переноса.
- Операция работает как длинное умножение, но без переноса.
- Используется для моделирования операций над конечными полями.
-
Определение
- Произведение двух чисел a и b без переноса определяется как c = ∑i c_i 2^i.
- Каждый бит c_i вычисляется как исключающее или произведение битов из a и b.
-
Пример
- Умножение a = 101000102 и b = 100101102 дает c = 1011000111011002.
- Для каждого бита в a, b сдвигается влево на указанное положение.
- Сдвинутые версии объединяются с использованием исключающего или.
-
Умножение многочленов
- Произведение без переноса можно рассматривать как умножение многочленов на поле GF(2).
- Исключающее или соответствует добавлению в GF(2).
- Пример показывает, как (X^7 ⋅ X^1) + (X^1 ⋅ X^7) ≡ 0 и (X^7 ⋅ X^2) + (X^5 ⋅ X^4) ≡ 0.
-
Приложения
- Элементы GF(2n) представляются в виде многочленов от GF(2)[X].
- Умножение элементов поля состоит из умножения многочленов и приведения к неприводимому многочлену.
- Умножение без переноса используется для первого шага вычисления.
- Такие поля находят применение в криптографии и алгоритмах контрольной суммы.
-
Реализации
- Новейшие процессоры x86 поддерживают CLMUL для выполнения операции.
- RISC-V также поддерживает Zbc: умножение без переноса.
- Программные реализации доступны в криптографических библиотеках.
-
Другие базы
- Определение продукта без переноса применимо к основаниям, отличным от 2.
- Результат зависит от основы, что делает бинарную форму наиболее практичной.
- Многочлены над другими конечными полями имеют приложения, но не рассматриваются как умножение чисел без переноса.