Raíz primitiva módulo n

Dado un número natural n, decimos que a es una raíz primitiva módulo n (abreviado mod n), si a genera como grupo a ${\mathbb{Z}}_n^{*}$, es decir, si $\mathrm{\forall }b\in {\mathbb{Z}}_n^{*}$ existe $k\in \mathbb{Z}$ tal que $a^k\equiv b(\mathrm{mod}n)$. Aquí ${\mathbb{Z}}_n^{*}$ denota los elementos invertibles módulo n.

Dado que el orden de ${\mathbb{Z}}_n^{*}$ es $\phi (n)$, siendo φ la función phi de Euler, una raíz primitiva es un elemento con ese orden.

Ejemplos

Si $n=5$ entonces 3 es raíz primitiva módulo 5:

$\begin{array}{c}{3}^1=3\\ 3^2=9\equiv 4(\mathrm{mod}5)\\ 3^3=3^2\times 3\equiv 4\times 3=12\equiv 2(\mathrm{mod}5)\\ 3^4=3^3\times 3\equiv 2\times 3=6\equiv 1(\mathrm{mod}5)\end{array}$

Si observamos bien, todo resto coprimo con 5 (1, 2, 3 y 4) es congruente con $3^k$ módulo 5 para algún $k\in \mathbb{Z}$. De hecho (y esto ocurre para toda raíz primitiva) el $k$ puede elegirse entre 1 y $4=\phi (5)$.

Para $n=14$, tenemos que 5 es raíz primitiva:

$\begin{array}{c}{5}^0=1\\ 5^1=5\\ 5^2=25\equiv 11(\mathrm{mod}14)\\ 5^3=5^2\times 5\equiv 11\times 5=55\equiv 13(\mathrm{mod}14)\\ 5^4=5^3\times 5\equiv 13\times 5=65\equiv 9(\mathrm{mod}14)\\ 5^5=5^4\times 5\equiv 9\times 5=45\equiv 3(\mathrm{mod}14)\end{array}$

${\mathbb{Z}}_{14}^{*}=\{1,3,5,9,11,13\}$, o sea que obtenemos todos los elementos de ${\mathbb{Z}}_{14}^{*}$ como potencias de 5.

Existencia de raíces primitivas

Se puede demostrar que si p es un número primo, entonces existe alguna raíz primitiva módulo p (para la demostración se utiliza el hecho de que ${\mathbb{Z}}_p$ es un cuerpo cuando p es primo). Fijada b una raíz primitiva módulo p, cualquier entero a que no sea divisible entre p puede escribirse como $a=b^r(\mathrm{mod}p)$ para un único $r\in \{1,2,...,p-1\}$.

También puede demostrarse que si $n=p^k$ con p un primo impar (mayor que 2), entonces existen raíces primitivas módulo n, así como también existen raíces primitivas módulo n cuando n=1, $n=2p^k$, siendo p, como antes, un primo impar. Éstos, junto con el valor n=4, son los únicos números n que permiten raíces primitivas módulo n.

Aplicaciones

Al utilizar el protocolo criptográfico Diffie-Hellman suelen escogerse un primo p y g una raíz primitiva módulo p. Como dijimos, dado $b\in {\mathbb{Z}}_p^{*}$ se tiene $b=g^r(\mathrm{mod}p)$ para un único $r\in \{1,2,...,p-1\}$. Encontrar ese r fijados a y b es lo que se conoce como el problema del logaritmo discreto.

Véase también

• Aritmética modular
• Logaritmo discreto

Referencias

• Plantilla:Cita libro

• Plantilla:Cita libro

Plantilla:Control de autoridades