Raíz discreta

El problema de hallar una raíz discreta se define de la siguiente manera. Dados un primo $n$ y dos enteros $a$ y $k$, hallar todos los $x$ para los cuales:

$x^k \equiv a \pmod n$

El algoritmo

Resolveremos este problema reduciéndolo al problema del logaritmo discreto.

Apliquemos el concepto de raíz primitiva módulo $n$. Sea $g$ una raíz primitiva módulo $n$. Nótese que, como $n$ es primo, debe existir, y se puede hallar en $O(Ans \cdot \log \phi (n) \cdot \log n) = O(Ans \cdot \log^2 n)$ más el tiempo de factorizar $\phi (n)$.

Podemos descartar fácilmente el caso en que $a = 0$. En este caso, obviamente hay una sola respuesta: $x = 0$.

Como sabemos que $n$ es primo y cualquier número entre 1 y $n-1$ se puede representar como una potencia de la raíz primitiva, podemos representar el problema de la raíz discreta de la siguiente manera:

$(g^y)^k \equiv a \pmod n$

donde

$x \equiv g^y \pmod n$

Esto, a su vez, se puede reescribir como

$(g^k)^y \equiv a \pmod n$

Ahora tenemos una incógnita $y$, que es un problema de logaritmo discreto. La solución se puede hallar usando el algoritmo baby-step giant-step de Shanks en $O(\sqrt {n} \log n)$ (o podemos verificar que no hay soluciones).

Habiendo hallado una solución $y_0$, una de las soluciones del problema de la raíz discreta será $x_0 = g^{y_0} \pmod n$.

Hallar todas las soluciones a partir de una solución conocida

Para resolver el problema dado por completo, necesitamos hallar todas las soluciones conociendo una de ellas: $x_0 = g^{y_0} \pmod n$.

Recordemos el hecho de que una raíz primitiva siempre tiene orden $\phi (n)$, es decir, la menor potencia de $g$ que da 1 es $\phi (n)$. Por lo tanto, si sumamos el término $\phi (n)$ al exponente, seguimos obteniendo el mismo valor:

$x^k \equiv g^{ y_0 \cdot k + l \cdot \phi (n)} \equiv a \pmod n \forall l \in Z$

De ahí que todas las soluciones sean de la forma:

$x = g^{y_0 + \frac {l \cdot \phi (n)}{k}} \pmod n \forall l \in Z$.

donde $l$ se elige de modo que la fracción deba ser un entero. Para que esto sea cierto, el numerador tiene que ser divisible por el mínimo común múltiplo de $\phi (n)$ y $k$. Recordemos que el mínimo común múltiplo de dos números es $lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}$; obtendremos

$x = g^{y_0 + i \frac {\phi (n)}{gcd(k, \phi (n))}} \pmod n \forall i \in Z$.

Esta es la fórmula final para todas las soluciones del problema de la raíz discreta.

Implementación

Aquí hay una implementación completa, incluyendo procedimientos para hallar la raíz primitiva, el logaritmo discreto, y hallar e imprimir todas las soluciones.

int gcd(int a, int b) {
	return a ? gcd(b % a, a) : b;
}
 
int powmod(int a, int b, int p) {
	int res = 1;
	while (b > 0) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
 
// Encuentra la raíz primitiva módulo p
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 (int factor : fact) {
			if (powmod(res, phi / factor, p) == 1) {
				ok = false;
				break;
			}
		}
		if (ok) return res;
	}
	return -1;
}
 
// Este programa encuentra todos los números x tales que x^k = a (mod n)
int main() {
	int n, k, a;
	scanf("%d %d %d", &n, &k, &a);
	if (a == 0) {
		puts("1\n0");
		return 0;
	}
 
	int g = generator(n);
 
	// Algoritmo de logaritmo discreto baby-step giant-step
	int sq = (int) sqrt (n + .0) + 1;
	vector<pair<int, int>> dec(sq);
	for (int i = 1; i <= sq; ++i)
		dec[i-1] = {powmod(g, i * sq * k % (n - 1), n), i};
	sort(dec.begin(), dec.end());
	int any_ans = -1;
	for (int i = 0; i < sq; ++i) {
		int my = powmod(g, i * k % (n - 1), n) * a % n;
		auto it = lower_bound(dec.begin(), dec.end(), make_pair(my, 0));
		if (it != dec.end() && it->first == my) {
			any_ans = it->second * sq - i;
			break;
		}
	}
	if (any_ans == -1) {
		puts("0");
		return 0;
	}
 
	// Imprime todas las respuestas posibles
	int delta = (n-1) / gcd(k, n-1);
	vector<int> ans;
	for (int cur = any_ans % delta; cur < n-1; cur += delta)
		ans.push_back(powmod(g, cur, n));
	sort(ans.begin(), ans.end());
	printf("%d\n", ans.size());
	for (int answer : ans)
		printf("%d ", answer);
}

Problemas de práctica

• Codeforces - Lunar New Year and a Recursive Sequence