Круговая свертка бинарных векторов (mod 2) с использованием NTT

Question

Пусть x, y будут векторами длины n с элементами 1 или 0. Я хочу эффективно вычислить круговую свертку

(x * y) mod 2

Где каждая составляющая результата берется по модулю 2.

Я знаю, как это сделать с помощью быстрого преобразования Фурье (умножить преобразования Фурье x и y. Преобразовать обратно. Выполнить «mod 2») . Однако для решения дискретной задачи и для больших n используются вычисления с плавающей запятой (я интересует n ~ 10^7), это может привести к ошибкам округления. Я ожидаю, что есть лучший способ сделать это, используя теоретико-числовое преобразование (NTT), но, к сожалению, я не знаком с теорией чисел или NTT.

Я смотрел на этом сайте. После процедуры там,

1. скажем, n = 10^7. мне нужно
2. модуль М (используйте 10^7).
3. простое число N=kn+1 для некоторого k. (используйте N = 3 * 10^7 + 1)
4. корень ω≡g^kmodN , где g — образующая (например, ω=2744)
5. Сделайте трансформацию и т.д.

Вопрос

Это кажется многообещающим. Однако мне понадобятся 32-битные целые числа для хранения каждого бита во время этого вычисления?Кроме того, это не использует тот факт, что мне нужны результаты только по модулю 2. Есть ли способ использовать это для упрощения процедуры?Поскольку я не знаю теории чисел, это не очевидно для меня.

Я не прошу полного решения, только для аргумента, если мой "мод 2" значительно упрощает реализацию (как с точки зрения сложности реализации необходимых алгоритмов, так и вычислительных ресурсов).

Другой вопрос: если невозможно упростить использование «мода 2», как вы думаете, будет ли окупаться использование NTT, а не просто использование известной библиотеки FFT для решения задачи с плавающей запятой?

Answer 1

Для NTT ваша процедура выглядит правильной. Да, вам понадобятся 32-битные целые числа для каждого бита исходного вектора. К сожалению, вы мало что можете сделать, чтобы использовать тот факт, что конечным результатом является мод 2, поскольку вам нужен корень порядка 10^7. Возможно, вы сможете уменьшить это число в два раза (и выполнить стандартное ДПФ для нескольких базовых уровней рекурсии), но, условно говоря, это мало что изменит.

Обратите внимание: для вашей реализации БПФ я считаю, что вы могли бы использовать целочисленную арифметику, начиная с ее мода 2, но я не уверен, что это будет вообще эффективно. Подробности см. в этом ответе по математическому обмену стеками .