Bonjour à tou-te-s,
j'ai une question en cryptographie, et je remercie d'emblée toute personne qui prendra le temps de me répondre. Je prends un grand nombre premier p, et ça me donne un corps Z/pZ. Je cherche à trouver un générateur de ce corps.
De ce que j'ai compris, je prends un nombre p premier tel que je connaisse la décomposition de p - 1 en produit de facteurs premiers. J'ai alors PHI(p - 1) générateurs du groupe multiplicatif de Z/pZ. Et en plus, je peux calculer PHI(p - 1) puisque je connais la décomposition de p - 1 en produits de facteurs premiers. Si en particulier je prends p - 1 = 2 * q avec q premier, l'ordre d'un élément du dit groupe est soit 2, soit q, soit p - 1. Dans ce cas, l'algorithme est de prendre un r au hasard dans le groupe multiplicatif, et de tester s'il génère le groupe, ou, pour le dire autrement, si r puissance k avec 1 < k < p - 1 donne toujours un nombre différent de 1.
Mais ça c'est un algorithme probabiliste. Je peux trouver le nombre de k à tester pour avoir une assez grande confiance.
Et donc, les questions:
- Par rapport à cet algorithme, existe t'il un générateur de nombres aléatoires dont deux tirages sont toujours différents (à condition d'en faire moins que p - 1 évidemment)?
- Existe t'il un moyen de trouver un générateur autrement?
- Existe t'il en particulier un algorithme déterministe?
- Bref, pour trouver un générateur, comment fait on en pratique?
Merci beaucoup
Partager