2
On connait les nombres premiers depuis l’antiquité et bien qu’on sache qu’il en existe une infinité, on ne sait toujours pas déterminer, rapidement, si un grand nombre est premier. C’est le mathématicien Euclide qui a démontré qu’il existe une infinité de nombre premiers, mais on sait que plus on va vers l’infini et plus ils se raréfient, ce qui accroit la difficulté. A titre d’illustration, il existe 25 nombres premiers entre 0 et 100 (25%), il en existe 168 entre 0 et 1000 (17%) et il y en a 1229 entre 0 et 10.000 (12%). Les applications des nombres premiers sont nombreuses, aussi bien en mathématiques qu’en informatique et en particulier en cryptographie.
L’égalité [latex]n = n \times 1[/latex] nous montre que tout entier naturel supérieur à 1 a au moins deux diviseurs : 1 et lui même. Un nombre premier est un entier positif qui n’est divisible que par lui même et par 1 et tous les nombres strictement supérieur à 1, qui ne sont pas premiers, peuvent être écrits comme le produit de nombres premiers, ce qui s’appelle « décomposer en produits de facteurs premiers ». Il faut noter que par convention, et on pourrait l’expliquer de plusieurs façons, le chiffre 1 n’est pas considéré comme étant un nombre premier. Selon la conjecture de Goldbach, on peut aussi dire que tout nombre entier pair supérieur à 3 peut s’écrire comme la somme de deux nombres premiers.
Il existe de nombreuses façons de tester si un nombre est premier, mais, de manière générale, le nombre d’opérations pour tester si un nombre est premier croit exponentiellement avec le nombre de chiffres. La méthode la plus naïve pour rechercher tous les nombres premiers plus petits qu’un entier naturel [latex]n[/latex] donné, est d’utiliser le crible du mathématicien Ératosthène :
- On écrit la liste de tous les nombres jusqu’à [latex]n[/latex]
- On élimine 1
- On souligne 2 et on élimine tous les multiples de 2
- On fait de même avec 3
- On choisit le plus petit nombre non souligné et non éliminé qui est 5
- On élimine tous ses multiples
- On réitère le procédé jusqu’à la partie entière de [latex]\sqrt{n}[/latex]
- Les nombres non éliminés sont les nombres premiers jusqu’à [latex]n[/latex]
Pour appliquer le crible d’Ératosthène, il convient de se remémorer les règles de divisibilité :
- Un nombre est divisible par 2 s’il se termine par un chiffre pair (0, 2, 4, 6, ou 8)
- Un nombre est divisible par 3 si la somme de ses chiffres est divisible par 3 et on peut répéter le procédé sur la somme obtenue
- Un nombre est divisible par 4 si le nombre formé par ses deux derniers chiffres est divisible par 4
- Un nombre est divisible par 5 s’il se termine par un 0 ou 5
- Un nombre est divisible par 6 s’il est divisible par 2 et par 3
- Un nombre est divisible par 7 si le nombre des dizaines moins le double du chiffre des unités est divisible par 7 et on peut répéter le procédé sur la différence obtenue
- Un nombre est divisible par 8 si le nombre formé par ses trois derniers chiffres est divisible par 8
- Un nombre est divisible par 9 si la somme de ses chiffres est divisible par 9 et on peut répéter le procédé sur la somme obtenue
- Un nombre est divisible par 10 s’il se termine par un 0
- Un nombre est divisible par 11 si la somme d’un chiffre sur deux en partant du dernier, moins la somme des autres chiffres est divisible par 11 et on peut répéter le procédé sur la différence obtenue
La factorisation des grands nombres reste aussi un défi pour les calculateurs actuels. Prendre deux grands nombres premiers et les multiplier se fait extrêmement rapidement, mais retrouver les deux nombres premiers à partir du résultat de la multiplication peut devenir un challenge. Les systèmes modernes de cryptage de données seront sûrs tant que la décomposition des grands nombres en facteurs premiers restera difficile. Cependant, les techniques de factorisation progressent rapidement, que ce soit grâce à des algorithmes plus performants ou grâce à des calculateurs plus puissants mis en réseau. L’arrivée de l’informatique quantique, fusion des sciences de l’information et de la physique quantique, commence à fragiliser la cryptographie moderne.
Le qubit (quantum + bit) ou qbit représente la plus petite unité de stockage d’information quantique. Il se compose d’une superposition de deux états de base nommés, par convention, [latex]|0\rangle[/latex] et [latex]|1\rangle[/latex] et prononcés ket 0 et ket 1. Contrairement à un bit qui vaut toujours 0 ou 1, un qubit est généralement dans une superposition de l’état 0 et 1 qui se décrit par une combinaison linéaire des deux états : [latex]\alpha \times |0\rangle + \beta \times |1\rangle[/latex]. Les coefficients [latex]\alpha[/latex] et [latex]\beta[/latex] sont des nombres complexes vérifiant la relation de norme [latex]|\alpha|^2 + |\beta|^2 = 1[/latex]. Lors de la mesure de la valeur du qubit, les seules réponses pouvant être obtenues sont [latex]|0\rangle[/latex] ou [latex]|1\rangle[/latex] avec les probabilités [latex]|\alpha|^2[/latex] et [latex]|\beta|^2[/latex], en sachant qu’après sa mesure, le qubit se trouve projeté dans l’état mesuré. Avec 4 bits, un ordinateur classique peut traiter un état parmi [latex]2^4[/latex], soit 16 états différents : 0000, 0001, 0010, 0011, …, 1111. Dans un ordinateur quantique, les quatre qubits pourraient être dans une superposition de tous ces états. L’avantage de l’ordinateur quantique est de pouvoir traiter simultanément les 16 états. Des ordinateurs quantiques équipés de processeurs de [latex]n[/latex] qubits permettent donc de gérer [latex]2^n[/latex] informations différentes simultanément. Ils calculent donc [latex]n[/latex] fois plus vite qu’un ordinateur classique puisqu’ils sont capables d’effectuer ces calculs en parallèle.
Alors que l’informatique quantique risque de mettre en péril la solidité des systèmes de cryptage utilisés actuellement, elle peut aussi accueillir de nouveaux algorithmes et apporter une réponse à l’assurance dans la transmission des données, car il n’est pas possible de mesurer les amplitudes [latex]\alpha[/latex] et [latex]\beta[/latex] du qubit unique initial, tout en préservant son état.
