As was deduced from the brute force point counting data for all possible elliptic curves of the form x^{3} + ax^{2} + b = y^{2} + xy over binary fields up till and including extension degree m = 10, the values of parameter a can be devided into two sets, both of a size q/2, where q = 2^{m} is the cardinality of the field and therefore equal to the number of possible values of a. Let us call these two sets A_{0} and A_{1} so that A_{0} A_{1} = , A_{0} A_{1} = and . = = q/2
Then furthermore it was found that A_{0} and A_{1} are only a function of the field (GF(2^{m})/<t^{m}+t^{k}+1>) and not of b. Let a_{0} A_{0} and a_{1} A_{1}, and then define the curves E_{0} and E_{1} to be E_{0}: x^{3} + a_{0}x^{2} + b = y^{2} + xy and E_{1}: x^{3} + a_{1}x^{2} + b = y^{2} + xy, then it was found that for some fixed b also #E_{0} and #E_{1} are fixed (not depending on the specific choice of a_{0} and a_{1} respectively) and that #E_{0} + #E_{1} = 2(q + 1). (Note: the notation #E is often used in literature to denote the cardinality of the Abelian group formed by the points of the elliptic curve E).
We would like to find how A_{0} and A_{1} depend on the field parameters, because that will reduce the amount of computations needed during the continuation of this research dramatically, as then we only have to try two values of a instead of q values.
The finite field , called a binary field, can be viewed as a vector space of dimension m over _{2}. That is, there exists a set of m elements { _{0}, _{1}, ..., _{m-1}} in such that each a can be written uniquely in the form
where c_{i} {0,1}.
The set { _{0}, _{1}, ..., _{m-1}} is called a basis of over _{2}. We can then represent a as a binary vector (c_{0}, c_{1}, ..., c_{m-1}). Libecc uses the polynomial basis, so in our case we just have _{i} = t^{i} where t is the fixed complex (or whatever) root of our reduction trinomial t^{m} + t^{k} + 1. (Note that it is possible to chose another basis, called a normal basis, of the form { , ^{2}, ^{22}, ..., ^{2m-1}} where . It is well known that such a basis always exists).
The observation that A_{0} is exactly half of the total space, and considering that there are only two possible values per 'dimension', indicates that A_{0} is a subspace of of one dimension less than .
It seems highly unlikely that this subspace would be 'curved'. I cannot prove this at this point, but it seems to me that there must be some kind of symmetry between the different dimensions: when we exchange any two coordinates then there shouldn't be a dramatic impact on the other coordinates. One property of a given coordinate c_{i} that I expect to stay fixed under the permutation of the other coordinates is the property of whether or not toggling c_{i} causes us to switch between A_{0} and A_{1}. This doesn't mean that a permutation of the other coordinates doesn't cause us to switch between A_{0} and A_{1} too, but it shouldn't cause us to change from switching to non-switching.
A_{0} is a hyperplane.
As one of the goals of this project is to reach people who did not study mathematics, lets first explain what a hyperplane means. Consider some n-dimensional vector space for which there exists an orthogonal basis. An orthogonal basis is a basis of elements (vectors) of that vector space that are all orthogonal to eachother. Orthogonal means, in terms of vectors, that they make an angle of 90 degrees with eachother. When two vectors are orthogonal, then their inproduct will be zero. I hestitate to explain inproduct, because when you don't know that then I doubt you would be reading this in the first place. But why not, the inproduct of two vectors can be calculated by multiplying their coordinates pair-wise and then summing up all those products. Thus, if one vector has coordinates (1,1,0,0,1,0,1) (in some seven dimensional space) and another one has coordinates (0,0,1,1,0,1,0) then they make an angle of 90 degrees because 1*0 + 1*0 + 0*1 + 0*1 + 1*0 + 0*1 + 1*0 = 0. A hyperplane is a subspace of one dimension less than the space in which it is contained (mathematicians would say, of codimension 1) that is 'flat'. That means that there exists a fixed vector n that that is a normal of the hyperplane at any point (it makes an angle of 90 degrees with the hyperplane at any point; or in other words with any vector that is the result of subtracting two arbitrary, though distinct, vectors that are element of the hyperplane). Ok, by now you should get the picture that the thing is 'flat'!
Let us next show that a hyperplane indeed fulfills the intuitive feeling that whether or not toggling any bit of a causes us to either switch between A_{0} and A_{1} or not, independent of the choice of the other bits. Lets use the notation from above and write a as a binary vector (c_{0}, c_{1}, ..., c_{m-1}) where c_{i} {0,1} represents the bits of a. Furthermore, let n be represented by the binary vector (n_{0}, n_{1}, ..., n_{m-1}). Without loss of generality, we can chose a = 0 = (0, 0, ..., 0) to be element of A_{0} (it has to be an element of either A_{0} or A_{1}, so why not A_{0}). Assume that A_{0} is a hyperplane and that n is the normal of that hyperplane. Then the angle that the vector n makes at any point a_{0} A_{0} will be 90 degrees, as per our definition that n is the normal of the hyperplane A_{0}. And that means that the inproduct of n with a_{0} - a_{i} will be 0 for any arbitrary a_{i} A_{0}. Therefore also for a_{i} = 0. Let (a_{0,0}, a_{0,1}, ..., a_{0,m-1}) be the vector representation of a_{0} then the inproduct can be written as [mod 2]. And since the n_{i} are fixed, this clearly shows that when n_{i} = 0 then changing a_{0,i} has no influence on the result of the inproduct and therefore will not cause a change of a_{0} being an element of A_{0}. While when n_{i} = 1 then changing the corresponding bit a_{0,i} will toggle the outcome of the inproduct and hence cause that vector not to be an element of A_{0} anymore. And this is independent of the value of any of the other bits.
Understanding the above (and still assuming that A_{0} is indeed a hyperplane of course) it is very easy to find the normal (n_{0}, n_{1}, ..., n_{m-1}). One only has to try each value of a with exactly one bit set (which are only m different values). Let this single bit be c_{j} so that
If, using this a, the resulting curve has the cardinality #E_{0}, the cardinality corresponding to A_{0}, then the inproduct has to be 0 (because we defined that a = 0 is element of A_{0}). The inproduct will therefore have to equal 1 precisely for each j that corresponds to A_{1} and thus has a cardinality #E_{1} #E_{0}! And the inproduct will only be 1 when n_{j} = 1.
An algorithm for finding the normal n of hyperplane A_{0} could therefore be the following:
There is a little problem with this algorithm. This project has two goals: 1) to make elliptic curve cryptography more accessible to people without a mathematic university degree, and 2) to be the first Open Source project providing the means to generate your own cryptographically safe curves, which basically comes down to providing the means to determine the cardinality of an arbitrary elliptic curve. Therefore, an algorithm with the phrase "Find the cardinality of all curves ... blah blah" is easier said than done. Surely, we can do the above brute force, and it would be feasible for curves over fields up till extension degrees of m = 31, and that might be enough to guess a relationship between A_{0} and m, but... we still have a hypothesis to prove too, namely that A_{0} is indeed a hyperplane and using the above algorithm won't prove that at all, it will just give results. Therefore, it would be necessary to check in addition whether or not the resulting normal n is indeed a normal to all a_{0} A_{0}! And determining the cardinality of the curves for any a is really too much and/or will not give enough data points to feel secure about the hypothesis...
Time to become really smart therefore (and believe it or not but I am actually proud of the following, heheh).
Suppose for a moment that #E_{0} is a multiple of 4 (as is the case as I will show below). That is, #E_{0} = 4k for some k . Then #E_{1} = 2(q + 1) - #E_{0} = 2(2^{m} + 1) - 4k 2 mod 4 for m 1. In other words, then #E_{1} is not divisable by 4.
Further, recall that the order of any point on the curve devides the cardinality of the curve. That means that if we can find any point that has order 4, then the curve must have a cardinality that is divisable by 4. Moreover, we are free to chose any arbitrary value of b for this investigation (as A_{0} does not depend on it). So, we can chose b = 1.
Then it is easy to prove that there is always a solution to the curve with a = 0 with x coordinate 1. Recall that E_{0}: x^{3} + a_{0}x^{2} + b = y^{2} + xy and set a_{0} = 0, b = 1 and x = 1 to get 0 = y^{2} + y, which has two solutions y = 0 and y = 1. And thus, the point P = (1, 0) is an element of this curve. Now lets calculate the order of P. Doubling the point, using the known rules,
If P_{x} = 0, then 2P = 0.
Provided that P_{x} is not 0,
2P = R where
s = P_{x} + P_{y} / P_{x}
R_{x} = s^{2} + s + a and R_{y} = P_{x}^{2} + (s + 1)R_{x}
gives us the following for our P = (1, 0). s = 1 + 0 / 1 = 1, R_{x} = 1 + 1 + 0 = 0 and R_{y} = 1 + (1 + 1)0 = 1. In other words 2P = (0, 1). And because now the x coordinate is 0, doubling this point again results in 0 (the "point at infinity"). So, the order of this point is 4 independent of the extension degree of the field (we only used that the field characteristic is 2)!
This in turn means that the cardinality of every elliptic curve of the form E_{0}^{1}: x^{3} + a_{0}x^{2} + 1 = y^{2} + xy over , with a_{0} A_{0} is a multiple of 4, for any m. Conversely, also for any m, every elliptic curve of the form E_{1}^{1}: x^{3} + a_{1}x^{2} + 1 = y^{2} + xy over , with a_{1} A_{1} is not divisable by 4, as was shown above.
As we saw before, there will always be a solution to the general elliptic equation E: x^{3} + ax^{2} + b = y^{2} + xy. for which x 0, let us call those solutions (x, y) for now and remember that x 0. But there does not necessarily exist a solution with x = (huh, where did that come from? Well, that will become clear in a minute).
Please note that the only solution to x^{4} = b is the unique x = , because as we saw before there is only a single solution for a square root in a field with characteristic 2, and likewise there is only a single solution for .
Consider the equation
x^{3} + ax^{2} + x^{4} = y^{2} + xy
This equation can only ever be true when x = , because x and y are given to satisfy the curve equation and thus the above equation is equivalent with x^{4} = b (just add the curve equation to it).
We can rewrite this equation as x^{4} + y^{2} + x^{3} + xy + ax^{2} = 0 and then, remembering that x 0, divide both sides by x^{2} to get
x^{2} + y^{2}/x^{2} + x + y/x + a = 0
Because of the field characteristic 2, we have x^{2} + y^{2}/x^{2} = (x + y/x)^{2}. Then, with s = x + y/x, the equation becomes equivalent with
s^{2} + s + a = 0
Now looking again to the rules for point doubling, this means that adding (x, y) to itself will result in a point with x-coordinate 0, if and only if x = ! In other words, when ( , y ) is a solution of the elliptive curve then this point will have order 4 and the cardinality of the curve will be a multiple of 4 and the chosen parameter a must be element of A_{0}. However, if there is no solution with x = then there exists no point with order 4, and thus 4 does not devide the cardinality of the curve and the chosen parameter a must be element of A_{1}.
This result did not use my hypothesis that A_{0} is a hyperplane, but it also doesn't give us a formula for A_{0}. We'd still have to try every possible value of a, but at least we don't have to calculate a cardinality anymore!
Assuming that A_{0} is a hyperplane however, we can now formulate the much faster algorithm (using x = b = 1, and using the fact that a with just bit c_{j} set is equal to t^{j}):
This algorithm is fast enough for every m and will suffice to find two values of a that do not result in two isomorphic curves. Since we can always use a = 0 for E_{0} it will even suffice to find just a single j for which the above equation is not soluble.
If A_{0} is not (always) a hyperplane then in order to find all of A_{0} we'd have find all a_{0} for which there exists a solution for y^{2} + y + a_{0} = 0. Also in this case it will suffice to find just a single a_{1} for which the equation is not soluble, but - it might come in handy later when we actually known what A_{0} is, and therefore I'd like to prove that it is, in fact, a hyperplane.
In order to do that we need two new mathematical tools. The Frobenius automorphism and the trace. I dedicated a special chapter to each, so please follow those links and get yourself familiar with these expressions.
Ok, now we have the mathematical tools to actually prove that A_{0} is a hyperplane.
Recall that A_{0} exists of all elements a_{0} for which there exists a y such that y^{2} + y + a_{0} = 0. Then, using theorem 5, we can immediately conclude that those are the values for which the trace is 0. And thus
Let t^{j} be an element of A_{1}, so that Tr(t^{j}) = 1, then it is now easy to see that toggling that bit will switch between A_{0} and A_{1} independent of the value of the other bits:
And that proves that A_{0} (and A_{1}) is a hyperplane.
Our quest continues in the next chapter Cracking parameter b of the elliptic curve .