Hay una natural (aleatoria) algoritmo:
Elija $x,y$ uniformemente al azar de $\mathbb{F}$.
Deje $s = ax^2 + by^2$. Si $s \ne 0$ $s$ es un cuadrado en $\mathbb{F}$, vamos a $r= \sqrt{s}$ (la raíz cuadrada puede ser calculada de manera eficiente en un número finito de campo) y el conjunto de $x'=x/r$, $y'=y/r$. Ahora $x',y'$ son una solución a la ecuación original, como puede ser fácilmente verificada, así que hemos terminado.
Si no, vuelva al paso 1.
Hay ninguna garantía de que este algoritmo se espera el tiempo de ejecución será polinomio? De forma heurística, sería de esperar que la respuesta sea sí: alrededor de la mitad de los elementos de $\mathbb{F}$ son cuadrados, por lo que (suponiendo que $ax^2 + by^2$ es distribuido uniformemente al azar al$x,y$) el número de iteraciones de este algoritmo será geométricamente distribuidos con el parámetro $1/2$, o 2 iteraciones en la espera. Por supuesto, esto es sólo un método heurístico.
Podemos justificar el tiempo de ejecución de forma más rigurosa? Me sostienen a continuación que la respuesta es sí.
Vamos a disponer de un trivial de primera situación: si estamos en el carácter de los dos, luego cada valor tiene una raíz cuadrada, por lo que el algoritmo anterior tendrá éxito con casi una certeza. (Dejando $s=ax^2 + by^2$,$\Pr[s=0]=1/|\mathbb{F}|$, y suponiendo que $s\ne 0$, $s$ es sin duda un cuadrado, por lo que el paso 2 se logra el éxito con probabilidad de $1-1/|\mathbb{F}| \ge 1/2$.)
Por lo tanto, en lo que sigue, se puede asumir que estamos en una extraña característica.
Para ayudarnos a razonar acerca de esta situación, vamos a dividir ambos lados por $a$, para obtener los relacionados con la ecuación
$$x^2 + c y^2 = d,$$
donde he definido $c=b/a$, $d=1/a$. Cualquier solución a esta ecuación se resuelve la ecuación original.
Voy a argumentar que $x^2 + c y^2$ es aproximadamente uniforme en $\mathbb{F}$, cuando se $(x,y)$ es uniforme en $\mathbb{F}^2$. Por de escala adecuado, esto demostrará que nuestra heurística de hecho era riguroso.
Voy a definir un grupo multiplicativo $\mathbb{G} = (\{(x,y) : x^2 + c y^2 \ne 0\}, \otimes)$, donde el grupo de operación $\otimes$ se define como sigue:
$$(x_1,y_1) \otimes (x_2,y_2) = (x_1 x_2 - c y_1 y_2, x_1 y_2 + x_2 y_1).$$
Es sencillo pero tedioso para comprobar que este hecho forma un grupo de operación. También, hay un grupo de homomorphism $N : \mathbb{G} \to \mathbb{F}^*$ dada por
$$N(x,y) = x^2 + c y^2.$$
De nuevo, es sencillo pero tedioso para comprobar que este es un homomorphism de la multiplicación de los grupos, por ejemplo, $N((x,y) \otimes (x',y')) = N(x,y) \times N(x',y')$.
Ahora vamos a $s,t$ ser de dos dos-cero elementos de $\mathbb{F}$. Definir
$$S = \{(x,y) \in \mathbb{G} : N(x,y) = s\},
T = \{(x,y) \in \mathbb{G} : N(x,y) = t\}.$$
Desde $N$ es surjective (como se muestra aquí), estos son dos de los cosets de que el núcleo de $N(\cdot)$, y cualquiera de las dos cosets debe tener el mismo tamaño (del teorema de Lagrange), por lo que se deduce que el $|S|=|T|$. Pero $s,t$ fueron arbitrarias distinto de cero elementos de $\mathbb{F}$, por lo que se deduce que el $N(x,y)$ se distribuye de manera uniforme en $\mathbb{F}^*$ al $x,y$ se distribuye de manera uniforme en $\mathbb{G}$.
Ahora $\mathbb{G}$ mantiene el conjunto de $(x,y)$ tal que $x^2+cy^2\ne 0$, por lo que debemos considerar el conjunto $A=\{(x,y) : x^2+cy^2=0\} = \mathbb{F}^2 \setminus \mathbb{G}$. Resulta que este juego no es muy grande: si $-c$ es un cuadrado en $\mathbb{F}$,$|A| = 2|\mathbb{F}|-1$, de lo contrario $|A|=1$. De ello se desprende que, al $x,y$ son elegidos de manera uniforme al azar de $\mathbb{F}$, la probabilidad de que $ax^2 + by^2=0$ es pequeña ($\le 2/|\mathbb{F}|$), por lo que la probabilidad de que tengamos éxito en el paso 2 del algoritmo en la parte superior de esta respuesta es, al menos,$(1-2/|\mathbb{F}|)/2$. Por lo tanto, se espera que el número de iteraciones es constante y pequeño. Este rigurosamente justifica el análisis heurístico de arriba, y muestra que el algoritmo se ejecuta en el polinomio de tiempo, según sea necesario.
En la tierra donde hizo este misterioso grupo $\mathbb{G}$? La intuición es que se trata de mirar a una complejización de la $\mathbb{F}$. En particular, vamos a $\mathbb{K} = \mathbb{F}(\sqrt{-c})$, es decir, tocan una raíz cuadrada de $-c$. Definir una norma en $\mathbb{K}$, por lo que el $N(z) = z \times \overline{z}$ donde $\overline{z}$ es el conjugado complejo de $z$: o, más precisamente, definir $N(\cdot)$ por
$$N(x+y\sqrt{-c}) = (x+y\sqrt{-c}) (x-y\sqrt{-c}) = x^2 + c y^2.$$
Esta norma es multiplicativo: $N(z_1 z_2) = N(z_1) N(z_2)$$z_1,z_2 \in \mathbb{K}$, e $N(z) \in \mathbb{F}$ todos los $z \in \mathbb{K}$. El grupo de operación de $\mathbb{G}$ es simplemente la multiplicación en $\mathbb{K}$, y el grupo de homomorphism $\mathbb{N}$ es sólo de esta norma. Esta intuición sólo funciona si $-1$ no es una plaza en $\mathbb{F}$ (de modo que $-c$ va a ser un no-cuadrado), pero creo que el argumento que me dio anteriormente contiene de hecho, independientemente de si $-1$ es un cuadrado o no.
Espero no haber cometido algún error. Mi agradecimiento a Steven Stadnicki por su cuidadoso de la prueba de lectura de un anterior intento de responder a esta pregunta y a Pablo Rotondo para los útiles comentarios de que la mejora de esta respuesta.
