Implementation of ECC over binary field 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 :


The user will enter a prime number $m$, which will serve as the order of the binary field as $2^m$.
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?



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$ ?



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?



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)
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?



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.
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&lt;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.