Raíz primitiva módulo n

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 \forall b\in \mathbb{Z}_n^* existe k\in\mathbb{Z} tal que a^k\equiv b (mod \ n). Aquí \mathbb{Z}_n^* denota los elementos invertibles módulo n.

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

Ejemplos[editar]

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


\begin{array}{l}
3^1 =   3   \\
3^2 =   9 \equiv 4 \pmod 5 \\
3^3 =  3^2 \times 3 \equiv 4 \times 3 =  12 \equiv 2 \pmod 5  \\
3^4 = 3^3 \times 3 \equiv 2 \times 3 = 6 \equiv 1 \pmod 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=\varphi(5).

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


\begin{array}{l}
5^0=1\\
5^1 =   5   \\
5^2 =   25 \equiv 11 \pmod {14} \\
5^3 =  5^2 \times 5 \equiv 11\times 5 =  55 \equiv 13 \pmod {14}  \\
5^4 = 5^3 \times 5 \equiv 13 \times 5 = 65 \equiv 9 \pmod {14}   \\
5^5 = 5^4 \times 5 \equiv 9 \times 5 = 45 \equiv 3 \pmod {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[editar]

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 \pmod 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[editar]

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 \pmod 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[editar]

Referencias[editar]

Apostol, Tom (2002). «Raíces primitivas». Introducción a la teoría analítica de números (2 edición). España: Reverté. pp. 255–265. ISBN 84-291-5006-4. 

de Oliveira Santos, José Plínio (2009). «6 - Raízes primitivas». Introducao à teoria dos numeros (en portugués) (3 edición). Río de Janeiro: IMPA. pp. 116–127. ISBN 978-85-244-0142-8.