Arrel primitiva

De Viquipèdia

Hom diu que el nombre enter a és una arrel primitiva (mod n) si pertany a l'exponent φ(n) (mod n), és a dir, si φ(n) és l'exponent no negatiu més petit que fa a^{\phi(n)} \equiv 1 \pmod{n} (φ és la funció Fi d'Euler).

Taula de continguts

[edita] El punt de vista de la Teoria de Grups

Des del punt de vista de la teoria de grups, que a sigui una arrel primitiva (mod n) és el mateix que dir que \mathbb{Z} / (n)^{\ast}, el grup multiplicatiu de les unitats de l'anell \mathbb{Z} / (n), és cíclic i que la classe a n'és un generador.

[edita] Existència d'arrels primitives

  • Si n és 2 o 4, hom comprova fàcilment, només escrivint-ne la taula, que el grup \mathbb{Z} / (n)^{\ast} és cíclic: 1 és una arel primitiva (mod 2) i 3 ho és (mod 4)
  • En canvi, si n és 2k, amb k > 2, el grup \mathbb{Z} / (n)^{\ast} ja no és cíclic, com resulta inmediatament de la congruència (2n + 1)^{2} \equiv 1 \pmod{8}. En efecte, com que 2 < \phi(8) < \phi(16) < \phi\left(2^{k}\right) < \ldots, és clar que els grups \mathbb{Z} / (n)^{\ast} no són cíclics, perquè 2 és el màxim dels ordres dels elements d'aquests grups.
  • Per a nombres primers senars, p, els grups \mathbb{Z} / (p^k)^{\ast} són tots cíclics, per qualsevol valor de k > 0.
  • Per a un nombre n qualsevol, si n = 2^{r} p_{1}^{r_1} p_{2}^{r_2} \cdots p_{k}^{r_k} n'és la descomposició en factors primers, el grup \mathbb{Z} / (n)^{\ast} és isomorf al producte directe dels grups \mathbb{Z} / \left(2^{r}\right)^{\ast} \times \mathbb{Z} / \left(p_{1}^{r_1}\right)^{\ast} \times \mathbb{Z} / \left(p_{2}^{r_2}\right)^{\ast} \times \cdots \times\mathbb{Z} / \left(p_{k}^{r_k}\right)^{\ast}. Tenint en compte quins d'aquests factors són grups cíclics i el fet que el producte és cíclic si, i només si, els factors ho són i els ordres respectius són coprimers, resulta que \mathbb{Z} / (n)^{\ast} és cíclic si, i només si, el nombre n és d'una d'aquestes quatre formes 2, 4, pk o 2pk. En conseqüència, hi ha arrels primitives (mod n) si, i només si, el nombre n és d'una d'aquestes quatre formes 2, 4, pk o 2pk.

[edita] Obtenció d'arrels primitives

  • Pel mòdul 2 només hi ha l'arrel primitiva 1 i, pel mòdul 4, només 3 ho és.
  • Si a és una arrel primitiva (mod p) (p primer senar) aleshores, o bé a, o bé a + p és una arrel primitiva (mod p2).
  • Si a és una arrel primitiva (mod p2) (p primer senar) aleshores, a també és una arrel primitiva (mod pk), per tot k > 1.

Per tant, calcular arrels primitives (mod pk), k > 1 és ben senzill: a partir de les arrels primitives (mod p). es calculen les arrels primitives (mod p2) i, d'aquí, les de (mod pk), per qualsevol k > 1.

Però el càlcul de les arrels primitives (mod p) és molt llarg i dificultós i poca cosa més es pot fer apart de cerques exhaustives, per la qual cosa, l'importància de les arrels primitives és molt gran en Criptografia.

[edita] Referències

  • Gauß Carl F. Disquisicions aritmètiques. (Disquisitiones Arithmeticæ Pascual Xufré, Griselda, (trad.) 1996) Societat Catalana de Matemàtiques (I. E. C.) Barcelona
  • Hardy G. H. & Wright E. M. (1983) An Introduction to the Theory of Numbers. Clarendon Press - Oxford (en anglès)
  • Ireland Kenneth & Rosen Michael (1990) A Classical Introduction to Modern Number Theory. Springer - Verlag