Elliptic curve embedding degrees

I've finally got around to reading [Hitt], which has raised a couple of
interesting questions in my mind.

Let p be a prime, and let q = p^m; let E/GF(q) be an elliptic curve
with #E(GF(q)) = r h, where r is prime. Let k and l be the smallest
positive integers such that p^l = q^k = 1 (mod r). Then (a) r | p^l - 1
and r | q^k - 1, and (b) k m = lcm(m, l).

[Hitt] explains that the Weil or Tate pairing on E maps onto the r-order
subgroup of GF(p^l), which will be a smaller field than GF(q^k), if m
doesn't divide l. She doesn't explain how to actually do this
computation. While I'm really not an expert at this stuff, the best way
I can see of making this actually work is to do the pairing computation
(using Miller's algorithm, say) in GF(q^k) as usual, and then use the
fact that, since l divides m k, GF(q^k) is an extension field of GF(p^l)
and hence forms a vector space over it; so you find an appropriate
change-of-basis matrix, apply it, and since the result of your pairing
is in the r-order subgroup of GF(q^k)^*, one should find that it's an
element of the subgroup GF(p^l)^*, so you throw away the zero entries in
your vector and proceed with index calculus.

I can't see a slicker way of doing this, since the computations in
GF(q^k) to calculate the pairing involve the coordinates of one of the
operands of the pairing, and while they're in GF(q), they may not be in
GF(p^l). Any suggestions would be appreciated.

The other question is simpler. I've found a lot of literature on the
subject of finding pairing-friendly ordinary elliptic curves over prime
fields, but none on finding such curves over /binary/ fields. The
techniques described in, say, [FST], don't work in this case because
powers of two are considerably sparser than primes! Maybe I'll just
have to mess with binary supersingular curves.

[FST] D. Freeman, M. Scott, E. Teske, A Taxonomy of Pairing-Friendly
Elliptic Curves;
http://citeseer.ist.psu.edu/freeman06taxonomy.html

[Hitt] L. Hitt, On an improved definition of embedding degree;
http://eprint.iacr.org/2006/415

-- [mdw]
.