tony\.reix on Sat, 22 Jan 2005 23:34:31 +0100

 Fw:PARI/gp : binomialmod(a,b,p)

Hi,

Would it be possible to have in Pari/gp an efficient
implementation of the computation of binomials modulo a prime
number ?

The formula has been discovered by E. Lucas.
See :
http://mathworld.wolfram.com/LucasCorrespondenceTheorem.html

The definition is (LaTeX -like) :

binomialmod(a,b,p) :
p must be prime.
a = \prod_{i=0}^{a_max}{a_i*p^i}  a_i < p
b = \prod_{i=0}^{b_max}{b_i*p^i}  b_i < p
binomialmod(a,b,p) \equiv
\prod_{i=0}^{min(a_max,b_max)}{binomial(a_i,b_i)} (mod p)

Here is a simple PARI/gp program:

binomialmod(a,b,p)=
B=1;
while(a!=0 && b!=0,     # I think it is:  &&  and not:  ||
because binomial(i,0)=1
a_=a%p;
b_=b%p;
a =(a-a_)/p;
b =(b-b_)/p;
B =(B*(binomial(a_,b_)%p)%p)
);
return(B)

10th first values modulo 7 :

tb(a,p)=for(i=0,a,print1(i); for(j=0,i,print1(" ",
binomialmod(i,j,p))); print)

? tb(10,7)
0  1
1  1 1
2  1 2 1
3  1 3 3 1
4  1 4 6 4 1
5  1 5 3 3 5 1
6  1 6 1 6 1 6 1
7  1 0 0 0 0 0 0 1
8  1 1 0 0 0 0 0 1 1
9  1 2 1 0 0 0 0 1 2 1
10 1 3 3 1 0 0 0 1 3 3 1

Regards,

Tony

Accédez au courrier électronique de La Poste : www.laposte.net ;
3615 LAPOSTENET (0,34?/mn) ; tél : 08 92 68 13 50 (0,34?/mn)