The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field

Question

Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$.

1. is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time? if $a$ is invertible modulo $P$ this is equivalent to $(1-by^2)/a$ is a square in $\mathcal{O}_L/P$.

2. is there any algorithm to find such $x$ and $y$ ? all such possible $(x,y)$?

3. an interesting case is: $a=b$ and $a$ is invertible modulo $P$.

Update: for $P$ above $2$, (wlog) $ord_P(a) = 0$ and $ord_P(b)=1$ there is an algorithm that outputs a solution (Algorithm 6.2)

Answer 1

This problem should really be posed over a general finite field (reductions of elements in $\mathcal O_L$ modulo $P$ can be computed in polynomial time).

Over any finite field $F$, the equation $ax^2+by^2=1$ has a solution whenever $a,b\neq 0$. This can be deduced using the pigeonhole principle, observing that the image sets of the maps $ax^2$ and $1-bx^2$ have total size $>|F|$ and therefore must overlap. If $a=0,b\neq 0$ (resp. $a\neq 0,b=0$) then there is a solution iff $b$ (resp. $a$) is a square in $F$. This condition can be checked in polynomial time by computing a Legendre symbol.

As for finding a solution (I will focus on the case $a,b\neq 0$), one simple approach is to pick $y$ at random and check if $1-by^2$ is a square, then if it is compute a square root. This gives a probabilistic polynomial time algorithm.

A deterministic polynomial-time algorithm is available as well, see here https://scholars.iwu.edu/files/39699175/fulltext.pdf