John,
> A variation of this, which would be useful in some elliptic curve
> calculations, would be a function
> RR(x).nearby_rational_whose_denominator_is_a_perfect_square().
>
> For either problem, is there a better solution than going through the
> continued fraction convergents until one is found which has the
> required property? I hope so, since as I wrote that I could see that
> this would certainly fail on most inputs....
the answer is yes. You want to find small integer solutions of
q^2*x - p = small, or if you write x=y/z, q^2*y - p*z = r with p,q,r small
(here y and z are known integers, and p,q,r are the unknowns).
Or modulo z: q^2*y = r (mod z) with r small. There are algorithms from
Coppersmith to find small roots of such modular equations.
The main idea is to build a lattice which contains (polynomial) multiples
of the equation to solve, to reduce the lattice (using LLL), and then one
obtains a set of polynomial equations with small coefficients, whose roots
modulo z necessarily are also roots over the integers.
@InProceedings{Coppersmith96b,
author = {Don Coppersmith},
title = {Finding a Small Root of a Univariate Modular Equation},
booktitle = {Proceedings of Eurocrypt'96},
pages = {155--165},
year = 1996,
volume = 1070,
series = lncs,
publisher = sv
}
@InProceedings{Coppersmith01,
author = {Don Coppersmith},
title = {Finding Small Solutions to Small Degree Polynomials},
booktitle = {Proceedings of CALC'01},
pages = {20--31},
year = 2001,
volume = 2146,
series = lncs,
publisher = sv
}
Paul
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
