The following code provides three solutions in such a simple case with a small value for the prime $p$.

```
p = 11
F = GF(p)
D = F(2)
# 1.st solution: brute force:
SOL = [ (x,y) for x in F for y in F if x^2 - D*y^2 == 1 ]
print "(1) Brute force solutions:\n", SOL
# 2.nd solution: Algebraic curve and its F-rational points
R.<x,y> = PolynomialRing( F )
C = Curve( x^2 - D*y^2 -1 )
print "(2) Let C be the folowing algebraic curve:\n", C
print "Its rational points are as follows:"
print C.rational_points()
# 3.rd solution: Group of elements of norm one in the field F( sqrt(D) )
S.<W> = PolynomialRing( F )
K.<a> = GF( p**2, modulus = W^2-D )
U = [ x for x in K if x.norm() == 1 ]
print "(3) Let K be the folowing field:\n", K
print "Its points of norm one are as follows:"
print U
```

Depending on the further use, the one or the other solution is better suited.
The above code delivers:

```
(1) Brute force solutions:
[(0, 4), (0, 7), (1, 0), (3, 2), (3, 9), (5, 1), (5, 10), (6, 1), (6, 10), (8, 2), (8, 9), (10, 0)]
(2) Let C be the folowing algebraic curve:
Affine Plane Curve over Finite Field of size 11 defined by x^2 - 2*y^2 - 1
Its rational points are as follows:
[(0, 4), (0, 7), (1, 0), (3, 2), (3, 9), (5, 1), (5, 10), (6, 1), (6, 10), (8, 2), (8, 9), (10, 0)]
(3) Let K be the folowing field:
Finite Field in a of size 11^2
Its points of norm one are as follows:
[9*a + 3, 10*a + 6, 7*a, 10*a + 5, 9*a + 8, 10, 2*a + 8, a + 5, 4*a, a + 6, 2*a + 3, 1]
```

(Output was slightly touched.) The last case offers also the multiplication.

Note: To get the components of an element in `U`

, one can lift it to `S`

, then take the coefficients, for instance:

```
sage: u = 3+2*a
sage: u in U
True
sage: S(u)
2*W + 3
sage: S(u).coefficients( sparse=False )
[3, 2]
sage: S(7*a).coefficients( sparse=False )
[0, 7]
sage: S(7*a).coefficients()
[7]
sage: S(1).coefficients( sparse=False )
[1]
```

Note that for $\pm1$ there is only one coefficient...

Observation: Working in $K$, we can find a multiplicative generator for the (abstract group $U$ of) $F$-rational point of the algebraic group, for instance:

```
sage: for u in U:
....: if u.multiplicative_order() == len(U):
....: print u
9*a + 3
9*a + 8
2*a + 8
2*a + 3
sage: len(U)
12
sage: euler_phi(len(U))
4
sage: set( [ (3+2*a)^k for k in range(12) ] ) == set(U)
True
```

So $3+2a=3+2\sqrt[F]D$ generates $U$.

Please give us an explicit example, i.e. values for the prime (power?) $p$ and $D$. Brute force works, computing the points of the rational curve works, associating the subgroup of $SL(2,F)$ with entries $x, y, Dy, x$ works. The solution should but best support the further application.

Let's say D = 2 and p = 11, Is there a routine that outputs all the solutions to the equation x^2 - 2y^2 mod 11? Thanks

Thank you very much @dan_fulea. It seemed to work for higher prime numbers as well - it just took some time. Btw, is there a routine that exists that gives a scalar multiple of a solution (<x,y>?