On s'intéresse à la division euclidienne de 2 polynomes A et B à coefficients sur un corps fini K où les opérations arithmétiques sont supposés en cout O(1). Le cas le plus défavorable est celui où le degré de B est à peu près la moitié de celui de A. Si A est de degré n, B de degré m avec m proche de n/2, la division naive est alors en O(n^2).
Soit donc
Code : Tout sélectionner
A=B*Q+R
On commence par faire le changement de variable x->1/x, et on multiplie par x^n
Code : Tout sélectionner
x^n*A(1/x)=x^m*B(1/x)*x^(n-m)*Q(1/x)+x^(n-m+1)*x^(m-1)*R(1/x)
Code : Tout sélectionner
a=b*q+x^(n-m+1)*r
L'algorithme de division rapide consiste à calculer l'inverse de b modulo x^(n-m+1), on en déduit q puis R par des opérations de multiplication qui peuvent etre accélérées.
Pour calculer l'inverse de b modulo x^t, on utilise une suite récurrente b_t de polynomes.
Pour t=1, on prend b_0=inverse(coefficient constant de b).
Soit b_t l'inverse de b modulo x^t, on a donc :
Code : Tout sélectionner
b*b_t=1+x^t*c
Code : Tout sélectionner
b*b_t*(1-x^t*c)=1 mod x^2t
Code : Tout sélectionner
b_2t=2*b_t-b*b_t^2 mod x^2t