Discussion :

[rmaker]

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:

1. 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)?
2. Existe t'il un moyen de trouver un générateur autrement?
3. Existe t'il en particulier un algorithme déterministe?
4. Bref, pour trouver un générateur, comment fait on en pratique?

Merci beaucoup

[Flodelarab]

Bonjour

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)?

Bien sûr que oui. Tu es en train de donner un ordre à tes éléments. Comme un tirage de boules dans une urne (l'urne se vide au fil des tirages et les répétitions sont impossibles). C'est un arrangement contrairement à la p-liste où la répétition est possible.

Concrètement, si tu tires un nombre dans {1,2,3,4,5} et que tu prends 4,
Le coup d'après tu tires dans {1,2,3,5} et que tu prends 3,
Le coup d'après tu tires dans {1,2,5} et que tu prends 1,
Le coup d'après tu tires dans {2,5} et que tu prends 5,
Le coup d'après tu tires dans {2} et que tu prends 2.
Tu as juste déterminé l'ordre 4-3-1-5-2.

si r puissance k avec 1 < k < p - 1 donne toujours un nombre différent de 1

Euh, pas non, mais bof bof. Le premier "inférieur" a-t-il des raisons d'être strict ? Le second "inférieur" a-t-il le même sens que le premier ?
Si r est générateur, il génère tous les nombres, même le 1. Mais intuitivement, on comprend que c'est le dernier. Car si on re-multiplie par r, on retombe sur r donc r¹.
Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p=13, candidat=11:
11^1 = 11
11^2 = 4
11^3 = 5
11^4 = 3
11^5 = 7
11^6 = 12
11^7 = 2
11^8 = 9
11^9 = 8
11^10 = 10
11^11 = 6
11^12 = 1
11^13 = 11

Existe t'il en particulier un algorithme déterministe?

Je ne crois pas, sinon on ne s'embêterait pas avec des algorithmes probabilistes.

[rmaker]

Merci pour ta réponse! Il y a des choses que je ne comprends pas, cela dit.

Bien sûr que oui. Tu es en train de donner un ordre à tes éléments. Comme un tirage de boules dans une urne (l'urne se vide au fil des tirages et les répétitions sont impossibles). C'est un arrangement contrairement à la p-liste où la répétition est possible.

Concrètement, si tu tires un nombre dans {1,2,3,4,5} et que tu prends 4,
[...]

Je ne suis pas du tout d'accord. Ca marche pour les petits nombres, mais pas en général. Parce que pour implémenter un algorithme qui fasse ça, si p est de l'ordre de ... 2048 bits, disons, ça veut dire que tu stockes l'ensemble des nombres que tu as déjà tiré. Et si c'est possible sur 32 bits (environ 4 milliards d'éléments), tu ne pourras pas stocker tous les numéros que tu as tirés. C'est juste physiquement impossible. C'est à mon avis tout le problème des nombres aléatoires sur les grands nombres.

As tu une solution? Mon objection est elle valide?

Bonjour
Euh, pas non, mais bof bof. Le premier "inférieur" a-t-il des raisons d'être strict ? Le second "inférieur" a-t-il le même sens que le premier ?
Si r est générateur, il génère tous les nombres, même le 1. Mais intuitivement, on comprend que c'est le dernier. [...]

On est bien d'accord, c'est en fait le petit théorème de Fermat. Ca ne sert à rien de vérifier pour 1 car on aura le nombre, et pour p - 1, car le résultat fait forcément un.

Je ne crois pas, sinon on ne s'embêterait pas avec des algorithmes probabilistes.

OK, bon, c'est bon à savoir! Merci beaucoup

[pseudocode]

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.

L'algo c'est trouver un r au hasard qui soit d'ordre p-1 ou d'ordre q.
Parce que si p fait 2048 bits, alors q =(p-1)/2 fait quand même... 2047 bits. C'est très acceptable.

Bref, il s'agit de vérifier que r n'est pas d'ordre 1 et n'est pas d'ordre 2.
r n'est pas d'ordre 1 => trivial: r != 1
r n'est pas d'ordre 2 => il n'y a qu'un seul élément d'ordre 2 (Phi(2)=1). Et comme "(p-1)^2=1 mod p" => r!=p-1

Par exemple, dans Z/11Z (p=11 , p-1=2*5), un élément quelconque entre 2 et 9 génère un sous-groupe d'ordre 5 ou 10.

      |   1^k      2^k      3^k      4^k      5^k      6^k      7^k      8^k      9^k      10^k
-----------------------------------------------------------------------------------------------
k=1   |    1        2        3        4        5        6        7        8        9       10
k=2   |    1        4        9        5        3        3        5        9        4        1
k=3   |    1        8        5        9        4        7        2        6        3       10
k=4   |    1        5        4        3        9        9        3        4        5        1
k=5   |    1       10        1        1        1       10        10       10       1       10
k=6   |    1        9        3        4        5        5        4        3        9        1
k=7   |    1        7        9        5        3        8        6        2        4       10
k=8   |    1        3        5        9        4        4        9        5        3        1
k=9   |    1        6        4        3        9        2        8        7        5       10
k=10  |    1        1        1        1        1        1        1        1        1        1
k=11  |    1        2        3        4        5        6        7        8        9       10
-----------------------------------------------------------------------------------------------
Ordre      1       10        5        5        5       10       10       10        5        2