По поводу вопроса 1) - как я понял, речь идет о простом

.
Есть формула, доказанная еще Гауссом:
где

определяется из условий

и

. Таким образом, вычисление биномиального коэффициента сводится к представлению

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