Deutsch English Français Italiano |
<sgtnp9$2n5o$1@cabale.usenet-fr.net> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!.POSTED!not-for-mail From: Olivier Miakinen <om+news@miakinen.net> Newsgroups: fr.sci.maths Subject: =?UTF-8?Q?Re:_Modulo_tout_retourn=c3=a9_dans_les_clefs?= Supersedes: <sgtnfj$2n4e$1@cabale.usenet-fr.net> Date: Fri, 3 Sep 2021 19:59:04 +0200 Organization: There's no cabale Lines: 91 Message-ID: <sgtnp9$2n5o$1@cabale.usenet-fr.net> References: <sgap79$vsa$2@shakotay.alphanet.ch> <sgbruv$2n00$1@cabale.usenet-fr.net> <sgd0df$sch$2@shakotay.alphanet.ch> NNTP-Posting-Host: 220.12.205.77.rev.sfr.net Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8bit X-Trace: cabale.usenet-fr.net 1630691945 89272 77.205.12.220 (3 Sep 2021 17:59:05 GMT) X-Complaints-To: abuse@usenet-fr.net NNTP-Posting-Date: Fri, 3 Sep 2021 17:59:05 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.4 X-Mozilla-News-Host: news://220.12.205.77.rev.sfr.net In-Reply-To: <sgd0df$sch$2@shakotay.alphanet.ch> Bytes: 5500 [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