Arrel primitiva

En teoria de nombres, el nombre enter ${\displaystyle a}$ és una arrel primitiva mòdul n si pertany a l'exponent ${\displaystyle \phi (n){\text{ mod }}n}$, és a dir, si ${\displaystyle \phi (n)}$ és l'exponent no negatiu més petit que fa ${\displaystyle a^{\phi (n)}\equiv 1{\text{ mod }}n}$, on ${\displaystyle \phi }$ és la funció Fi d'Euler. Des del punt de vista de la teoria de grups, que ${\displaystyle a}$ sigui una arrel primitiva mòdul ${\displaystyle n}$ és el mateix que dir que ${\displaystyle (\mathbb {Z} /(n))^{\ast }}$, el grup multiplicatiu de les unitats de l'anell ℤ/(n), és cíclic i que la classe de ${\displaystyle a}$ n'és un generador.

Existència d'arrels primitives

• Si n és 2 o 4, hom comprova fàcilment, només escrivint-ne la taula, que el grup ${\displaystyle (\mathbb {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 ${\displaystyle 2^{k}}$, amb k > 2, el grup ${\displaystyle (\mathbb {Z} /(n))^{\ast }}$ ja no és cíclic, com resulta immediatament de la congruència ${\displaystyle (2n+1)^{2}\equiv 1{\text{ mod }}8}$. En efecte, com que ${\displaystyle 2<\phi (8)<\phi (16)<\phi \left(2^{k}\right)<\ldots }$, és clar que els grups ${\displaystyle (\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 ${\displaystyle (\mathbb {Z} /(p^{k}))^{\ast }}$ són tots cíclics, per qualsevol valor de k > 0.
• Per a un nombre n qualsevol, si ${\displaystyle 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 ${\displaystyle (\mathbb {Z} /(n))^{\ast }}$ és isomorf al producte directe dels grups ${\displaystyle (\mathbb {Z} /(2^{r}))^{\ast }\times (\mathbb {Z} /(p_{1}^{r_{1}}))^{\ast }\times (\mathbb {Z} /(p_{2}^{r_{2}}))^{\ast }\times \cdots \times (\mathbb {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 ${\displaystyle (\mathbb {Z} /(n))^{\ast }}$ és cíclic si, i només si, el nombre n és d'una d'aquestes quatre formes: 2, 4, p^k o 2p^k. 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

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

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

De fet, 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.

S'ha demostrat que l'arrel primitiva més petita mòdul p és de l'ordre de ${\displaystyle p^{4/{\sqrt {e}}}}$,^[1] i si es demostra que la hipòtesi generalitzada de Riemann és certa, aquest límit superior es podria millorar a un valor de ${\displaystyle 2(\log p)^{2}}$.^[2]

Referències

1. Burgess, D. A. «The distribution of quadratic residues and non-residues». Mathematika, 4, 1957, pàg. 106-112.
2. Bach, Eric «Explicit bounds for primality testing and related problems». Math. Comp., 55, pàg. 355-380.

Bibliografia

• Gauß, Carl Friedrich; Pascual Xufré, Griselda (trad.). Disquisicions aritmètiques (orig. Disquisitiones Arithmeticæ) (en llatí originalment). edició en català. 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.