2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Факториал за полиномиальное время
Сообщение06.04.2008, 00:10 
Аватара пользователя
Доброе время суток.

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

Пусть $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$)?

 
 
 
 
Сообщение06.04.2008, 10:31 
Аватара пользователя
По поводу вопроса 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 у меня большие сомнения).

 
 
 
 
Сообщение06.04.2008, 15:35 
Аватара пользователя
Спасибо!

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

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

 
 
 
 
Сообщение08.04.2008, 16:06 
Аватара пользователя
:?
Вроде бы речь шла о вычислении по модулю p.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group