Arrel primitiva

En teoria de nombres, el nombre enter $a$ és una arrel primitiva mòdul n si pertany a l'exponent $\varphi (n)\text{ mod }n$, és a dir, si $\varphi (n)$ és l'exponent no negatiu més petit que fa $a^{\varphi (n)}\equiv 1\text{ mod }n$, on $\varphi$ és la funció Fi d'Euler. 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 $(\mathbb{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

• 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 arrel primitiva mòdul 2 i 3 ho és mòdul 4.
• En canvi, si n és $2^k$, amb k > 2, el grup $(\mathbb{Z}/(n){)}^{\ast }$ ja no és cíclic, com resulta immediatament de la congruència $(2n+1{)}^2\equiv 1\text{ mod }8$. En efecte, com que $2<\varphi (8)<\varphi (16)<\varphi \left(2^k\right)<\dots$, é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}/(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 $(\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 $p^{4/\sqrt{e}}$, i si es demostra que la hipòtesi generalitzada de Riemann és certa, aquest límit superior es podria millorar a un valor de $2(\log p{)}^2$.

Bibliografia

• Plantilla:Ref-llibre
• Plantilla:Ref-llibre
• Plantilla:Ref-llibre