Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?i.e. Given $N = 2^\eta$, $M = 2^\mu$ (with $N$, $M \in \mathbb{Z}$), find bit $2^\mu$ of $(2^\eta)!$ in $O( p(\eta, \mu) )$.Note: I have asked this on mathoverflow.net here and have not been getting any answers so I have cross-posted.From the comment on the other site, Gene Kopp points out that one can efficiently compute the lower order bits by doing modular arithmetic and higher order bits using Stirling's approximation, so this question is really 'how efficiently can one compute the middle order bits?'.
Efficiently getting bits of N! ?
ds.algorithms;nt.number theory
Dick Lipton has a beautiful post from 2009 on the relationship between the factorial function and factoring. There's a lot there that is unrelated to this question, but one salient point is this theorem:If $n!$ can be computed by a  straight-line arithmetic computation  in $O(\log^{c} n)$ steps, then  factoring has polynomial size  circuits.I suspect that this is evidence that your question, especially within the time bounds you mention, is going to be difficult to answer. 