Ошибка реализации умножения Шёнхаге-Штрассена

Я пытаюсь реализовать алгоритм умножения Шёнхаге-Штрассена с использованием NTT и сталкиваюсь с проблемой, когда конечный результирующий вектор на самом деле не равен тому, чем он должен быть.

Для двух входных векторов a и b, каждый из которых состоит из N "цифр" из K битов (последние N/2 записи каждого набора равны 0), каждому из которых задан модуль M = 2^(2*K)+1, корень из единицы w = N^(4*K-1) | w^N = 1 mod M, модульная инверсия этого значения wi | wi*w = 1 mod M и u | u*N = 1 mod M, следующий код Python используется для (попытки) умножения этих векторов с помощью алгоритма Шёнхаге-Штрассена:

#a and b are lists of length N, representing large integers
A = [ sum([ (a[i]*pow(w,i*j,M))%M for i in range(N)]) for j in range(N)] #NTT of a
B = [ sum([ (b[i]*pow(w,i*j,M))%M for i in range(N)]) for j in range(N)] #NTT of b
C = [ (A[i]*B[i])%M for i in range(N)] #A * B multiplied pointwise
c = [ sum([ (C[i]*pow(wi,i*j,M))%M for i in range(N)]) for j in range(N)] #intermediate step in INTT of C
ci = [ (i*u)%M for i in c] #INTT of C, should be product of a and b

Теоретически, если я не ошибаюсь, взяв NTT для a и b, умножая по точкам, затем взяв INTT результата, должно получиться произведение, и я протестировал эти методы для NTT и INTT, чтобы подтвердить, что они инвертируют каждый Другие. Однако конечный результирующий вектор ci, а не произведение a и b, является произведением, в котором каждый элемент берется по модулю M, что дает неверный результат для произведения.

Например, запуск теста с N=K=8 и случайными векторами для a, b дает следующее:

M = 2^(2*8)+1 = 65537
w = 16, wi = 61441
u = 57345
a = [212, 251, 84, 186, 0, 0, 0, 0] (3126131668 as an integer)
b = [180, 27, 234, 225, 0, 0, 0, 0] (3790216116)
NTT(a) = [733, 66681, 147842, 92262, 130933, 107825, 114562, 127302]
NTT(b) = [666, 64598, 80332, 54468, 131236, 186644, 181708, 88232]
Pointwise product of above two lines mod M = [29419, 39913, 25015, 14993, 42695, 49488, 52438, 51319]
INTT of above line (i.e. result) = [38160, 50904, 5968, 11108, 15616, 62424, 41850, 0] (11848430946168040720)
Actual product of a x b = [38160, 50904, 71505, 142182, 81153, 62424, 41850, 0] (11848714628791561488)

В этом примере и почти каждый раз, когда я его пробую, элементы реального продукта и результат моего алгоритма одинаковы для нескольких элементов около начала и конца вектора, но к середине они отклоняются. Как я упоминал выше, каждый элемент ci равен элементам a*b по модулю M. Я, должно быть, неправильно понимаю этот алгоритм, хотя не совсем уверен, что именно. Я где-то использую неправильный модуль?


python algorithm multiplication bigint number-theory
person user2649681    schedule 08.10.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Остерегайтесь теории чисел и NTT не являются моей областью знаний, поэтому читайте с предубеждением, но я успешно реализовал NTT в C ++ самостоятельно и использовал его. для больших умножений (bigint, bigfloatingpoint, bigfixedpoint), так что вот некоторые из моих insigtst. Я настоятельно рекомендую вам сначала прочитать оба моих QA:

так что вы можете сравнить свои результаты / код / ​​константы с моими. Однако я развил свой NTT, чтобы использовать одно жестко запрограммированное простое число (самый большой корень единства, который соответствует 32-битному значению).

Теперь, что может быть не так с вашим кодом. Я не пишу код на Python, но я не вижу кода NTT в вашем вопросе. Во всяком случае, из того, что я вижу:

  1. проверьте свой корень или единство

    В своем вопросе вы упоминаете условие:

    w^N = 1 mod M

    но этого далеко не достаточно. См. Первую ссылку выше, где описаны все условия, которые должны быть выполнены (с кодом, который находит и проверяет их). Я не уверен, что ваши параметры соответствуют всем необходимым условиям, и вы просто забыли или пропустили их, поэтому проверьте. IIRC Я тоже боролся с этими условиями, поскольку в то время я кодировал это там, где в моем распоряжении было очень мало информации NTT, и большинство из них было неполным или неправильным ...

  2. Вы не используете модульную арифметику !!!

    Я предполагаю, что ваше простое число равно M (в моей терминологии это p), поэтому все подрезультаты должны быть меньше M, что явно неверно в вашем примере:

    M = 65537
NTT(a) = [733, 66681, 147842, 92262, 130933, 107825, 114562, 127302]
NTT(b) = [666, 64598, 80332, 54468, 131236, 186644, 181708, 88232]

    как вы можете видеть, только первый элемент обоих NTT действителен, все остальные больше M, что неверно !!!

  3. # P10 # # P11 # # P12 #
    # P13 #
    # P14 # # P15 #

Итак, вы не используете модульную арифемику, используете слишком малое число и / или обрабатываете слишком большие фрагменты данных и возможно < / strong> также выбран неправильный штрих.

person Spektre    schedule 09.10.2019