Re: Computation of binomials modulo p^M

[Max Alekseyev <maxale@gmail.com>]

The following paper may be helpful:
http://www.cecm.sfu.ca/organics/papers/granville/index.html

I have PARI/GP implementation of the formula for binomial(m,n) modulo
p^k from Theorem 1 given there.

Max

2010/5/19 Xavier-FranÃois Roblot <roblot@math.titech.ac.jp>:
> Dear PARI user,
>
> This is not really a question related to PARI but more a computational question. I hope you won't mind but I thought people on that list might be able to give me some help with the following problem.
>
> Let p be a prime (say less than 50), M an integer (such that p^M is about 10^10) and N another integer (say smaller than 30). For s of size p^M, I am interesting to compute all the binomial coefficients binom{s}{n} modulo p^M for n = 0 up to N-1. At the moment, I am doing that in the straightforward way using the classic relation between binom{s}{n+1} and binom{s}{n} and it works okay. But, since this computation is really the bottleneck in the project I am working on at the moment, I'll be very interested to hear about faster solutions.
>
> Best,
>
> Xavier
>
> PS. Another solution is to compute (1+T)^s (mod p^M, T^N) using binary exponentiation but I think it is slower than the direct approach.
>