Re: Modulo tout retourné dans les clefs

[Supersedes pour corriger une erreur, j'espère que c'est la seule]

Bonjour,

Afin de répondre correctement et sans à priori, j'ai fait un petit
programme en python pour évaluer l'efficacité des différents nombres
pris comme modulos. Pour ce programme j'ai fait quelques hypothèses
simplificatrices, qui peuvent avoir influé sur les résultats. Je suis
preneur de tous commentaires à ce propos.

Mais j'ai été surpris !

Le 28/08/2021 11:42, Benoit me répondait :

>

2. Pourquoi ne pas avoir pris un nombre premier de trois chiffres, voire
9973 ?

>
Ça c'est pour n'avoir à ajouter que deux chiffres au code plutôt que
trois ou quatre. Je pense que 97 (le plus grand nombre premier à
deux chiffres) est le meilleur compromis entre l'économie de place
et la sécurité.

Première surprise : ce n'est pas le meilleur compromis.
Deuxième surprise : le meilleur compromis n'est pas un nombre premier.

À ce propos, si je passe le nombre premier de deux chiffres à trois,
est-ce que je suis assurément dix fois plus sûr ?

Troisième surprise : non, ce n'est pas dix fois plus sûr.


Tout d'abord mes hypothèses simplificatrices. J'ai supposé que les 13
chiffres du code INSEE avaient tous la même probabilité, indépendamment
du fait que, par exemple, le premier chiffre est le plus souvent un 1
ou un 2, plus rarement un 3, 4, 7 ou 8, et jamais un autre chiffre.
Idem pour les 4e et 5e chiffres qui sont le plus souvent entre 01 et 12.
Par ailleurs j'ai supposé aussi pour simplifier que le code de vérification
était forcément correct, les erreurs possibles étant sur les 13 premiers
chiffres.

Cela étant posé, j'ai voulu déterminer les risques qu'une erreur sur un
ou deux chiffres passe inaperçue en comptant le nombre de paires de codes
qui donnent la même clé de contrôle lorsque les deux codes de la paire
ne diffèrent que d'un ou deux chiffres.

1er cas : un seul chiffre est erroné.

Ce cas est très facile à traiter. Si le modulo est un nombre premier, ou
même un nombre non premier mais non divisible par 2 ou 5, et qu'il est
plus grand que 10, alors modifier un seul chiffre revient à ajouter ou
retirer un nombre qui ne sera jamais un multiple de ce modulo. Dans ce
cas, la clé de contrôle suffira toujours à détecter l'erreur.

2e cas : deux chiffres sont erronés.

Voici un exemple d'erreur possible : ajouter 1 à un chiffre du code INSEE
(par exemple le passer de 1 à 2 ou de 5 à 6), et simultanément ajouter 7
au chiffre qui se trouve cinq rangs plus loin (par exemple le passer de 0
à 7 ou de 2 à 9). Ceci est possible parce que 100007 est un multiple de
97 (c'est 1031 fois 97). Cette erreur peut concerner 8 paires de chiffres
d'un nombre de 13 chiffres. Par ailleurs, elle peut concerner 9 valeurs
du premier chiffre (de 0 à 8) et 3 valeurs de l'autre chiffre (de 0 à 2).
L'erreur associée au nombre 100007 doit donc être comptée 216 fois car
8×9×3 = 216.

Le plus petit multiple de 97 concerné est 97 lui-même (+100 -3) compté 693
fois. Le plus grand multiple de 97 est 5 999 999 999 991 (+6.10^12 -9)
compté 4 fois. Au total, pour 97, le nombre de paires de codes donannt la
même clé s'élève à 2798. Est-ce le meilleur nombre à deux chiffres ? Non !
Parmi tous les nombres à deux chiffres (en excluant les multiples de 2 ou
de 5), il en existe un et un seul qui fait mieux que 97, et il s'agit de
93, alors seulement 2167 paires de clés indiscernables.

Peut-on faire mieux avec une clé à trois chiffres ? Oui ! Est-ce que le plus
grand nombre premier de trois chiffres (997) fait dix fois mieux que 97 ?
Pas du tout ! Il ne fait même pas trois fois mieux : 1083. Est-ce qu'on peut
quand même faire beaucoup mieux ? Oui ! Jugez plutôt. 993 fait déjà bien mieux
avec 270. 991 et 989 font encore mieux avec 90 et 81. Mais 987 fait beaucoup
plus que ça, et même infiniment mieux, avec 0 !

Eh oui, si on calculait un code modulo 987 au lieu de modulo 97, aucune erreur
sur seulement 2 chiffres ne serait indétectable. Et 987 n'est pas le seul
nombre à trois chiffres qui le permette, le plus petit est 279.


Bon, mon message est déjà très long, mais si certains sont intéressés je peux
publier mon programme ainsi que montrer quelques résultats.

Cordialement,
--
Olivier Miakinen