Implementation of ECC over binary field

Question

I am supposed to implement ECC over binary field (in C++) for equations of the type - $y^2 + xy = x^3 + ax + b$, as my project. I wish to include the following features :

1. The user will enter a prime number $m$, which will serve as the order of the binary field as $2^m$.
2. For the given $m$, the irreducible polynomial will be generated.

Q1. AFAIK, there is no method to efficiently find a random irreducible polynomial. The only way is to pick a random polynomial and check whether it is irreducible or not. (The polynomial can be no more than pentanomial, and trinomial in some cases) Am I thinking the right way?

3. The coefficients $a$ and $b$ will be generated.

Q2. Can I use random number generator (with appropriate constraints) to generate $a$ and $b$ instead of producing it from a Seed $S$ ? Also, I have seen both Seed $S$ and the parameter $b$ being mentioned. What is the purpose to write both the things when $S$ is sufficient to generate $b$ ?

4. Various points that lie on the curve will be listed.

Q3. To generate all the points, put $x=0, 1, 2 ...m-1$ and solve for $y$ for equations of the type : $y^2 + ky = l$. How to find the square root in such a scenario? Is there any better way to generate all the points?

5. Schoof's algorithm and the likes will be demonstrated to count all the points lying on the elliptic curve. (Though all the points have already been generated, but presenting an algorithm will be an added advantage)
6. A suitable base point $P$ will be chosen such that it has reasonably low cofactor.

Q4. To find such a point, the order of each and every point should be found out. The only way that I can think of is : Pick a point $Q$. Find $2Q, 3Q$ until the points start repeating. Hence, one gets the order. Do so for all the points while maintaining the maximum order. Is there any better way to achieve it?

7. Finally an El-Gamal and/or Diffie Hellman analogous of ECC over binary field will be presented.

I would like to get clarification on above questions based on the mentioned scenarios. As of now, I don't have sufficient knowledge of ECC so it is pretty much possible that I have asked some nonsensical questions and I am really very sorry for it. Please feel free to share your ideas on these/any other features so as to make the project more worthy.

Answer 1

Q1.

Here's an algorithm to test irreducibility of a univariate non-constant monic polynomial over a finite field $\mathbb F_q$. (I learnt this from von zur Gathen and Gerhard's Modern Computer Algebra.)

Let $q=p^e$ be a prime power. A generalization of Fermat's little theorem states that for all $d\geq1$, $$ x^{q^d}-x \;=\;\prod \{\,f\in\mathbb F_q[x]\text{ monic and irreducible with }\deg f\mid d\,\} \text. $$

Therefore, a monic polynomial $f\in\mathbb F_q[x]$ is irreducible if and only if $\gcd(x^{q^d}-x,f)=1$ for all $d\in\{1,\dots,n-1\}$. This immediately yields an algorithm for testing irreducibility; it requires $\mathcal O(n^3\log(nq))$ elementary arithmetic operations when implemented correctly.

5. If you are interested in a high-level description of Schoof's algorithm, have a look at this post of mine. (In particular, note that it is not exactly trivial to implement.)

Q4.

Suppose you have a prime factorization of the curve $E$'s group order (perhaps obtained using Schoof's algorithm followed by a factoring algorithm), say $$n=\lvert E\rvert=\prod_{i=1}^k p_i^{e_i} \text.$$ Note that in any finite group, an element's order divides the group order. Hence you can easily check whether a point $P\in E$ is a generator by computing the powers $[n/p_i]P$: If one of them is the identity, then $P$ is not a generator (since its order must then be a divisor of $n/p_i<n$), otherwise it is. Now one can show (using the classification of finite abelian groups) that a randomly chosen group element is a generator with probability at least $$ \prod_{i=1}^k\left(1-\frac1{p_i}\right)^{e_i} \text, $$ which should be "large enough" for practical purposes (when $n$ has few small prime divisors), hence you can find a generator by randomly picking points on the curve until you get one.

Answer 2

Q1: generating a random irreducible binary polynomial

Yes, the best known way to generate a random irreducible binary polynomial of a given degree $p$ is to randomly generate a binary polynomial of degree $p$ with an odd number of terms, including $x^p$ and $1$ (perhaps: not a polynomial among those previously considered; this helps if restricting to polynomials with low number of terms); and test if this polynomial is irreducible; until finding an irreducible one.

For some $p$, it is possible to find a trinomial; for other $p$, at least a pentanomial is necessary (see this answer for why this is conjectured sufficient even if we had the stricter criteria of requiring the polynomial to be primitive).

Some parameter generation methods (including that in FIPS 186-2 for polynomial basis) do not use a random irreducible binary polynomial of the least possible degree as the question considers, but rather a primitive polynomial of the specified degree with the least possible number of terms, and as a tie-breaker between any two distinct primitive polynomials of the same degree and same number of terms, the one not containing the highest degree coefficient appearing in one but not in the other (which defines a proper order relation).

The most involved part is testing irreducibility. The other answer tells how to do this. Jörg Arndt's tables of mathematical data will provide test cases for small $p$. A former version of this answer discussed testing for primitive polynomials.

---

Q2: Yes you can use a random number generator to generate $a$ and $b$; make that a cryptographically strong pseudo-random generator seeded by $S$, and repeat generating $a$ and $b$ until they meet constraints you have, and you should be done. I fail to find a a reference for a standard method to do this for the kind of curve you consider.

Q3: Except for small $p$, you do not want to generate all points on the curve; there are in the order of $\mathcal O(2^p)$, that's too much. For small $p$, you can indeed generate all points, and yes for a given $x$ finding the corresponding value(s) of $y$ reduces to a 2^nd degree equation, which can be solved, and that saves time compared to trying all values of $y$.

In order to determine the number of points on the curve, except for small $p$, Schoof's algorithm and the likes is the way to go; I can't help for this.

Q4: is nicely treated in the other answer.