Числа Белла по простому модулю $p$ - первые $p$ штук

[MetaMorphy]

Всем привет. Если кратко - можно ли их вычислить быстрее чем за $O(p^2)$?

Т.е. для заданного простого $p$ нужно вычислить $B_n \bmod p$, $0 \leqslant n < p$. Очевидный алгоритм требует $O(p^2)$ сложений по модулю $p$.

Кстати, "теория" вокруг связанных с этими числами многочленов — как образов $\Phi(x^n)$ линейного отображения $\Phi$ пространства многочленов в себя, задаваемого путём $\Phi(x^{\underline{n}}) = x^n$, где $x^{\underline{n}} = x(x-1)\ldots(x-n+1)$ — позволила мне обнаружить "много чего интересного" в вычислительном плане. Но не ответ на заданный мной вопрос

[MetaMorphy]

Ура, ответ положительный. Идея — в вычислении производящей функции $\displaystyle\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=e^{e^x-1}$ через "быстрые" алгоритмы композиции степенных рядов. Осталось выбрать подходящий и упростить всё "до предела"...

[MetaMorphy]

В общем, получается уложиться в $O(p \log p)$ операций в $\mathbb{F}_p$.

[MetaMorphy]

Моя чуть более поздняя "находка" здесь.