On cherche tout d'abord à construire des nombres premiers p avec un générateur de (Z/pZ)*.
Un théorème du à Rabin et Miller, affirme que la proportion des entiers a entre 1 et p, tels que pour p-1=2^s t avec t impair, a^t n'est pas égal à 1 et pour tout i entre 0 et s-1, a^(2^i t) distinct de -1, est inférieure ou égale à 1/4. Ainsi si p passe k tests de Rabin-Miller avec succès, il sera dit premier avec une probabilité supérieure ou égale à (1-1/4^k).
Utiliser le programme SGermain.java pour produire de probables nombres premiers de Sophie Germain avec un générateur du groupe multiplicatif. Expliquer pourquoi considérer de tels nombres premiers. On utilisera ensuite la version BigInteger de SGermain pour produire des exemples plus percutants.
En utilisant le programme PasSGermain.java construire des nombres premiers de la forme kp+1 avec un élément d'ordre p. Pourquoi considérer de tels nombres premiers? Utiliser ensuite la version PasSGermain-big.java avec BigInteger.
Ecrire un programme d'échange des clefs.
Utiliser le programme BSGS.java et sa version BigInteger BSGS-big.java qui implémente l'algorithme Baby Steps-Giant Steps pour résoudre des instances du logarithme discret. On pourra commencer par calculer n tel que 3^n=525 modulo 809.