Сегодня узнал от @ronrothblum, что вы можете вычислить все n уравнения Лагранжа eq(x, i) за n + ~\log_2{n} умножений в поле (и одно обращение), вместо 2n👇
Если сделать это наивно, это займет 2n умножений в поле (например, ) 👇
2,7K