Q1: generating a random primitive binary polynomial

Yes, the best known way to generate a random primitive 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$$; and test if it is primitive; until finding a primitive one.

For some $$p$$, it is possible to find a trinomial (see the list of all primitive trinomials for $$p\le400$$); for other $$p$$, at least a pentanomial is necessary (see this list of one primitive pentanomial with about equally spaced coefficients for each $$p\le660$$); and it is conjectured always sufficient (see this answer).

The most involved part is testing primitiveness. We can use that a LFSR using a polynomial of degree $$p$$ has period $$2^p-1$$ starting from some non-zero state if and only if its polynomial is primitive.

• We compute the state of the LFSR after $$2^p-1$$ steps starting from $$1$$ (there's an easy $$\mathcal O(p^3)$$ algorithm for that), and check that is $$1$$ (otherwise, the polynomial is not primitive and we stop).
• After that check, it only remains to check that the actual period is not smaller. A deterministic algorithm uses that the period must divide $$2^p-1$$. So, for each prime $$q$$ dividing $$2^p-1$$, we compute the state of the LFSR after $$(2^p-1)/q$$ steps starting from $$1$$, and check that's not $$1$$ (otherwise, the polynomial is not primitive and we stop).

Factoring $$2^p-1$$ is difficult, but The Cunningham Project can come to the rescue with the factorization of all $$2^p-1$$ for odd $$p<991$$, and then some. I think there is a randomized algorithm that does not require factoring $$2^p-1$$, but I fail to find a reference.

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.

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 2nd degree equation, which can be solved, and that saves time compared to trying all values of $$y$$.

Q4: Except for small $$p$$, Schoof's algorithm and the likes is the way to go; I can't help for this.