Routines for Pell's equations

edit

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$.