Thanks Paul!
John
On 31/01/2008, Paul Zimmermann <[EMAIL PROTECTED]> wrote:
>
> 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
>
> >
>
--
John Cremona
--~--~---------~--~----~------------~-------~--~----~
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-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
