WikiMath

---

Objectif

Comme on l'a précédemment évoqué, nous devons trouver des problèmes difficiles d'arithmétique sur lesquels fonder notre protocole de sécurité. La plupart des approches actuelles de sécurité se ramènent au problème de retrouver les facteurs premiers d'un grand entier : depuis l'Antiquité, on cherche à le faire efficacement, et aucune solution n'a jusqu'à présent été trouvée.

On doit donc pouvoir trouver deux grands nombres premiers originaux, et faire leur produit. Notre méthode sera d'autant plus sûre qu'il sera difficile de retrouver les facteurs premiers de ce produit.

Obtention de grands nombres premiers

Le crible d'Eratosthène

Pour obtenir une liste de nombres premiers inférieurs à $N$, on peut procéder comme suit :

• Créer la liste des entiers de 2 à $N$,
• Supprimer, dans cette liste, les multiples de 2, puis les multiples du nombre suivant restant dans la liste (3), puis les multiples du nombre suivant dans la liste (5).
• Arrêter à $N/2$.

On vous demande :

• De comprendre pourquoi, ce faisant, on obtient bien la liste des nombres premiers inférieurs à $N$.
• De comprendre pourquoi on s'arrête à $N/2$.
• D'implémenter cela sur la pyboard.
• De réfléchir s'il s'agit là d'une bonne méthode pour obtenir de grands nombres premiers dans le cadre de l'internet des objets, voire en sécurité informatique tout court.

Un théorème de Fermat

Petit théorème de Fermat...

Si $n$ est premier, alors $n$ divise $a^n-a, a>1$

En d'autres termes, $a^n \equiv a [n].$

L'application aux tests de primalité

Pour obtenir un grand nombre premier, l'idée est de tirer un grand nombre de chiffres, d'en constituer un nombre par concaténation, puis de tester si ce nombre est premier.

Le problème avec le théorème de Fermat, c'est que l'implication est dans le mauvais sens : on voudrait quelque chose de la forme "si telle propriété, alors le nombre est premier", comme par exemple dans le théorème de Wilson. Cependant :

• il est difficile d'être plus efficace que Fermat.
• Si la réciproque est fausse en général, elle est concrètement très souvent vrai, et on peut s'en servir comme base d'une méthode probabiliste de test de primalité : quelque chose qui, quand elle dit que le nombre n'est pas premier, ne se trompe jamais (sens prouvé du théorème de Fermat), et quand elle dit que le nombre est premier, a un risque très réduit de se tromper.

On vous demande d'implémenter, dans le capteur, un premier test de primalité probabiliste basé sur Fermat. On pourra :

1. Commencer par faire quelques tests simples : un nombre à au moins deux chiffres, et se terminant par 0,2,4,5,6,8, par exemple, n'est pas premier.
2. Intégrer ensuite le test de $a^n \equiv a [n]$, pour voir si le nombre a une chance d'être premier.

Miller-Rabin

Miller-Rabin est, en quelque sorte, un raffinement de ce qui précède. Il s'agit à nouveau d'un test probabiliste de primalité, mais pour lequel le risque de se tromper n'arrive jamais en pratique. Ce test est très efficace pour mesurer la primalité de grands entiers.

Son explication en détail dépasse le cadre de ce cours. On vous demande juste d'en faire une implémentation dans votre bibliothèque pour le pyboard, en reprenant le code trouvé ici. On pourra vérifier, dans une console python classique, que l'on produit bien des nombres premiers, à l'aide de la fonction isprime de numpy.