Démonstrateur du Crible Quadratique

Cryptographie et Crible Quadratique

---

La cryptologie est un art qui remonte à l'Antiquité et se base sur des notions d'arithmétique pour chiffrer ou déchiffrer des messages.
La cryptologie est utilisé dans de nombreux domaines tels que le domaine militaire (renseignement et communication), l'industrie (sécurité du secret industriel), le secteur bancaire...
Bien que déjà utilisée à l'époque de l'Empire Romain, c'est seulement durant le XXème siècle que les techniques les plus importantes, tel que la cryptographie asymétrique, sont apparus.

En cryptographie, on peut distinguer deux catégories de méthodes de chiffrement: Les chiffrements à clé secrète et les chiffrements à clé publique (cryptographie asymétrique).
Les chiffrements à clé secrète (exemple: tout algorithme de chiffrement affine, comme le code César) utilise la même clé pour le chiffrement et le déchiffrement. Le défaut de ces méthodes de chiffrement était qu'ils étaient relativement facile de les casser et nécessitaient un canal de communication sécuriser pour transmettre la clé.
Les chiffrements à clé publique reposent sur la difficulté supposée de certains problèmes mathématiques (exemple: la factorisation pour le déchiffrement) pour lesquels l’opération inverse est simple (exemple: le calcul du produit pour le chiffrement).

Ce site présente et implémente la succession d'algorithmes de factorisation de grands nombres qui ont servi de base pour l'algorithme du crible quadratique, inventé en 1981 par Carl Pomerance.
Le crible quadratique est en pratique le deuxième algorithme de factorisation de grands nombres le plus rapide, juste derrière le crible généralisé sur corps de nombres et est le premier pour les nombres de moins de 100 digits.

Note: Ce site est avant tout un demonstrateur à vocation pédagogique et destiné à illustrer les notions de cours de MT10.
Les performances du site sont limités par les ressources restreintes accordées par le serveur de l'UTC, il n'est donc pas possible de factoriser des nombres extrêmement grands (la limite est de 12~13 digits pour un crible complet) et n'en a pas la vocation.

RETOUR