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 , es decir, si existe tal que . Aquí denota los elementos invertibles módulo n.

Dado que el orden de es , siendo φ la función phi de Euler, una raíz primitiva es un elemento con ese orden.

EjemplosEditar

Si   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   módulo 5 para algún  . De hecho (y esto ocurre para toda raíz primitiva) el   puede elegirse entre 1 y  .

Para  , tenemos que 5 es raíz primitiva:

 

 , o sea que obtenemos todos los elementos de   como potencias de 5.

Existencia de raíces primitivasEditar

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   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   para un único  .

También puede demostrarse que si   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.

AplicacionesEditar

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   se tiene   para un único  . Encontrar ese r fijados a y b es lo que se conoce como el problema del logaritmo discreto.

Véase tambiénEditar

ReferenciasEditar

  • 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.