Eficientemente obteniendo trozos de N! ?

Dados y M , ¿es posible obtener el bit M '(o dígito de cualquier base pequeña) de N ! en tiempo / espacio de O ( p ( l n ( N ) , l n ( M ) ) ) , donde p ( x , y ) es alguna función polinómica en x e y ?$N$$M$$M$$N!$$O( p( ln(N), ln(M) ) )$$p(x, y)$$x$$y$

es decir, dado , M = 2 μ (con N , M ∈ Z ), encuentre el bit 2 μ de ( 2 η ) . en O ( p ( η , μ ) ) .$N = 2^\eta$$M = 2^\mu$$N$$M \in \mathbb{Z}$$2^\mu$$(2^\eta)!$$O( p(\eta, \mu) )$

Nota: He preguntado esto en mathoverflow.net aquí y no he recibido ninguna respuesta, por lo que he publicado.

Del comentario en el otro sitio, Gene Kopp señala que uno puede calcular eficientemente los bits de orden inferior haciendo aritmética modular y bits de orden superior utilizando la aproximación de Stirling, por lo que esta pregunta es realmente '¿qué tan eficientemente se puede calcular los bits de orden medio?' .

Dick Lipton tiene una hermosa publicación de 2009 sobre la relación entre la función factorial y la factorización. Hay muchas cosas que no están relacionadas con esta pregunta, pero un punto destacado es este teorema:

Si se puede calcular mediante un cálculo aritmético en línea recta en pasos O ( log c n ) , luego la factorización tiene circuitos de tamaño polinómico.$n!$$O(\log^{c} n)$

Sospecho que esto es evidencia de que su pregunta, especialmente dentro de los límites de tiempo que menciona, será difícil de responder.

$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$