Raíz primitiva

Definición

En aritmética modular, un número $g$ se llama raíz primitiva módulo n si todo número coprimo con $n$ es congruente con una potencia de $g$ módulo $n$. Matemáticamente, $g$ es una raíz primitiva módulo n si y solo si para cualquier entero $a$ tal que $\gcd(a, n) = 1$, existe un entero $k$ tal que:

$g^k \equiv a \pmod n$.

$k$ se llama entonces el índice o logaritmo discreto de $a$ en base $g$ módulo $n$. $g$ también se llama el generador del grupo multiplicativo de enteros módulo $n$.

En particular, para el caso en que $n$ es primo, las potencias de la raíz primitiva recorren todos los números de $1$ a $n-1$.

Existencia

Existe raíz primitiva módulo $n$ si y solo si:

• $n$ es 1, 2, 4, o
• $n$ es potencia de un primo impar $(n = p^k)$, o
• $n$ es el doble de una potencia de un primo impar $(n = 2 \cdot p^k)$.

Este teorema fue demostrado por Gauss en 1801.

Relación con la función de Euler

Sea $g$ una raíz primitiva módulo $n$. Entonces podemos mostrar que el menor número $k$ para el cual $g^k \equiv 1 \pmod n$ es igual a $\phi (n)$. Además, el recíproco también es cierto, y este hecho se usará en este artículo para hallar una raíz primitiva.

Más aún, la cantidad de raíces primitivas módulo $n$, si hay alguna, es igual a $\phi (\phi (n) )$.

Algoritmo para hallar una raíz primitiva

Un algoritmo naive es considerar todos los números en el rango $[1, n-1]$. Y luego comprobar si cada uno es una raíz primitiva, calculando todas sus potencias para ver si son todas distintas. Este algoritmo tiene complejidad $O(g \cdot n)$, que sería demasiado lento. En esta sección proponemos un algoritmo más rápido usando varios teoremas conocidos.

De la sección anterior, sabemos que si el menor número $k$ para el cual $g^k \equiv 1 \pmod n$ es $\phi (n)$, entonces $g$ es una raíz primitiva. Como para cualquier número $a$ coprimo con $n$, sabemos por el teorema de Euler que $a ^ { \phi (n) } \equiv 1 \pmod n$, entonces para comprobar si $g$ es raíz primitiva, basta con comprobar que para todo $d$ menor que $\phi (n)$, $g^d \not \equiv 1 \pmod n$. Sin embargo, este algoritmo sigue siendo demasiado lento.

Por el teorema de Lagrange, sabemos que el índice de 1 de cualquier número módulo $n$ debe ser un divisor de $\phi (n)$. Así, basta verificar para todo divisor propio $d \mid \phi (n)$ que $g^d \not \equiv 1 \pmod n$. Este ya es un algoritmo mucho más rápido, pero todavía podemos hacerlo mejor.

Factoricemos $\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$. Demostramos que en el algoritmo anterior basta considerar solo los valores de $d$ que tienen la forma $\frac { \phi (n) } {p_j}$. En efecto, sea $d$ cualquier divisor propio de $\phi (n)$. Entonces, obviamente, existe un $j$ tal que $d \mid \frac { \phi (n) } {p_j}$, es decir $d \cdot k = \frac { \phi (n) } {p_j}$. Sin embargo, si $g^d \equiv 1 \pmod n$, obtendríamos:

$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.

es decir, entre los números de la forma $\frac {\phi (n)} {p_i}$, habría al menos uno tal que las condiciones no se cumplieran.

Ahora tenemos un algoritmo completo para hallar la raíz primitiva:

• Primero, hallar $\phi (n)$ y factorizarlo.

• Luego iterar por todos los números $g \in [1, n]$, y para cada número, para comprobar si es raíz primitiva, hacemos lo siguiente:

  • Calcular todos los $g ^ { \frac {\phi (n)} {p_i}} \pmod n$.
  • Si todos los valores calculados son distintos de $1$, entonces $g$ es una raíz primitiva.

  El tiempo de ejecución de este algoritmo es $O(Ans \cdot \log \phi (n) \cdot \log n)$ (suponiendo que $\phi (n)$ tiene $\log \phi (n)$ divisores).

Shoup (1990, 1992) demostró, asumiendo la hipótesis de Riemann generalizada , que $g$ es $O(\log^6 p)$.

Implementación

El siguiente código asume que el módulo p es un número primo. Para que funcione para cualquier valor de p, hay que añadir el cálculo de $\phi (p)$.

int powmod (int a, int b, int p) {
	int res = 1;
	while (b)
		if (b & 1)
			res = int (res * 1ll * a % p),  --b;
		else
			a = int (a * 1ll * a % p),  b >>= 1;
	return res;
}
 
int generator (int p) {
	vector<int> fact;
	int phi = p-1,  n = phi;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			fact.push_back (i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		fact.push_back (n);
 
	for (int res=2; res<=p; ++res) {
		bool ok = true;
		for (size_t i=0; i<fact.size() && ok; ++i)
			ok &= powmod (res, phi / fact[i], p) != 1;
		if (ok)  return res;
	}
	return -1;
}