Max Alekseyev on Wed, 19 May 2010 16:19:39 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Computation of binomials modulo p^M

The following paper may be helpful:

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


2010/5/19 Xavier-FranÃois Roblot <>:
> 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.