Мотивация. Существует быстрое приближение к обычному умножению. Концептуально он работает как длинное умножение, за исключением того факта, что перенос отбрасывается, а не применяется к более значимой позиции. Отсюда и его название: продукт без переноски. Одним из способов использования является повышение скорости приложений, выполняющих шифрование блочным шифром в Режим Галуа/Счетчик. Операция также известна как XOR умножение, так как сложение с отбрасыванием переноса эквивалентно исключающему или.
Этот вопрос касается качества этого приближения с точки зрения расстояния Хэмминга.
Продукт без переноски. Предположим, у нас есть два неотрицательных целых числа $a=\sum_{i}a_{i}2^{i}$ и $b=\sum_{i}b_{i}2^{i}$, с $a_i , b_i \in \{ 0 , 1\}$ обозначающие биты этих чисел. Затем продукт без переноски из $а,б$ определяется как $c=\sum_{i}c_{i}2^{i}$, с каждым битом $c_i$ вычисляется как XOR произведений битов из входных чисел следующим образом:
$$c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{ij}.$$
Вопросы. С точки зрения $n$, какой максимум Расстояние Хэмминга от обычного продукта к продукту без переноски, который любой $n$-битные числа могут быть? И каково среднее расстояние Хэмминга между обычным и бескарровым произведением $n$-битные числа?
