.set_order is deterministically incorrect in rare cases

[grhkm21]

Steps To Reproduce

I don't know if "deterministically incorrect" is the correct term, but the method is probabilistic, and I am claiming that it does the wrong thing with probability 1.

E = EllipticCurve(GF(127), [0, 1])
E.set_order(126)

Expected Behavior

ok

Actual Behavior

It should give an error. In a separate session, you see that

sage: E = EllipticCurve(GF(127), [0, 1])
....: assert all(P * 126 == 0 for P in E) and E.order() == 108

Additional Information

The bug is obvious from the code, but I am not sure about a fix that doesn't involve computing .order directly. For more test cases just brute force. In essence we want a method E.has_order(N) that doesn't involve computing E.order().

sage: from tqdm import tqdm
....: from sage.schemes.curves.projective_curve import Hasse_bounds
....: 
....: for p in prime_range(100, 200):
....:     for j in range(1, p):
....:         E = EllipticCurve(GF(p), j=j)
....:         o = E.order()
....:         inv = E.abelian_group().invariants()
....:         if len(inv) == 1:
....:             continue
....:         a, b = Hasse_bounds(p, 1)
....:         for o1 in range(a, b + 1):
....:             if o1 == o:
....:                 continue
....:             if all((P * o1).is_zero() for P in E.gens()):
....:                 print("!", p, j, o1)
! 101 11 90
! 101 11 110
! 101 11 120
! 101 24 84
! 103 22 120
! 103 102 120
! 109 72 120
! 109 89 120
! 113 33 96
! 113 33 112
! 113 90 120
! 127 54 120
! 137 84 120
! 137 128 160

Here's a stupid idea that doesn't work: derive \tr(E) then verify the Frobenius quadratic equation is correct.

sage: p = 127
....: E = EllipticCurve(GF(p), j=0)
....: t0 = p + 1 - 108
....: t1 = p + 1 - 126
....: phi = E.frobenius_endomorphism()
....: assert all(phi(phi(P)) - t0 * phi(P) + 127 * P == 0 for P in E)
....: assert all(phi(phi(P)) - t1 * phi(P) + 127 * P == 0 for P in E)

@JosePisco @yyyyx4 might be interested.

Environment

Latest Sage version

Checklist

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

[grhkm21]

I mark it as major since the method is quite useful. For example if we want to find the twist of the curve with a given order, we can use this (or rather .has_order).

[grhkm21]

Okay the trace test thing is stupid because phi(P) == P over the base field 🤦🏻 taking a quadratic extension does separate the two cases, at least for the example above, but obviously I don't have a proof that it always does, plus it's stupidly slow.

Another option is to also check the order on the quadratic twist, but that's also probabilistic and I highly suspect it's also deterministically incorrect in rare cases.

One more observation is that the number of "fake orders" should be very few - I believe at most 5 - because of uh I will fill this in later I need to get off the train

[grhkm21]

The reason for the number of fake orders is that with the current implementation of .set_order we are able to check (with high probability with a large enough num_checks) that the given order $N$ satisfies $\mathrm{lcm}_{P \in E(K)} \mathrm{ord}(P) \mid N$, and since $E(K) \cong \mathbb{Z} / m\mathbb{Z} \times \mathbb{Z} / (N / m)\mathbb{Z}$, we have $\mathrm{lcm}_{P \in E(K)} \mathrm{ord}(P) = \mathrm{lcm}(m, N / m) \geq \sqrt{N}$. This combined with the Weil-Hasse bound proves my claim.

I don't know how to use it to our advantage though 😓

Also @GiacomoPope I think you would also be interested

[grhkm21]

This bug only applies when the curve is non-cyclic.

[user202729]

Technically it's not a bug… since set_order is used incorrectly so erroneous result can be expected. Of course it's nice if error detection is more robust, as long as the method does not get unusably slow.

The only "bug" I can find is with the documentation making claims such as the following

It is also very likely an error to pass a value which is not the actual order of this curve. How unlikely is determined by num_checks, the factorization of the actual order, and the actual group structure:

---

Anyway, here are some other ideas to possibly fix it. Of course, any additional checking will slow down the .set_order() function, the question is is the slowdown worthwhile.

Theorem: The set of points in $E$ defined over a field $𝔽_{p^k}$ is a finite Abelian group.

Which implies, by the fundamental theorem of finite Abelian group, we can write $E ≅ ℤ/n_1 ℤ ⊕ ℤ/n_2 ℤ ⊕ ⋯$ where $n_i$ is divisible by $n_{i+1}$.

Theorem: $\text{lcm}_{P ∈ E} \text{order}(P) = n_1$.

Which means the current algorithm checks if $n_1 \mid \texttt{order}$. If $E$ is cyclic, combine this with $|E| = n_1 ≥ \frac{\texttt{order}}{2}$ this is clearly correct.

Theorem: $E[m] ≅ 0$, $ℤ/mℤ$, or $(ℤ/mℤ)^2$.

Which implies, if there's a $ℤ/n_3 ℤ$ term in the decomposition above, then $E[n₃] ≅ (ℤ/mℤ)^3$ or larger, contradiction. So, if $E/𝔽_{p^k}$ is not cyclic, it must be $ℤ/aℤ ⊕ ℤ/bℤ$ for $b \mid a$. Our algorithm checks if $a \mid \texttt{order}$ in this case.

Conjecture: generic group operations cannot, in polynomial time, distinguish between the following, given $n = p_1 p_2 p_3$ where $p_i$ are large primes of similar magnitude:

• The group $G = ℤ/p_1 p_2 p_3 ℤ$, and
• The group $G = ℤ/p_1 p_2ℤ ⊕ ℤ/p_2 ℤ$.

Note that computing a basis involves factorizing the order (see .gens() method documentation in Sage)

Assume the above conjecture, we're in trouble. Nevertheless:

Theorem: In the case above, pick two random points in the curve,

• for the first case, the Weil pairing is always $0$.
• for the second case, the Weil pairing for $n = p_1 p_2^2$ (the correct group order) is always $0$, but the Weil pairing for our $n = p_1 p_2 p_3$ is nonzero.

So,

Conjecture: If we also check the Weil pairing is zero for the provided n for many random pairs of points, then we're good.

I guess. (Sounds about right, but I'm lazy to prove it.)

Now the question is, is the Weil pairing fast enough to compute to justify the change?

---

This is another idea, building on grhkm21's work above.

Assume $E/F ≅ ℤ/(a b) ℤ ⊕ ℤ/b ℤ$ where $a ≥ 1, b > 1$.
Then a fake order is $a b (b+δ)$ for integer $δ ≠ 0$.

As shown above, we have that $|δ|∈ O(1)$. But we also have $a ∈ O(1)$.

As such, if we're given a fake order $n = a b (b+δ)$, we can simply try to iterate over all values of $a$ and $δ$, then solve for $b$.

If the root is an integer, then we check if it's highly likely that every point has order $a b$, if yes then by Hasse-Weil bound we have that $E/F ≅ ℤ/a' b'ℤ ⊕ ℤ/b'ℤ$ for some $a' b' = a b$ and $a' ∈ O(1)$.

Claim: in this case $a = a'$ and $b = b'$, with finitely many exceptions.

Proof: We have $\frac{a}{a'}= \left( \frac{b}{b'}\right)^2$. So $\frac{a' b'^2}{a b^2} = \left( \frac{a}{a'}\right)^{3/2}$, but this value is in $1 ± O(\frac{1}{\sqrt{n}})$, so for $n$ large enough it forces $a=a'$ (recall there are only $O(1)$ choices of $\frac{a}{a'}$).

---

An example where both a curve and its quadratic twist has a fake order is given below. It is not sufficient though.

It might make an interesting exercise to prove that when the degree of the finite field is odd then there is no solution, or find a counterexample.
Theorem 4.4 in Washington's book might be useful.

F = GF(257^2)
assert [*F.modulus()] == [3, 251, 1]
E = EllipticCurve([F.gen()^13111, 1])
assert E.order() == 256*256
E.set_order(256*257)
E.set_order(256*256)
G = E.quadratic_twist()
assert G.order() == 258*258
G.set_order(258*257)
G.set_order(258*258)