Effizientes Erhalten von N-Bits! ?

Ist es bei und möglich, das M -te Bit (oder die Ziffer einer beliebigen kleinen Basis) von N zu erhalten! in Zeit / Raum von O (p (ln (N), ln (M))) , wobei p (x, y) eine Polynomfunktion in x und y ist ?$N$$M$$M$$N!$$O( p( ln(N), ln(M) ) )$$p(x, y)$$x$$y$

dh wenn $N = 2^\eta$ , $M = 2^\mu$ (mit $N$ , $M \in \mathbb{Z}$ ) gegeben ist, finde Bit $2^\mu$ von $(2^\eta)!$in $O( p(\eta, \mu) )$ .

Anmerkung: Ich habe dies auf mathoverflow.net fragte hier und haben keine Antworten wurde immer so habe ich Quer gebucht.

In dem Kommentar auf der anderen Seite weist Gene Kopp darauf hin, dass man die Bits niedrigerer Ordnung effizient berechnen kann, indem man modulare Arithmetikbits und Bits höherer Ordnung unter Verwendung der Stirlingschen Näherung ausführt. Diese Frage lautet also wirklich: Wie effizient kann man die Bits mittlerer Ordnung berechnen? .

Dick Lipton hat einen schönen Beitrag aus dem Jahr 2009 über die Beziehung zwischen der Fakultätsfunktion und dem Factoring. Es gibt eine Menge, die nichts mit dieser Frage zu tun hat, aber ein hervorstechender Punkt ist dieser Satz:

Wennkann durch eine geradlinige arithmetische Berechnung in -Schritten berechnet werden, wobei das Faktorisieren Polynomgrößenschaltungen aufweist.O ( log c n $n!$$O(\log^{c} n)$

Ich vermute, dass dies ein Beweis dafür ist, dass Ihre Frage, insbesondere innerhalb der von Ihnen genannten Zeiträume, schwer zu beantworten sein wird.

Sureshs Antwort beantwortet wahrscheinlich die Frage für Sie, aber ich dachte, ich würde auf einen Sonderfall hinweisen. Sie können das Ergebnis immer für die weniger signifikanten Ziffern für jede Basis berechnen. Nehmen Sie als Basis.$p$

Es ist klar, dass jeder p- ^te Term in der Fakultät ein Vielfaches von . Jeder ^-te Term ist ein Vielfaches von usw. Somit ist die höchste Potenz von ein Faktor vonist . ist durch Stirlings-Näherung leicht zu approximieren: . Ferner ist kann die Summe immer effizient berechnet werden, indem stattdessen (da( p 2 ) p 2 p N ! X p = ∑ ⌊ log p ( N ! ) ⌋ i = 1 ⌊ $p$$(p^2)$$p^2$$p$$N!$logp(N!)lnN! ≈NlnN-NpN⌈logp(N)⌉>N! 1≤i≤N⌈logp(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}$i>⌊logp(N!)$\lfloor \frac{N}{p^i}\rfloor = 0$für ).$i > {\lfloor \log_p(N!) \rfloor}$

Somit sind die letzten Ziffern vonsind Null in der Basis . N ! $X_p$$N!$$p$