Multiplication rapide par FFT : idée de départ

Multiplication pour interpolation. On cherche à multiplier deux

polynômes A et B de degré ≤ n.
Le résultat C = A · B est un polynôme de degré ≤ 2n et donc
complétement déterminé par 2n + 1 valeurs.
Les valeurs de C sont faciles à calculer : C(x) = A(x) · B(x).

Problèmes. Il faut quand même calculer beaucoup de valeurs de C, et,

surtout reconstruire un polynôme à partir de ses valeurs ce qui peut être
un problème coûteux.

Solution. On utilise les racines de l’unité et la transformée de Fourier

discrète !

Remarque. FFT = Fast Fourier Transform

Multiplication rapide par FFT : transformée de Fourier

discrète
Racine de l’unité. On suppose que l’on travaille dans un anneau R
(unitaire, commutatif) qui contient ω une racine primitive de l’unité
d’ordre n ≥ 2, c’est-à-dire ωn = 1 et ωm 6 = 1 pour 1 ≤ m < n .

DFT. Pour A ∈ R[X ], on pose

n 1
n
DFTω (A) = A (1), A(ω), . . . , A(ω ) ∈R
−

C’est un morphisme d’anneau (où l’addition et la multiplication dans R n

se font composante par composante) de noyau l’idéal engendré par
X n 1.
−

On note R n [X ] l’ensemble des polynômes de R[X] et de degré < n .

Alors la restriction de DFT à Rn [X] est injective.

Convolution. Pour A, B ∈ Rn [X], on pose

A ∗ B = A · B mod X n −

1 ∈ R n[X]

Proposition
L’ensemble R n [X ] avec l’addition classique et la convolution pour
multiplication est un anneau isomorphe (par DFT) à R n .

Explicitement, pour A, B ∈ R n [X], on a

DFTω (A ∗ B ) = DFTω (A ) DFTω (B )

·

DFTω (A + B ) = DFTω (A ) + DFTω( B)

Remarque. ( Rn[ X] , +, ∗) ∼
= R[ X ]/( X n −

1)
Multiplication rapide par FFT : matrices de Vandermonde
Définition. Pour α ∈ R, on définit
···
 
1 1 1 1
1 α α2 ··· α n−1 
2 4
· · · α 2(n−1)
(i 1)(j 1)
 
Vα = (α
−

)1≤i,j≤n = 1
−

 α α 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1 αn−1 α 2(n−1) · · · α(n−1)

Calcul de DFT et DFT−1

Soit A ∈ Rn [X], on écrit A = an−1 X n−1 + · · · + a0 . On a alors
DFTω (A) = (a0 , a1 , . . . , an −

1) · Vω

Pour (v0 , . . . , vn−1 ) ∈ Rn , on pose

(a0 , a1 , . . . , an −

1) = (v 0 , . . . , vn −

1) · Vω−1
n−1
Alors DFTω an −

1X + · · · + a0 v 0 , . . . , vn −

Théorème
Vω · Vω 1
−

= n · Idn
(i−1)(j−1) n


Preuve. On a Vα = α i,j=1
et donc l’entrée i, j de la matrice
Vω · Vω−1 est
n
X n
X
ω (i−1)(k−1) ω−(k−1)(j−1) = ω (k−1)(i−j)
k=1 k=1

6 j) alors ωi−j est une racine primitive de l’unité

Mais, si n - i − j (i.e i =
6 = 1 et d’ordre divisant n et donc
n
(
X n si i = j,
(ωi−j )k =
k=1
0 sinon

Corollaire. Vω−1 = n−1 Vω −

1 (si n est inversible dans R).

Multiplication rapide par FFT : premier essai

Méthode. Soit deux polynômes A, B ∈ R[X] avec deg(AB) < n, alors

A · B = A ∗ B = DFT−1
w (DFTw (A ∗ B))

= DFT−1
w (DFTw (A) · DFTw (B))
1
= DFTw−1 (DFTw (A) · DFTw (B))
n

Algèbre linéaire. Multiplication d’une matrice n × n par un vecteur de

dimension n se fait en O(n2 ) opérations dans R, et donc la méthode
ci-dessus donne un algorithme en O(n2 ) opérations dans R.

FFT. Il faut pouvoir calculer plus rapidement la fonction DFT et donc

pour cela utiliser plutôt la transformée de Fourier rapide (FFT).
Multiplication rapide par FFT : Transformée de Fourier
rapide
Hypothèses. R contient une racine primitive de l’unité d’ordre n = 2k
et 2 est inversible dans R.

Diviser pour régner. Pour A(X) ∈ Rn[X], on calcule les restes des
divisions euclidiennes

R± (X) = A(X) mod X n/2 ± 1.

Les polynômes R+ et R− sont de degré < n/2 = 2k−1 et peuvent être

calculés très facilement par la formule (en posant m = n/2)

a2m−1 X 2m 1
+ · · · + am X m + am−1 X m 1
+ · · · + a0 mod (X m ∓ 1)
− −

m−1
= (a2m −

1 ± am 1 )X
−

+ · · · + (am ± a0 ).

Multiplication rapide par FFT : Transformée de Fourier

rapide
Rappel. R± (X ) = A(X ) mod Xn/ 2 ± 1

Suite. Pour 0 ≤ l ≤ n/2, on a

A(ω2l ) = R (ω2l )
−
et A( ω2 l+1) = R +(ω 2l+1 )

puisque ω ln = 1 et ω n/ 2 = −

1.

Comme ω2 est une racine primitive de l’unité d’ordre n/2, le calcul de

DFTω (A) revient à calculer

DFTω 2 ( R ) et DFTω2 (R+)

˜

où R̃+ (X ) = R + (ωX).

Multiplication rapide par FFT : Transformée de Fourier

rapide
Algorithme.
nP1
−

Soit A(X ) = ai X i ∈ R n [X] avec n = 2k , calcule DFTω (A).

i =0
(1) Si n = 1 alors retourner a0
(2) Faire
n/
P2 n/
P2
R ←
−
(a i + ai +n/ 2 )Xi et R̃+ ← (ai −

ai +n/2 )ωi X i
i=0 i=0

(3) Calculer DFTω 2 (R ) et DFTω2 (R̃+) par cet algorithme (récursif)

−

(4) Retourner
(R (1), R̃+ (1), R (ω2 ) , R̃+ (ω 2 ), . . . R (ωn 2 ), R̃ +(ω n 2 ))
− − −
− −

Complexité. On a T (n) = 2T(n/2) + n pour les additions et

T (n) = 2T(n/2) + n/2 pour les multiplications, et donc le coût de
l’algorithme est O(n log n).
 Complexité de l’algorithme de multiplication par FFT
Soit R un anneau contenant les racines primitives de l’unité d’ordre 2k
pour tout k ≥ 1.
Alors, il est possible de multiplier deux polynômes de R[X ] de degré < n
en O(n log n) opérations de R.

Et sinon ? Si R ne contient pas une racine de l’unité d’ordre 2k, mais

cependant 2 est inversible dans R, on travaille plutôt dans
k 1
D = R[T ]/(T 2
−

+ 1)
¯

qui contient R et dans lequel ω = T est une racine primitive de l’unité

d’ordre 2 k.
Problème. Travailler dans D revient à travailler dans R[T ] et on tourne
en rond...

Multiplication rapide par FFT : Schönhage et Strassen

Plongements. On pose s = 2 bk/2c et t = 2 dk/2e , ainsi on a n = st, et
t = s ou 2s.
On pose D = R[T ]/( T2s + 1) et on note ω = T ∈ D, c’est une racine de
¯

l’unité d’ordre 4s
.

Pour A ∈ Rn [X ], on écrit sous la forme

t 1
−

X
A (X ) = Ai (X ) · Xsi
i=0

avec Ai ∈ Rs [X]. Puis, on définit

t 1
√
−

X
Ã( X) = A i(ω) · X i ∈ Dt [X ] (Note : t ' n).
i=0

Réciproque. On peut reconstruire A à partir de à en remplaçant X par

X s puis ω par X.

Multiplication rapide par FFT : Schönhage et Strassen

Produit. Pour A, B ∈ R[X ] avec deg(AB) < n . On pose H˜ = Ã B̃ et
on note H ∈ R [X ], le polynôme reconstruit à partir de H̃ en remplaçant
X par Xs et ω par X .

Lemme
A(X )B(X ) = H(X )
tP1
−

tP1
−

Preuve. On écrit A (X ) = Ai ( X) · X si et B (X ) = B i (X ) · X si,

i=0 i=0
d’où
i
2t 2
−

i
XX
Ã( X) B̃( X ) = Aj (ω) Bi −

j ( ω) X .

i=0 j =0

Or deg(Aj Bi j ) < 2s donc il n’y a pas de “simplification” dans D, et en

−

remplaçant X par Xs et ω par X , on obtient

2t
X2 Xi
−

Aj ( X) Bi j (X) X si = A(X ) B(X ).

−

i=0 j=0
Multiplication rapide par FFT : Schönhage et Strassen
Description. Pour multiplier deux polynômes A, B ∈ R[X ], on prend k
minimal tel que deg(AB) < n = 2 k . On pose s = 2 bk/2 c et t = 2d k/2 e.
On calcule les polynômes à et B̃ par la méthode expliquée ci-dessus, et
on calcule le produit à B̃ dans Dt[X ] (par FFT !) pour en déduire le
résultat de AB .

Pour calculer dans D = R[T ]/(T 2s + 1), on utilise la même méthode

√
récursivement (avec un degré de taille n).

Complexité de l’algorithme de Schönhage et Strassen

L’algorithme de Schönhage et Strassen calcule le produit de deux
polynômes de R[X ] de degré < n en O(n log n log log n) opérations
dans R .

L’algorithme de Schönhage et Strassen calcule le produit de deux entiers

de taille 2wn en O (n log n log log n) opérations sur des entiers de w bits.

Division euclidienne rapide par la méthode de Newton

Problème. On note deg A = n et deg B = m avec n ≥ m et on suppose

que B est unitaire.
Il existe deux uniques polynômes Q et R dans R[X] tels que

A(X) = B(X) · Q(X) + R(X) (∗)

avec deg R < deg B.

L’algorithme classique calcule Q et R en O(n2 ) opérations dans R.

Remarque. Si on connaı̂t Q, on peut retrouver R en une multiplication

et une addition de polynômes à coefficients dans R. Donc il suffit de
calculer Q.

Division euclidienne rapide par la méthode de Newton

Polynômes réciproques. Pour P ∈ R [X ] et k ≥ deg P , on note
Reck (P (X)) = X k P (1/X ) ∈ R [X].

On remplace X par 1/X dans (∗) et on multiplie par X n

1   1    
n m n− m Q 1
X A = X B X ·

X X X   1 
+ Xn m +1
Xm 1
R
− −

d’où
Recn(A) ≡ Recm (B) · Recn −

m ( Q) (mod Xn −m+1 ),
et finalement

Recn m ( Q) = Recn (A) · Recm (B) 1

mod Xn m+1
.
− −

Remarque. On peut facilement reconstruire Q à partir de Recn −

m ( Q).
Division euclidienne rapide par la méthode de Newton
Exemple. Prenons R = F11[X ]. On considère les deux polynômes
A(X) = 9X 5 + 10X 3 + 7X 2 + X + 10 et B(X) = X 3 + 6X 2 + 6X + 9

Et donc
Rec5 (A) = 10 X5 + X 4 + 7X 3 + 10X2 + 9
Rec3 (B) = 9X 3 + 6X 2 + 6X + 1

On a n −

m + 1 = 3 et on trouve (cf. plus loin) que

(9X 3 + 6X 2 + 6X + 1)(8X 2 + 5X + 1) ≡ 1 (mod X 3)

Donc
Rec2( Q) = 5X 2 + X + 9, d’où Q (X) = 9X 2 + X + 5

et
R(X ) = A( X ) −

B( X ) · Q( X ) = 6X + 9 .

Division euclidienne rapide par la méthode de Newton

Reformulation. Soit F (X) ∈ D [X ] avec F (0) = 1 et soit l ≥ 1.
On veut trouver G(X) ∈ D[X ] tel que F (X) G(X ) ≡ 1 (mod X l).
·

Inversion par la méthode de Newton

On définit une suite de polynômes Gi ∈ D [X ] par G 0 (X) = 1 et, pour
i≥0
2 2i+1
Gi+1 (X) = 2 Gi (X) F (X) · Gi (X) mod X
−

i
Alors, pour tout i ≥ 0, on a F (X) · Gi (X) ≡ 1 (mod X 2 ) .
Preuve. Clair pour i = 0. Par récurrence, on a, pour i ≥ 1

1 −

F · Gi+1 ≡ 1 −

F · (2Gi −

F · Gi2) ≡ 1 −

2 F · Gi + (F · Gi )2
i+1
≡ (1 −

F · Gi )2 ≡ 0 (mod X 2 ).

Division euclidienne rapide par la méthode de Newton

Exemple. On calcule l’inverse de F (X) = 9X 3 + 6X 2 + 6X + 1 modulo
X 3 dans F11 [X ].
On a

G 0 (X) = 1
G1 (X) = 2 · 1 − (9X 3 + 6X 2 + 6X + 1) · 1 mod X 2
= 5X + 1
G2 (X) = 2 (5X + 1) (9X3 + 6 X2 + 6 X + 1) (5X + 1)2 mod X 4
·

−
·

= 10X + 2 (10X 3 + 3X 2 + 5X + 1)
−

2
= X 3 + 8X + 5X + 1

Donc la réponse est

8X 2 + 5X + 1 .