Эффективно получать биты N! ?

Учитывая и M , возможно ли получить M -й бит (или цифру любого небольшого основания) из N ! во времени / пространстве O ( p ( l n ( N ) , l n ( M ) ) ) , где p ( x , y ) - некоторая полиномиальная функция от x и y ?$N$$M$$M$$N!$$O( p( ln(N), ln(M) ) )$$p(x, y)$$x$$y$

т.е. учитывая , M = 2 μ (с N , M ∈ Z ), найти бит 2 μ из ( 2 η ) ! в O ( p ( η , μ ) ) .$N = 2^\eta$$M = 2^\mu$$N$$M \in \mathbb{Z}$$2^\mu$$(2^\eta)!$$O( p(\eta, \mu) )$

Примечание: я спрашивал об этом на mathoverflow.net здесь и не получал никаких ответов, поэтому я написал кросс-пост.

Из комментария на другом сайте Джин Копп отмечает, что можно эффективно вычислять биты младшего разряда, выполняя модульную арифметику и биты старшего разряда, используя приближение Стирлинга, так что этот вопрос действительно «насколько эффективно можно вычислить биты среднего порядка?» ,

У Дика Липтона есть прекрасный пост с 2009 года о взаимосвязи между факториальной функцией и факторингом. Есть много вещей, которые не имеют отношения к этому вопросу, но один важный момент - эта теорема:

Если может быть вычислено путем арифметического вычисления по прямой линии в O ( log c n ) шагах, тогда факторинг имеет схемы полиномиального размера.$n!$$O(\log^{c} n)$

Я подозреваю, что это является свидетельством того, что на ваш вопрос, особенно в указанные вами сроки, будет сложно ответить.

$p$

$p$$(p^2)$$p^2$$p$$N!$$X_p = \sum_{i=1}^{\lfloor \log_p(N!) \rfloor} \lfloor \frac{N}{p^i}\rfloor$$\log_p(N!)$$\ln N! \approx N \ln N - N$$p^{N \lceil \log_p (N) \rceil} > N!$$1 \leq i \leq {N \lceil \log_p (N) \rceil}$$\lfloor \frac{N}{p^i}\rfloor = 0$$i > {\lfloor \log_p(N!) \rfloor}$

$X_p$$N!$$p$