У меня N-1 (N - степень 2) чисел a<sub>1</sub>,a<sub>2</sub>…a<sub>N-1</sub> в мире модов p (где p - большое простое число)
Моя цель - чтобы найти сумму всех возможных k -группировок (ровно k из чисел, умноженных вместе, mod p), но мне не дано ни одно из значений. Вместо этого мне даны значения p, r и N из приведенного ниже уравнения.
for all 0 <= j < N, (r<sup>j</sup>+a<sub>1</sub>)(r<sup>j</sup>+a<sub>2</sub>)…(r<sup>j</sup>+a<sub>N-1</sub>)
Я также знаю следующее
r<sup>N</sup> ≡ 1 mod p
Для всех 1 <= j < N, r<sup>j</sup> != 1 mod p
Суммирование от j = 0 до N -1 из r<sup>j</sup> ≡ 0 mod p
До сих пор я понял следующее
Если мы скажем, что результаты умножения входных данных = y и используют N = 4 в качестве примера, при срыве получим уравнение
y<sub>j</sub> ≡ r<sup>3j</sup> + b<sub>1</sub>r<sup>2j</sup> + b<sub>2</sub>r<sup>j</sup> + b<sub>3</sub>
где b<sub>k</sub> это сумма всех возможных k -группировок (ответ, который я ищу)
Я также знаю, что у меня есть форма значения балла (r<sup>j</sup>, y<sub>j</sub>)
Пока все Я пытался (умножение на матрицу P<sup>-1</sup>(x), интерполяция Лагранжа) не дал мне полезного ответа, у меня нет идей относительно того, как рассчитать эти коэффициенты, что означает, что я даже не могу начать кодировать программа для этого.
Пример, из которого я должен работать, дает следующую информацию (a<sub>1</sub> = 6, a<sub>2</sub> = 13, a<sub>3</sub> = 30, но мне не нужна эта информация для ее решения )
p = 53
r = 30
y1 = 17
y2 = 24
y3 = 44
y4 = 0
и мой вывод должен быть
b1 = 49
b2 = 12
b3 = 8
У кого-нибудь есть какие-либо предложения? Я знаю, что FFT может быть вовлечен, потому что мы узнали об этом в то время, но я не могу найти использование для него, которое не оставляет меня с воображаемыми числами.
EDIT: исправлено форматирование