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
{\displaystyle \mathbb {Z} _{n}^{*}}
{\displaystyle \forall b\in \mathbb {Z} _{n}^{*}}
{\displaystyle a^{k}\equiv b{\pmod {n}}}
{\displaystyle \mathbb {Z} _{n}^{*}}
denota los elementos invertibles módulo n. Dado que el orden de
{\displaystyle \mathbb {Z} _{n}^{*}}
φ ( n )
, siendo φ la función phi de Euler, una raíz primitiva es un elemento con ese orden.
entonces 3 es raíz primitiva módulo 5: Si observamos bien, todo resto coprimo con 5 (1, 2, 3 y 4) es congruente con
De hecho (y esto ocurre para toda raíz primitiva) el
, tenemos que 5 es raíz primitiva:
, o sea que obtenemos todos los elementos de
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
{\displaystyle \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
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,
, 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. 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
{\displaystyle b\in \mathbb {Z} _{p}^{*}}
Encontrar ese r fijados a y b es lo que se conoce como el problema del logaritmo discreto.