What is Weils theorem and how can it be used?
The order E of an elliptic curve y^2 + x·y = x^3 + a·x^2 + b over GF(2^(L*K)) can be calculated using the magic formula: 2^(L*K) + 1 – lucas( 2^L-(e-1), 2^L, K ) where e is the order of the curve over GF(2^L), and the function lucas(p,Z,K) = V(K), is defined by the recursion V(0) = 2; V(1) = p; V(K) = p·V(K-1) – Z·V(K-2) Note that GF(2^L) is a sub-field of GF(2^(L*K)) – a and b need to be elements of this sub-field for the theorem to apply. Moreover, E is divisible by e – this useful fact is not always mentioned. If L is fairly small, we can find e by “brute force”, and quite often it turns out that E/e is a (large) prime – if it is, we can choose the fixed point F by choosing an arbitrary point R and setting F = e*R (if this is zero, try again). F then has order E/e. Note that K needs to be prime, as otherwise there will be an intermediate sub-curve of larg(ish) order, and E/e will not be prime. To apply the theorem, we need to identify a sub-field of GF(2^L*K) of order 2^L – dependin
