# Square roots in finite fields

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 close merge delete

Sort by » oldest newest most voted

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

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.

( 2019-08-26 12:10:50 -0600 )edit

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

more