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

Ejemplos[editar]

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

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