Na aritmética modular, um número $g$ é chamado de raiz primitiva modulo n se todo número coprimo de $n$ for congruente à uma potência de $g$ módulo $n$. Matematicamente, $g$ é uma raiz primitiva se, e somente se, para qualquer inteiro $a$ no qual $\gcd(a, n) = 1$, existe um inteiro $k$ que:
$g^k \equiv a \pmod n$.
$k$ é então chamado de index ou logaritmo discreto de $a$ na base $g$ módulo $n$. $g$ também é chamado de gerador do grupo multiplicativo de inteiros módulo $n$.
Em particular, no caso em que $n$ é primo, as potências da raiz primitiva percorrem todos os números de $1$ até $n-1$.
Uma raiz primitiva módulo $n$ existe se:
Este teorema foi provado por Gauss em 1801.
Seja $g$ uma raiz primitiva módulo $n$. Então podemos mostrar que o menor número $k$ para o qual $g^k \equiv 1 \pmod n$ é igual a $\phi (n)$. Além disso, o inverso também é verdadeiro, e esse fato será usado neste artigo para encontrar uma raiz primitiva.
Além disso, o número de raízes primitivas módulo $n$, se houver alguma, é igual a $\phi (\phi (n) )$.
Um método é considerar todos os números no intervalo $[1, n-1]$. E então verifique se cada uma é uma raiz primitiva, calculando todas as suas exponenciações para ver se são todas diferentes. Esse algoritmo tem complexidade $O(g \cdot n)$, o que seria lento. Nesta seção, propomos um algoritmo mais rápido usando teoremas conhecidos.
Na seção anterior, sabemos que se o menor número $k$ para o qual $g^k \equiv 1 \pmod n$ é $\phi (n)$, então $g$ é uma raiz primitiva. Como para qualquer número $a$ coprimo com $n$, sabemos pelo teorema de Euler que $a ^ { \phi (n) } \equiv 1 \pmod n$, para verificar se $g$ é raiz primitiva, basta verificar isso para todos os $d$ menores que $\phi (n)$, $g^d \not \equiv 1 \pmod n$. Entretanto, esse algoritmo ainda é lento.
Pelo teorema de Lagrange, o índice 1 de qualquer número módulo $n$ deve ser um divisor de $\phi (n)$. Portanto, é suficiente verificar para todos os divisores apropriados $d \mid \phi (n)$ que $g^d \not \equiv 1 \pmod n$. Esse já é um algoritmo muito mais rápido, mas ainda podemos fazer melhor.
Fatore $\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$. Provamos que no algoritmo anterior, é suficiente considerar apenas os valores de $d$ que têm a forma $\frac { \phi (n) } {p_j}$. De fato, seja $d$ qualquer divisor adequado de $\phi (n)$. Então, obviamente, existe o $j$ que $d \mid \frac { \phi (n) } {p_j}$, ou seja, $d \cdot k = \frac { \phi (n) } {p_j}$. No entanto, se $g^d \equiv 1 \pmod n$, nós teríamos:
$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.
ou seja, entre os números da forma $\frac {\phi (n)} {p_i}$, haveria pelo menos um deles para que as condições não fossem atendidas.
Agora temos um algoritmo completo para encontrar a raiz primitiva:
Em seguida, itere sobre todos os números $g \in [1, n]$, e, para cada número, para verificar se é raiz primitiva, fazemos o seguinte:
O tempo de execução desse algoritmo é $O(Ans \cdot \log \phi (n) \cdot \log n)$ (assumindo que $\phi (n)$ tenha $\log \phi (n)$ divisores).
Shoup (1990, 1992) provou, assumindo a hipótese generalizada de Riemann, que $g$ é $O(\log^6 p)$.
O código a seguir assume que o módulo p é um número primo. Para que funcione com qualquer valor de p, devemos adicionar o 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;
}