La taille d'une entrée n'est pas sa valeur

bool premier(long n) {
    if (n < 2) { return false; }
    for (long d = 2; d * d <= n; d = d + 1) {
        if (n % d == 0) { return false; }
    }
    return true;
}

Non, et c'est le piège le plus profond du chapitre.

La complexité se compte « en fonction de la taille de l'entrée ». Or la taille d'un entier $n$ n'est pas $n$ : c'est le nombre de chiffres — ou de bits — qu'il faut pour l'écrire, soit $k=\lfloor {\log }_{2}n\rfloor +1$. En fonction de $k$, l'algorithme fait

$$\sqrt{n}=\sqrt{2^k}={\left(\sqrt{2}\right)}^k$$

divisions : c'est exponentiel en la taille de l'entrée.

La mesure le rend palpable. Pour le plus grand nombre premier inférieur à $2^k$ :

              n     | bits | divisions | temps
             1021   |   10 |        30 | < 1 ms
          1048573   |   20 |      1022 | < 1 ms
       1073741789   |   30 |     32766 | < 1 ms
    1099511627689   |   40 |   1048574 | 0,9 ms
 1125899906842597   |   50 |  33554430 |  29 ms

Dix bits de plus multiplient le travail par $32$, exactement : $30\to 1022\to 32766\to 1048574\to 33554430$. Ce n'est pas approximativement $32$, c'est $\sqrt{2^{10}}=2^5=32$.

L'extrapolation est édifiante. Au rythme mesuré — $33554430$ divisions en $29$ ms, soit environ $1,1$ milliard par seconde —, un nombre de $100$ bits demanderait $2^{50}$ divisions, soit près de onze jours. Un nombre de $200$ bits en demanderait $2^{100}$, soit plus longtemps que l'âge de l'univers. Les clés cryptographiques ont aujourd'hui $2048$ bits ; c'est exactement là-dessus que repose leur sécurité.