Ask Your Question

Square roots in finite fields

asked 2019-08-26 16:50:40 +0200

Nikolaj gravatar image

updated 2019-08-26 20:58:02 +0200

FrédéricC gravatar image

In a finite field, say

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
F = GF(p)

does the square_root function always return the root r s.t. sign(r) = +1, assuming that a root exists, where sign is the function that return -1 iff r > (p-1)/2

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2019-08-26 18:04:15 +0200

tmonteil gravatar image

updated 2019-08-26 18:05:33 +0200

It is not specified in the documentation, so you should not rely on this. Note however that the sqrt() method has a all option, to provide all square roots, so that you can pick the smallest:

sage: a = F.random_element()
sage: a
sage: a.sqrt(extend=False, all=True)
sage: min(_)
edit flag offensive delete link more

answered 2019-08-26 18:19:01 +0200

rburing gravatar image

The documentation does not specify it, but it is true. (It should be added to the documentation.)

When you call a.sqrt() first a square root x is computed, and then x = x._balanced_abs() is called.

def _balanced_abs(self):
    This function returns `x` or `-x`, whichever has a
    positive representative in `-n/2 < x \leq n/2`.
    This is used so that the same square root is always returned,
    despite the possibly probabilistic nature of the underlying
    if self.lift() > self.__modulus.sageInteger >> 1:
        return -self
        return self
edit flag offensive delete link more


Note that, though the source code shows some behaviour, as long as the documentation does not specify it, changes in the code can be done silently, and the user's code hidden assumption become wrong.

tmonteil gravatar imagetmonteil ( 2019-08-26 19:10:50 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-08-26 16:50:40 +0200

Seen: 404 times

Last updated: Aug 26 '19