Факториал за полиномиальное время

[Echo-Off]

Доброе время суток.

Интересует следующий вопрос:

Пусть $p>20$ - простое. Можно ли за время, полиномиальное от $\log p$ вычислить:

1)

$$C_{(p-1)/2}^{(p-1)/4} = \frac {(\frac{p-1}2)!}{(\frac{p-1}4)!\cdot(\frac{p-1}4)!}$$

по модулю $p$

2)

$$C_{(p-1)/2}^{(p-1)/3} = \frac {(\frac{p-1}2)!}{(\frac{p-1}3)!\cdot(\frac{p-1}6)!}$$

по модулю $p$ (в предположении, что $p \equiv 1 \pmod{3}$)

3) Вообще $$C_{(p-1)/2}^{k}$ по модулю $p$ для произвольного $k$

4) $n!$ по модулю $p$ (естественно, $n<p$)?

[maxal]

По поводу вопроса 1) - как я понял, речь идет о простом $p\equiv 1\pmod 4$.
Есть формула, доказанная еще Гауссом:

$$\binom{\frac{p-1}{2}}{\frac{p-1}{4}}\equiv 2a\pmod p,$$

где $a$ определяется из условий $p=a^2+b^2$ и $a\equiv 1\pmod 4$. Таким образом, вычисление биномиального коэффициента сводится к представлению $p$ в виду суммы квадратов, что можно осуществить за полиномиальное время (см., например, Высшая арифметика, глава V).

Подробности см. в книге Gauss and Jacobi Sums. Возможно, там же есть ответы и на остальные вопросы (хотя насчет 3 и 4 у меня большие сомнения).

[Echo-Off]

Спасибо!

Насчёт 3 и 4 у меня самого есть сомнения Но может, для них всё равно есть какая-нибудь красивая формула?

[Sonic86]

Очень плохая вещь: при использовании формулы Стирлинга получается, что средний биномиальный коэффициент показательно растет от р. А значит его длина - показательно растет от log(p). Поэтому само его написание невозможно за полиномиальное время.
У меня уже просто такое было - было очень обидно.

[worm2]

Вроде бы речь шла о вычислении по модулю p.