Re: [sage-support] feature request/proposal concerning the method nearby_rational

[John Cremona]

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

John

On 31/01/2008, Georg <georg.gra...@gmail.com> wrote:
>
> Hi,
> there is a method
> RR(x).nearby_rational(...)
> which returns a rational number ....
> it would be convenient for me to have a method which returns a
> rational number which has also a rational square root, something like
> RR(x).nearby_rational_perfect_square(...)
> , I'm not asking for a workaround, at least not for the most obvious
> one (taking the square root of x and using .nearby_rational with
> adjusted tolerance...),
> may this method could be useful for others, too ....
> Thanks, Georg
>
>
> >
>

--
John Cremona

[Paul Zimmermann]

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]

Thanks Paul!

John

--
John Cremona