campo finito a fracción racional

Question

Supongamos que tengo un número $n\in\mathbb F_p$ es decir, un elemento del campo finito obtenido por aritmética módulo de algún primo (impar) $p$ . Estoy buscando una manera de encontrar una descripción simple de $n$ como una fracción $\frac ab$ . En otras palabras, me gustaría una manera de obtener enteros $a,b$ con

$$bn = a \pmod p$$

Obviamente $a=n, b=1$ es una solución, pero me gustaría encontrar el par que minimice $\lvert ab\rvert$ , lo que corresponde aproximadamente a minimizar el número de dígitos que implica su escritura. $b$ no debe ser un múltiplo de $p$ Sin embargo, eso representaría una división por cero en $\mathbb F_p$ . Yo esperaría que todos los resultados satisfagan las siguientes restricciones, que se reducen simplemente a elegir los signos de forma razonable y a cancelar los factores comunes:

$$\begin{gather*} \tfrac{1-p}{2} \leq a \leq \tfrac{p-1}{2} \\ 0 < b \leq \tfrac{p-1}{2} \\ \gcd(a, b) = 1 \end{gather*}$$

Una forma posible es enumerar todas las fracciones que satisfacen las condiciones anteriores, y construir un diccionario a partir de ellas donde $n$ se puede buscar. Pero eso se vuelve inviable para las grandes $p$ .

¿Hay algún algoritmo mejor para encontrar $a$ y $b$ ?

Answer 1

Hay un documento aquí 1 que dice que Thue demostró que si $a$ , $b$ y $m$ son relativamente primos, entonces $$ax-by\equiv0\pmod m$$ puede resolverse con números enteros $x$ y $y$ tal que $|x|\le\sqrt m$ , $|y|\le\sqrt m$ .

$a=1$ , $b=n$ se reduce a su congruencia. El resultado no es exactamente lo que quieres, pero seguramente el método de prueba de Thue te dará lo que quieres.

1 Alfred Brauer y T. L. Reynolds: Sobre un teorema de Aubry-Thue , Canad. J. Math. 3(1951), 367-374. http://dx.doi.org/10.4153/CJM-1951-042-6