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

["tony\.reix" <tony.reix@laposte.net>]

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)