systèmes de numération

Comment le calcul en base 3 surpasse le calcul binaire

Longtemps exploré mais rarement adopté, le calcul de base 3 pourrait   trouver sa place dans la cybersécurité.

Trois, comme le disait Schoolhouse Rock ! aux enfants des années 1970, est un nombre magique. Trois petits cochons ; trois lits, bols et ours pour Boucle d'or ; trois trilogies de Star Wars . Il faut au moins trois pieds pour qu'un tabouret tienne debout tout seul et au moins trois points pour définir un triangle.

Le chiffre 3 suggère également une autre façon de compter. Notre système décimal familier en base 10 utilise les 10 chiffres de zéro à 9. Le binaire, notre lingua franca numérique, représente les nombres en utilisant uniquement les deux chiffres zéro et 1.

Mais les mathématiciens ont depuis longtemps exploré le comptage par trois. Prenons par exemple la base 3, ou ternaire, qui utilise trois chiffres. La convention standard est d'utiliser les chiffres zéro, 1 et 2.

La caractéristique principale de la notation ternaire est son efficacité redoutable. Avec deux bits binaires, vous pouvez représenter quatre nombres. Deux " trits " — chacun avec trois états différents — vous permettent de représenter neuf nombres différents. Un nombre qui nécessite 42 bits n'aurait besoin que de 27 trits.

Si un système à trois états est si efficace, on pourrait imaginer qu'un système à quatre ou cinq états le serait encore plus. Mais plus vous avez besoin de chiffres, plus vous aurez besoin d'espace. Il s'avère que le ternaire est la base d'entiers la plus économique de toutes pour représenter de grands nombres.

Pour comprendre pourquoi, considérons une mesure importante qui calcule l’espace dont un système aura besoin pour stocker des données. Vous commencez par la base du système numérique, appelée la base, et vous la multipliez par le nombre de chiffres nécessaires pour représenter un grand nombre dans cette base. Par exemple, le nombre 100 000 en base 10 nécessite six chiffres. Son " économie de base " est donc de 10 × 6 = 60. En base 2, le même nombre nécessite 17 chiffres, donc son économie de base est de 2 × 17 = 34. Et en base 3, il nécessite 11 chiffres, donc son économie de base est de 3 × 11 = 33. Pour les grands nombres, la base 3 a une économie de base inférieure à celle de toute autre base entière. (Étonnamment, si vous autorisez une base à être n’importe quel nombre réel, et pas seulement un entier, alors la base de calcul la plus efficace est le nombre irrationnel e .)

Outre son efficacité numérique, la base 3 offre des avantages informatiques. Elle suggère un moyen de réduire le nombre de requêtes nécessaires pour répondre à des questions ayant plus de deux réponses possibles. Un système logique binaire ne peut répondre que par " oui " ou " non ". Ainsi, si vous comparez deux nombres, x et y , pour savoir lequel est le plus grand, vous pouvez d'abord demander à l'ordinateur " Est-ce que x est inférieur à y ? " Si la réponse est non, vous devez poser une deuxième requête : " Est-ce que x est égal à y ? " Si la réponse est oui, alors ils sont égaux ; si la réponse est non, alors y est inférieur à x .

Un système utilisant la logique ternaire peut donner l'une des trois réponses. De ce fait, il ne nécessite qu'une seule requête : " x est -il inférieur, égal ou supérieur à y ? "

Malgré ses avantages naturels, le calcul en base 3 n’a jamais décollé, même si de nombreux mathématiciens s’émerveillaient de son efficacité. En 1840, un imprimeur, inventeur, banquier et mathématicien autodidacte anglais du nom de Thomas Fowler a inventé une machine à calcul ternaire pour calculer les valeurs pondérées des impôts et des intérêts. " Après cela, très peu de choses ont été faites pendant des années ", a déclaré Bertrand Cambou , physicien appliqué à la Northern Arizona University.

En 1950, à l’aube de l’ère numérique, un rapport sur la technologie informatique de l’époque, qui s’étalait sur une longue période, suggérait que l’informatique ternaire présentait un avantage. Et à l’automne 1958, des visiteurs en Union soviétique rapportèrent que des ingénieurs avaient développé un ordinateur ternaire appelé Setun, le premier ordinateur moderne basé sur la logique et le matériel ternaires. Les scientifiques soviétiques construisirent des dizaines d’ordinateurs Setun.

Pourquoi le calcul ternaire n'a-t-il pas eu de succès ? La principale raison était la convention. Même si les scientifiques soviétiques construisaient des dispositifs ternaires, le reste du monde se concentrait sur le développement de matériel et de logiciels basés sur des circuits de commutation, fondements du calcul binaire. Le binaire était plus facile à mettre en œuvre.

Mais ces dernières années ont été marquées par des progrès rapides. Des ingénieurs ont proposé des moyens de construire des systèmes logiques ternaires même sur du matériel binaire. Et Cambou, avec le soutien de l’armée américaine, a développé des systèmes de cybersécurité qui utilisent le calcul de base 3. Dans des articles publiés en 2018 et 2019 , lui et ses collaborateurs ont décrit rigoureusement un système ternaire qui pourrait remplacer l’infrastructure à clés publiques existante, qui comprend les clés numériques nécessaires pour crypter ou décrypter les cybercommunications. Le passage des bits aux trits, a-t-il déclaré, réduit considérablement le taux d’erreur, car les états ternaires gèrent mieux les informations erratiques.

Schoolhouse Rock! s’est révélé prophétique. " Le passé, le présent et le futur ", chantaient les personnages du dessin animé. " Le chiffre magique est le trois. "

Auteur: Internet

Info: https://www.quantamagazine.org/, Stephen Ornes, 9 août 2024

[ confrontés ] [ signature rythmique ]