Ask Your Question
1

Square roots in finite fields

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

Nikolaj gravatar image

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

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
0

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

tmonteil gravatar image

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

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
1834217616495034514094794093133330973284288791501997659378762348291100326643535685471201140044598836487769582691199
sage: a.sqrt(extend=False, all=True)
[1772773690009084021117103044811629640109943447713374481808538816773421425422985900937975658202516833536671045288222,
2229635865212583372300686780924274516446939372225633403523519319350610225067851963504711970926498830501223227271565]
sage: min(_)
1772773690009084021117103044811629640109943447713374481808538816773421425422985900937975658202516833536671045288222
edit flag offensive delete link more
0

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

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
    algorithm.
    """
    if self.lift() > self.__modulus.sageInteger >> 1:
        return -self
    else:
        return self
edit flag offensive delete link more

Comments

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 +0100 )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

Stats

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

Seen: 2,269 times

Last updated: Aug 26 '19