- Introduction
- Les nombres premiers peuvent être expliqués simplement, mais recèlent une complexité considérable.
- Ils sont utilisés dans de nombreux domaines, notamment des concepts mathématiques, des visualisations intéressantes et la cryptographie.
- J'ai décidé de relever le défi de les générer via du code.
- Défi
- Générer des nombres premiers utilisables par l'algorithme RSA.
- La taille de clé RSA actuellement adaptée est de 2048 bits, donc 2 nombres premiers de 1024 bits sont nécessaires.
- Contraintes :
- Écrire le code depuis le départ (sans dépendances externes)
- N'utiliser que le CPU AMD Ryzen 7 du portable et 16 Go de RAM
- Générer des nombres premiers dans un délai « raisonnable »
- Choix du langage : Rust
- Génération de nombres premiers 16 bits
- Utilisation d'un générateur pseudo-aléatoire via
/dev/urandom pour créer des nombres aléatoires
- Utilisation d'une méthode de test de primalité simple : la division d'essai (Trial Division)
- Un nombre premier 16 bits peut être généré en moyenne en 40 ms
- Génération de nombres premiers 64 bits
- Implémentation d'un algorithme de division d'essai optimisé
- Vérification des nombres de la forme 6k±1 uniquement
- Génération préalable d'une liste de petits nombres premiers pour filtrer rapidement les nombres facilement divisibles
- Environ 6 secondes après optimisation
- Les algorithmes déterministes atteignent leurs limites pour les plus grands nombres
- Test de primalité probabiliste
- Utilisation du petit théorème de Fermat (Fermat's Little Theorem)
- Problème : un nombre composé peut aussi satisfaire la condition (pseudoprimes)
- Test de primalité de Miller-Rabin
- Version probabiliste améliorée du test de Fermat
- Il n'existe aucun composé qui devienne pseudoprime pour toutes les bases
- Le taux d'erreur est très faible, ce qui le rend exploitable en pratique
- Génération de nombres premiers 128 bits
- Possibilité de générer rapidement avec le test de Miller-Rabin (en moyenne 0,03 s)
- En raison de la limite du type u128, l'extension à 1024 bits est difficile
- Implémentation de BigInt pour 1024 bits
- Amélioration progressive à travers plusieurs tentatives
- Tentative 1 : stocker chaque chiffre du nombre dans un tableau
- Tentative 2 : stocker le nombre sous forme binaire
- Tentative 3 : stocker le nombre par blocs d'octets
- Tentative 4 : stocker le nombre par blocs u64
- Tentative 5 : optimisation des algorithmes d'opérations arithmétiques
- Optimisation du test Miller-Rabin et de l'ensemble de la logique
- Traitement parallèle via le multithreading
- Résultat final
- Génération d'un nombre premier 1024 bits en environ 40 ms (8 ms ~ 800 ms)
- Grâce au traitement parallèle, le temps moyen est de 0,04 s
Opinion de GN⁺
- Le processus d'amélioration progressive par itérations et échecs était impressionnant
- Partie d'une implémentation simple, puis a appliqué de nouvelles idées et optimisé à chaque étape
- Malgré les échecs, il n'a pas abandonné, a identifié la cause du problème et recherché des solutions
- Malgré une connaissance mathématique limitée, l'auteur a cherché des ressources, compris et appliqué les concepts nécessaires
- Apprentissage de concepts mathématiques requis tels que le petit théorème de Fermat et le test de primalité de Miller-Rabin
- Il a compris et mis en œuvre des contenus difficiles à un niveau opérationnel
- L'implémentation d'un BigInt personnalisé pour surmonter les limites des types entiers à longueur fixe était remarquable
- Plutôt que d'utiliser simplement une bibliothèque existante, il a compris le fonctionnement interne et effectué des optimisations
- Les améliorations progressives issues d'idées variées sont particulièrement marquantes
- La manière dont le traitement parallèle avec multithreading a amélioré fortement les performances était intéressante
- Il a bien identifié et exploité la nature du problème avec des calculs indépendants
- Il n'a pas simplement visé la vitesse brute, mais adopté une approche efficace tenant compte des caractéristiques du problème
- Bien que le niveau de sécurité cryptographique ne soit pas celui d'une solution de production, cela reste un projet très significatif d'un point de vue pédagogique et exploratoire
- Il s'agit d'un défi où la curiosité et l'esprit de défi de l'auteur se démarquent davantage que l'utilisation pratique
- Les insights et l'expérience acquis au cours du processus devraient beaucoup aider à sa progression future
1 commentaires
Avis de Hacker News
En lien avec cela, certaines crypto-monnaies utilisent des éléments liés à la recherche de grands nombres premiers dans la fonction de preuve de travail. Il y a environ huit ans, on pouvait gagner beaucoup d’argent avec une implémentation très rapide de test de primalité. L’auteur a été, à une époque, le développeur et le mainteneur d’un logiciel de minage pour Riecoin.
Cet article passe sous silence la multiplication de Montgomery, l’une des meilleures optimisations pour un test de primalité rapide. C’est pourtant la base d’une implémentation pratique et rapide de l’exponentiation modulaire.
La CGBN publiée par Niall Emmart est une bibliothèque GPU bigint incroyablement rapide. C’est encore, à ma connaissance, l’implémentation de batch modexp la plus rapide.
Python inclut une modexp assez bonne qui calcule pow(x, y, m) → x^y % m. Cela permet d’implémenter facilement les tests de primalité de Fermat ou Miller-Rabin.
Au départ, la notion de test de primalité probabiliste me semblait étrange et j’ai essayé de trouver un algorithme déterministe capable de traiter des nombres gigantesques, mais APR-CL et ECPP sont trop complexes mathématiquement pour que je puisse les comprendre. Je me suis rendu compte que des algorithmes probabilistes sont utilisés dans presque tous les cas, y compris RSA.
Rendre Miller-Rabin déterministe sur une plage maximale donnée est trivial : il suffit de choisir des bases prouvées qui éliminent tous les pseudoprimes pour cette plage.
La multiplication de grands nombres peut être simplifiée avec une seule ligne d’assembleur inline. J’aurais aimé que le langage C inclue le concept de multiplication étendue. Le support matériel existe partout.
Le test de Fermat suffisait, car l’algorithme ne fonctionne pas si le nombre n’est pas réellement premier. Mais je ne sais pas s’il est possible de démontrer qu’il n’existe pas de valeurs de P/Q composées permettant de chiffrer/déchiffrer avec succès des messages.
Je suis curieux de savoir combien de temps le projet a duré. L’auteur a implémenté Karatsuba, Toom-Cook, la FFT complexe, la NTT et Schönhage–Strassen. Il recommande le livre de Silverman : A Friendly Introduction to Number Theory.
Lorsqu’on écrit son propre code de multiplication de grands nombres, on ressent à quel point il est difficile de traduire la présentation de haut niveau d’un article mathématique en opérations concrètes. Il y a un léger souci dans la partie portant sur la base.
La dernière optimisation consistant à ajouter 2 au lieu de générer un nouveau nombre compromet légèrement la sécurité, car les nombres premiers ne sont pas uniformément répartis ; cela introduit un biais vers les nombres premiers qui suivent immédiatement un grand écart entre deux nombres premiers.
Il y a une petite erreur dans l’explication du petit théorème de Fermat : on dit que a^(p-1) est divisible par p, alors c’est en fait a^(p-1) - 1 qui doit être divisible par p. En termes d’arithmétique modulaire, la formulation est correcte.