Je m'intéresse à la théorie algorithmique des nombres. Au début, le sujet s'est développé quand les théoriciens des nombres ont dû résoudre de manière effective certains problèmes comme décider si un nombre est premier, trouver les racines rationnelles d'un polynôme ou même calculer son groupe de Galois. Gauss a étudié la factorisation et la primalité tandis que Bouniokowski s'est intéressé au logarithme discret, mais aucun n'a fait de grande avancée. Plus tard, au début du XXe siècle, Pocklington a trouvé une méthode pour décider si un nombre de Fermat est premier, Kraitchik a accéléré considérablement la factorisation et le logarithme discret, tandis que Lehmer a introduit les fractions continues dans un algorithme de factorisation. Après la naissance du premier ordinateur, le domaine s'est développé et des découvertes majeures ont suivi. Parmi les plus célèbres on compte celles de Karatsuba et Strassen qui ont inventé des méthodes de multiplication de polynômes et, respectivement, matrices. Le domaine est à l'intersection des mathématiques et de l'informatique car les objects d'étude sont mathématiques alors que les méthodes sont algorithmiques.

Mais ce n'est pas tout. Quand plusieurs algorithmes ont été créés pour le même but, il est devenu crucial de les comparer. Cela a engendré de nouvelles questions: Quels sont les groupes algébriques sur F_p qui ont approximativement p éléments? Combient de courbes elliptiques sur F_p partagent un même cardinal? Quelle est la probabilité qu'un nombre autour de x, à √x près, ait tous se facteurs premiers inférieurs à y? Cette fois-ci ce sont les objets qui sont informatiques (les algorithmes), alors que les méthodes sont mathematiques (stylo, papier et preuves).

En 1976 Diffie et Hellman ont proposé de verruier une information à l'aide d'un cadenas mathematique. Ces cadenas sont des fonctions bijectives, faciles à fermer, i.e. rapidement calculables dans un sense, et dûres à casser, i.e. difficilement calculables dans l'autre sense (à moins d'avoir un indice secret). Ils ont proposé de chercher des fonctions à sense unique et on suggéré que le couple (exponentiation, logarithme discret) pourrait marcher. En 1978, Rivest, Shamir et Adleman ont proposé le couple (multiplication, factorisation), qui est encore utilisé sur la carte bleu et le portable de votre poche.

Quant à mon sujet spécifique, il s'agit du logarithme discret dans F_pn. La raison c'est l'utilisation de plus en plus importante des couplages (accouplements) de groupes en cryptographie. Un couplage est une application bilinéaire, non dégénérée φ:G₁×G₂ → G₃ avec G₁, G₂ et G₃ groupes abéliens. Un bon couplage doit être facile à calculer et nécessite que le problème du logarithme discret soit dûr dans tous les trois groupes. À présent, les meilleurs couplages utilisent des courbes elliptiques pour G₁ et G₂ et F_pn pour G₃. Ainsi, la sécurité des nouveaux cryptosystèmes dépend de la difficulté du problème du logarithme discret.