Raiz primitiva

Definição

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

Existência

Uma raiz primitiva módulo $n$ existe se:

Este teorema foi provado por Gauss em 1801.

Relação com a função Euler

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

Algoritmo para encontrar uma raiz primitiva

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:

Shoup (1990, 1992) provou, assumindo a hipótese generalizada de Riemann, que $g$ é $O(\log^6 p)$.

Implementação

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;
}