Obtendo bits de N com eficiência! ?

Dados e M , é possível obter o M 'ésimo bit (ou dígito de qualquer base pequena) de N ! no tempo / espaço de ó ( p ( l n ( N ) , l N ( H ) ) ) , onde P ( x , y ) é uma função polinomial de x e y ?$N$$M$$M$$N!$$O( p( ln(N), ln(M) ) )$$p(x, y)$$x$$y$

Dado que , M = 2 μ (com N , M ∈ Z ), encontre o bit 2 μ de ( 2 η ) ! em O ( p ( η , μ ) ) .$N = 2^\eta$$M = 2^\mu$$N$$M \in \mathbb{Z}$$2^\mu$$(2^\eta)!$$O( p(\eta, \mu) )$

Nota: Eu perguntei isso no mathoverflow.net aqui e não recebi nenhuma resposta, por isso tenho postagens cruzadas.

A partir do comentário no outro site, Gene Kopp ressalta que é possível calcular com eficiência os bits de ordem inferior fazendo aritmética modular e bits de ordem superior usando a aproximação de Stirling, então essa pergunta é realmente 'com que eficiência é possível calcular os bits de ordem média?' .

Dick Lipton tem um belo post de 2009 sobre a relação entre a função fatorial e a fatoração. Há muita coisa que não tem relação com essa questão, mas um ponto importante é esse teorema:

$n!$$O(\log^{c} n)$

Suspeito que seja uma evidência de que sua pergunta, especialmente dentro do prazo que você mencionou, 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$