📚 Description

The current implementation of quadratic_twist computes (possibly several times) unnecessary finite field square roots, but the only requirement is to select D which has no such square roots, which can be tested efficiently using PARI (by checking that the norm is not a quadratic residue).

This solves slowness over large finite field extensions:

sage: p = 2**255 - 19
....: K.<a> = GF(p**64)
# Sage 9.8
sage: %timeit EllipticCurve(K, [0, K.random_element()]).quadratic_twist()
17.8 s ± 8.5 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
# This patch
sage: %timeit EllipticCurve(K, [0, K.random_element()]).quadratic_twist()
9.69 ms ± 388 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

📝 Checklist

• I have made sure that the title is self-explanatory and the description concisely explains the PR.
• I have linked an issue or discussion.
• I have created tests covering the changes.
• I have updated the documentation accordingly.

⌛ Dependencies