Arrel primitiva

De Viquipèdia
Dreceres ràpides: navegació, cerca

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

El punt de vista de la teoria de grups[modifica | modifica el codi]

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

Existència d'arrels primitives[modifica | modifica el codi]

  • Si n és 2 o 4, hom comprova fàcilment, només escrivint-ne la taula, que el grup (\Z / (n))^{\ast} és cíclic: 1 és una arrel primitiva mòdul 2 i 3 ho és mòdul 4.
  • En canvi, si n és 2^{k}, amb k > 2, el grup (\Z / (n))^{\ast} ja no és cíclic, com resulta immediatament 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 (\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 (\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 (\Z / (n))^{\ast} és isomorf al producte directe dels grups (\Z / (2^{r}))^{\ast} \times (\Z / (p_{1}^{r_1}))^{\ast} \times (\Z / (p_{2}^{r_2}))^{\ast} \times \cdots \times(\Z/(p_{k}^{r_k}))^{\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 mòdul n si, i només si, el nombre n és d'una d'aquestes quatre formes.

Obtenció d'arrels primitives[modifica | modifica el codi]

  • 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 mòdul p (amb p un nombre primer senar) aleshores, o bé a, o bé a + p és una arrel primitiva mòdul p2.
  • Si a és una arrel primitiva mòdul p2 (amb p un nombre primer senar), aleshores a també és una arrel primitiva mòdul pk, per tot k > 1.

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

Però el càlcul de les arrels primitives mòdul p és molt llarg i dificultós i poca cosa més es pot fer a part de cerques exhaustives, per la qual cosa, la importància de les arrels primitives és molt gran en criptografia.

Referències[modifica | modifica el codi]

  • Gauß, Carl Friedrich; Pascual Xufré, Griselda (trad.). Disquisicions aritmètiques (orig. Disquisitiones Arithmeticæ). edició en català (en llatí originalment). Barcelona: Societat Catalana de Matemàtiques (IEC), 1996. 
  • Hardy, G. H.; Wright, E. M.. An Introduction to the Theory of Numbers (en anglès). Oxford: Clarendon Press, 1983. 
  • Ireland, Kenneth; Rosen, Michael. A Classical Introduction to Modern Number Theory (en anglès). Springer-Verlag, 1990 (Graduate Texts in Mathematics). ISBN 9780387973296.