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.
Ejemplos
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
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
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
- Aritmética modular
- Logaritmo discreto
Referencias
- 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.
Datos: Q948010