Introduction
Nombres premiers, arithmétique modulaire, exponentiation rapide… ça sert à quelque chose où c’est juste un prétexte à écrire des textes abscons et truffés de formules incompréhensibles ?
Nous pourrions réponde qu’être inutile est un charme, la beauté intérieure du frivole. À ce sujet, le point de vue de Godrey Harold Hardy, que nous avons déjà rencontré, actif dans le domaine qui nous intéresse ici, la théorie des nombres, est emblématique et ironique à plein d’égards. Il écrit dans L’apologie d’un mathématicien2 : « Je n’ai jamais fait quelque chose “d’utile”. Aucune de mes découvertes n’a été faite, ou n’est susceptible de se faire, directement ou indirectement, pour le bien ou le mal, la moindre différence pour le charme du monde. J’ai aidé à former d’autres mathématiciens mais des mathématiciens de la même sorte que moi, et leur travail a été, dans la mesure où je les ai aidés, aussi inutile que le mien. Jugé par toutes les normes pratiques, la valeur de ma vie mathématique est nulle ; et en dehors des mathématiques elle est bien banale. J’ai une seule chance d’échapper à un verdict de banalité complète, celle d’être jugé pour avoir créé quelque chose digne d’être créé. Et le fait que j’ai créé quelque chose est indéniable. »
Ce qui est certains est que trente ans après ce texte, les recherches en théorie des nombres donneront naissance à des applications concrètes dont nous parlions dans le chapitre précédent. D’ici là, voyons un autre exemple, obscur et bien connu des citoyens français.
Clé vitale
Nous avons tous et toutes un numéro de Sécurité sociale, unique qui nous est attribué une fois pour toutes. Prenez votre carte vitale et cherchez-le. Savez-vous comment le NIR, ou numéro d’inscription au répertoire, le nombre à $13$ chiffres dit de Sécurité Sociale est-il déterminé et produit par l’INSEE ? De la manière suivante…
Sa forme est :
$$SAAMMIIIIIPPP$$
Où :
$S$, le sexe est codé $1$ pour les hommes et $2$ pour les femmes.
$AA$, les deux derniers chiffres de l’année de naissance.
$MM$, le mois de naissance.
$IIIII$, le code INSEE de la ville de naissance, que l’on décompose en $II_{D}$ pour le département et $III_{C}$ pour la commune.
$PPP$, le rang d’arrivée parmi les naissances de ce jour en ce lieu.
Il reste à parler du nombre à deux chiffres, légèrement à l’écart, que l’on appelle la clé (que nous noterons $CC$).
C’est en fait un système de vérification. Si par exemple un opérateur se trompait dans sa saisie, ou si vous-même intervertissiez quelques éléments, l’algorithme de contrôle a posteriori produira une clé différente. Le procédé est alors nécessaire mais pas suffisant pour vérifier s’il n’y a pas eu une erreur en entrée. Deux nombres différents peuvent avoir la même clé, mais dans le cas contraire, il y a un problème.
Calcul
Pour le calculer, on considère le reste de la division euclidienne du NIR par $97$ que l’on retranche ensuite à $97$. Comment s’y prend-on ?
Prenons l’exemple fictif suivant pour comprendre la suite des opérations, et cherchons à calculer la clé d’une femme née en 1969 dans le Maine-et-Loire, son NIR est donc : $2690549588157$.
Si nous devons procéder avec les outils du collège, et beaucoup de courage, nous commençons par poser la division que nous pouvons écrire :
$2690549588157=97\times 27737624620+17$. La clé est alors :
$CC= 97-17=80$.
Au lycée, un élève biberonné de nouvelles technologie se précipite sur sa calculatrice et tape : $2690549588157 \div 97$
Sur la Texas Instrument TI-83 Premium CE, un modèle puissant, il obtient : $2,773762462\times 10^{10}$. Sibyllin résultat dont on ne sait trop quoi dire. L’idée serait de garder la partie entière, de la multiplier par $97$ et de soustraire au nombre de départ. Sauf que les capacités d’affichage de la machine sont de dix chiffres seulement, la Numworks rencontre le même problème, mais elle a l’honnêteté de répondre que c’est une approximation, et la partie entière nous est inaccessible.
Alors retroussons-nous les manches, va falloir mettre les mains dans cambouis. Avec les notations du paragraphe précédent, nous réécrivons le NIR sous la forme suivante :
$$S\times 10^{12}+AA\times 10^{10}+MM\times 10^{8}+II_{D}\times 10^{6}+III_{C}\times 10^{3}+PPP$$
Et nous utilisons l’arithmétique modulaire en remarquant que : $10^{2}\equiv 3 \left[ 97\right]$ (une manière compliquée, mais fonctionnelle, de dire que : $100=1 \times 97 + 3$).
De là nous avons :
$$10^{12}=\left(10^{2} \right)^{6}\equiv 3^{6}\left[ 97\right] \equiv 50\left[ 97\right]$$,
car $3^{6} = 729 = 7 \times 97 + 50$.
De même :
$$10^{10} \equiv 49\left[ 97\right]$$
$$10^{8} \equiv 81\left[ 97\right]$$
$$10^{6} \equiv 27\left[ 97\right]$$
$$10^{3} \equiv 30\left[ 97\right]$$
On obtient donc :
$$NIR \equiv 50\times S + 49 \times AA+ 81 \times MM + 27 \times II_{D} + 30 \times III_{C} + R~[97]$$
Donc dans notre cas fictif d’une femme née en 1969 dans le Maine-et-Loire, cela donne :
$$\begin{align*}
S &= 2 \\
AA &= 69 \\
MM &= 05 \\
II_{D} & = 49 \\
III_{C} & = 588 \\
R & = 157 \\
\end{align*}$$
Nous avons alors :
$$\begin{align*}
50\times S & = 100 \equiv 3 \left[ 97\right] \\
49 \times AA & = 3381 \equiv 83 \left[ 97\right] \\
81\times MM & = 405 \equiv 17 \left[ 97\right] \\
27\times II_{D} & = 1323 \equiv 62 \left[ 97\right] \\
30\times III_{C} & = 17640 \equiv 83 \left[ 97\right] \\
R & = 157 \equiv 60 \left[ 97\right] \\
\end{align*}$$
En conséquence :
$$50\times S + 49 \times AA+ 81 \times MM + 27 \times II_{D} + 30 \times III_{C} + R = 308 \equiv 17~[97]$$
Et pour finir :
$$CC= 97-17=80$$.
C.Q.F.D.
Modulo 97
Cette méthode de calcul de la clé n’est pas réservée au numéro de Sécurité Sociale. Voyez un relevé d’identité bancaire, l’IBAN – pour International Bank Account Number – qui y figure contient lui aussi un système de contrôle :
Cette clé est, comme précédemment, calculé à partir de $97$. Pourquoi cette valeur ? Et pas $99$ ?
Après la lecture du chapitre sur le crible d’Ératosthène vous avez une ébauche de réponse : $97$ est le plus grand nombre premier à deux chiffres. Ni trop, ni trop peu compte tenu de ce qu’on lui demande. À savoir, être facilement calculable et fournir le plus grand nombre de clés possibles – entre $00$ et $199$. Mais il faut avoir à l’esprit le type d’erreurs le plus courant susceptible d’apparaître lors de la saisie du NIR :
• Omission d’un chiffre.
• Erreur sur un chiffre lors de la saisie.
• Permutation de deux chiffres.
Si la première est facile à détecter, les deux autres sont les plus courantes. Prenons prenons pour simplifier, $210$ comme NIR et $10$ comme base de calcul, $10$ sera la clé. Si l’opérateur se trompe et entre $120$, l’erreur ne se verra pas. Essayons avec les mêmes valeurs sauf que nous choisissons $11$ au lieu de $10$. Constatons que $210=11\times 19+1$, la clé est donc $9$. Mais pour $120$, la clé est $1$.
Le choix du plus grand nombre à deux chiffres comme base signale le plus d’erreurs possible, et le fait qu’il soit premier permet de les corriger de manière automatique, sans aucune ambiguïté ou presque, par exhaustion.