Square roots in finite fields

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

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