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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: