determining if an element is a square

[Jonathan Bober]

Does anyone know a good way to determine if an element of Q(sqrt 5) is a square? I'm rewriting some of my code in cython, and simply checking (using sage) if something is a square is taking roughly 1000000% of the time it takes to run my code.

Currently sage constructs a quadratic polynomial over K and tries to factor it. (I'm sure I can get a 50% speedup in my case by simply checking first to see if the norm is positive.) I'm thinking that a good way to check if something is a square might be to take the square roots of its embeddings in RR and then check to see if they are algebraic integers by computing traces. Maybe there is a better way to do this. I'm going to walk away from my computer for a few minutes and hope that when I get back someone will have come up with a better solution.

[William Stein]

On Tue, Aug 9, 2011 at 9:54 PM, Jonathan Bober <jwb...@gmail.com> wrote:
> Does anyone know a good way to determine if an element of Q(sqrt 5) is a
> square? I'm rewriting some of my code in cython, and simply checking (using
> sage) if something is a square is taking roughly 1000000% of the time it
> takes to run my code.
>
> Currently sage constructs a quadratic polynomial over K and tries to factor
> it. (I'm sure I can get a 50% speedup in my case by simply checking first to
> see if the norm is positive.) I'm thinking that a good way to check if
> something is a square might be to take the square roots of its embeddings in
> RR and then check to see if they are algebraic integers by computing traces.

They will be algebraic integers, since the square root of an algebraic
integer is an algebraic integers.
But of course you really mean "a quadratic algebraic integer whose
characteristic polynomial has
discriminant that is a square time 5".

> Maybe there is a better way to do this. I'm going to walk away from my
> computer for a few minutes and hope that when I get back someone will have
> come up with a better solution.

I think your solution sounds pretty good, and it reminds me of what
one does with integers. It should be possible to code it so it is
reasonably fast.

-- William

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[R. Andrew Ohana]

The only other thought that I had was to check that your element is a square modulo a couple smallish primes before other checks.

--

Andrew

[Jonathan Bober]

On Tue, Aug 9, 2011 at 9:54 PM, Jonathan Bober <jwb...@gmail.com> wrote:

Does anyone know a good way to determine if an element of Q(sqrt 5) is a square? I'm rewriting some of my code in cython, and simply checking (using sage) if something is a square is taking roughly 1000000% of the time it takes to run my code.

Currently sage constructs a quadratic polynomial over K and tries to factor it. (I'm sure I can get a 50% speedup in my case by simply checking first to see if the norm is positive.)

Of course, I'm sure what I meant was "I'm sure I can get a 50% speedup in my case by simply checking first to see if the element is totally positive." Unfortunately, for some reason these things are totally positive %90 of the time.