Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Problem Description

Many doctests use .lift_x() to construct a specific point, hence they implicitly rely on the method being deterministic. This is true in many cases, but there are base-ring implementations for which it fails:

sage: F.<t> = GF((101,3))
sage: E = EllipticCurve(F, [1,1])
sage: for _ in range(10):
....:     print(E.lift_x(t+1))
....:
(t + 1 : 39*t^2 + 14*t + 12 : 1)
(t + 1 : 39*t^2 + 14*t + 12 : 1)
(t + 1 : 62*t^2 + 87*t + 89 : 1)
(t + 1 : 62*t^2 + 87*t + 89 : 1)
(t + 1 : 62*t^2 + 87*t + 89 : 1)
(t + 1 : 39*t^2 + 14*t + 12 : 1)
(t + 1 : 62*t^2 + 87*t + 89 : 1)
(t + 1 : 39*t^2 + 14*t + 12 : 1)
(t + 1 : 62*t^2 + 87*t + 89 : 1)
(t + 1 : 39*t^2 + 14*t + 12 : 1)

This creates the unpleasant situation that users will write code which silently assumes that .lift_x() is deterministic, then encounter surprising bugs once they try the same code on other base fields where it suddenly behaves randomly.

Cc: @JohnCremona

Proposed Solution

Make .lift_x() deterministic and document that guarantee.

This can be as easy as calling ys.sort() in two places in .lift_x(), but it breaks a lot of doctests — including some that I'm not confident enough about to change them.

Alternatives Considered

Make all .sqrt() methods deterministic.

This seems more work, is more likely to miss some cases, and is prone to other implementations being added later that break the guarantee again.

Additional Information

No response