3. Générateurs d'un groupe particulier

Générateurs d'un groupe particulier

  • M

    Bonjour à tous.
    Un petit problème :
    Soit p=25343.
    On cherche un générateur du groupe multiplicatif (Z/pZ)*.
    Pour cela, on utilise la méthode suivante que vous devez justifier.

    1. On choisit au hasard un élément x de (Z/pZ)*, différent de 1 et de -1.
    2. On calcule x12671x^{12671}x12671 (dans(Z/pZ)*, c'est-à-dire modulo p).
    3. Ou bien le résultat vaut 1, ou bien il vaut -1.
    4. Si le résultat est -1, alors x est un générateur de (Z/pZ)*.
    5. Si le résultat est 1, alors -x est un générateur.
    M 1 réponse
  • M

    Personne ?
    Alors un "petit" coup de pouce : p est premier.
    Si ça ne suffit pas, je donnerai un "gros" coup de pouce ...

    O 1 réponse
  • O

    Le deuxième coup de pouce : p−1=2×12671p-1 = 2\times12671p−1=2×12671 et 12671 est premier.
    Lagrange : y=x12671y = x^{12671}y=x12671 vérifie y2=1y^2 = 1y2=1. Donc (corps) y=±1y = \pm1y=±1.

    etc.

    M 1 réponse
  • M

    Bonjour Ostap_Bender
    Tout-à-fait.
    Restent les questions 4 et 5.

    O 1 réponse
  • O

    Bon ça va être encore pour mézigue pâteux:
    4) et 5) sont aussi évidents.
    4) soit k l'ordre de x dans (zp)∗(\mathbb z_p)^*(zp​)∗.
    k divise p−1=2×12671p-1 = 2\times12671p−1=2×12671.
    k = 1, 2, 12671 sont impossible puisque y=x12671=−1y = x^{12671} = -1y=x12671=−1.
    D'après le principe de Sherlock Holmes, l'ordre est donc 25342. CQFD.
    5) Méthode du jaguar casqué: On applique le 4) à −x-x−x.

    amicalement.

    O 1 réponse
  • O

    Beurk !

    1. est faux : x = -1, k= 2.
    O 1 réponse
  • O

    Ah, oui mais x=-1 est exclus dans le 1. Fin du mode beurk!

    Bon, 2 n'est pas générateur, un tableur fait le job en écrivant 12671 en base 2.
    $\begin{array}{rr} \ k & 2^k\ \ \hline\ \ 1 & 2\ \ 2 &4\ \ 4 &16\ \ 8 & 256\ \ 16 &14850\ \ 32 & 13057\ \ 64 & 2888\ \ 128 & 2697\ \ 256& 368\ \ 512 &8709\ \ 1024 &20425\ \ 2048 & 9502\ \ 4096 & 16238\ \ 8192 & 4072\ \ 12288& 1249\ \ 12544& 3458\ \ 12608& 1562\ \ 12609&3124\ \ 12611 &12496\ \ 12615 & 22535\ \ 12623 & 16099\ \ 12639& 9631\ \ 12671& 1 \ \end{array}$
    Donc -2 est générateur.

    M 1 réponse
  • M

    Excuse mon esprit obtus et ne te moque pas : pourquoi ce sort particulier réservé à 2 ?

    O 1 réponse
  • O

    Bah, ta méthode te permet de gagner à tous les coups. Autant prendre le premier venu. Tiens, c'est 2 !
    Tu veux 5 ?
    $\begin{array}{rr} k & 5^k\ \hline\ 1 & 5\ 2 &25\ 4 &625\ 8 & 10480\ 16 &19181\ 32 & 6430\ 64 & 10467\128 & 300\ 256& 13971\ 512 &22398\ 1024 &5719\ 2048 & 14491\ 4096 & 22326\ 8192 & 4152\ 12288& 18201\ 12544& 19852\ 12608& 3627\ 12609&18135\ 12611 &22544\ 12615 & 24635\ 12623 & 5659\ 12639& 1210\ 12671& 25342 \end{array}$

    Donc 5 est générateur.

    M 1 réponse
  • M

    Ah, c'était juste un exemple ...
    En fait, "ma" méthode fonctionne à chaque fois que p est premier (nombre premier sûr) et que q = (p-1)/2 est également premier (nombre premier de Sophie Germain).
    Le choix que j'avais fait de 25343 et de 12671 ne s'imposait pas.

    Merci pour la 5) : je n'y avais même pas pensé (l'age sans doute ...). La solution que j'avais trouvée est autrement plus alambiquée.
    Mais comme on dit : pourquoi faire simple quand on peut faire compliqué ?

Se connecter pour répondre