Xavier-FranÃois Roblot on Wed, 19 May 2010 09:20:23 +0200

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

Computation of binomials modulo p^M

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. 



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.