# Descent method with gaussian reduction.

Sorry for a very late blog post, I had a really busy week and finally I managed to find sometime to write about the progress I made in the last week. I implemented an improved version of the descent method which uses gaussian reduction. I found this algorithm in [1]. Here is a sketch of the algorithm.

#### descent(a, b)

1. If $|a| > |b|$ then swap $a$ and $b$, solve the resulting equation, then swap $y$ and $z$ in the solution obtained.
2. If $b = 1$ then set $(x, y, z) = (1, 1, 0)$ and stop.
3. If $a = 1$  then set $(x, y, z) = (1, 0, 1)$ and stop.
4. If $b = -1$ there is no solution (since $a$ must be $-1$).
5. If $b = -a$ then set $(x, y, z) = (0, 1, 1)$ and stop.
6. If $b = a$ then let $(x_{1}, y_{1}, z_{1})$ be a solution of $X_{1}^2 + Z_{1}^2 = aY_{1}^2$, set $(x, y, z) = (ay_{1}, x_{1}, z_{1})$ and stop.
7. Let $w$ be a solution to $x^2 \equiv a (mod \ b)$. with $w \leq |b|/2$, and set $(x_{0}, z_{0}) = (w, 1)$, so that $x_{0}^2 - az_{0}^2 \equiv 0 (mod \ b)$.
8. Use lattice reduction to find a new nontrivial solution $(x_{0}, z_{0})$ to the congruence $X^2 - aZ^2 \equiv 0 (mod \ b)$ with $x_{0}^2 + |a|z_{0}^2$ as small as possible.
9. Set $t = (x_{0}^2 - az_{0}^2)/b$ and write $t = t_{1}t_{2}^2$ with $t_{1}$ square-free.
10. Let $(x_{1}, y_{1}, z_{1})$ be a solution to $X^2 - aZ^2 = t_{1}Y^2$ then
$(x, y, z) = (x_{0 }x_{1} + az_{0}z_{1}, t_{1}t_{2}y_{1}, z_{0}x_{1} + x_{0}z_{1})$

I spent a lot of time finding an algorithm for lattice reduction. There were generalized algorithms but I looked for something which is faster because we are concerned with vectors with two bases. I found  gaussian reduction algorithm in [2] which uses a method specific to this case.

#### References

[1] .. Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0.
[2] .. Gaussian lattice Reduction [online]. Available: http://home.ie.cuhk.edu.hk/~wkshum/wordpress/?p=404