Le test de primalité naïf est-il polynomial ?

1. L'algorithme fait $\Theta (\sqrt{N})$ divisions. C'est très peu devant $N$ — on serait tenté d'appeler cela « rapide ».

2. L'entrée est l'entier $N$, écrit en binaire : sa taille est $n=\lfloor {\log }_{2}N\rfloor +1$ bits. Donc $N\approx 2^n$ et

$$\sqrt{N}\approx 2^{n/2}.$$

L'algorithme est exponentiel en la taille de l'entrée.

3. Le tableau rend la chose palpable, et les temps sont mesurés :

Treize bits de plus multiplient le temps par quatre-vingt-dix. Une clé cryptographique fait $2048$ bits : l'algorithme demanderait $2^{1024}$ divisions.

Ce que l'exercice enseigne. « Polynomial » ne se juge jamais sur la valeur des nombres, toujours sur leur écriture. La faute est d'autant plus facile que $\sqrt{N}$ a l'air modeste. Le test de primalité est dans $\mathsf{P}$ — l'algorithme AKS, de 2002, est polynomial en $\log N$ —, mais ce n'est pas celui-là qui le prouve.

C'est exactement le défaut annoncé par le chapitre chap:dynamique pour le sac à dos, et il resurgit ici sur un algorithme que tout le monde croit connaître.