Note: I have now answered this by my own research and can generate random fields up to G(2^9) in reasonable time. I would need to find more speedups for larger fields. At this time G(2^8) takes a few seconds and G(2^9) takes a few hours (it varies widely depending on my generation options). If anyone is interested I will expand upon the process.
I would like to create random Galois fields over $G(2^8)$ with operators $(\otimes, \oplus)$ where $\oplus$ is the standard XOR and $\otimes$ is a randomly defined multiplicative operator. I have an algorithm in mind, but I suspect that it will not generate all possible fields. I know that all such fields are isomorphic, but differences are crucial! Especially for cryptography.
I know that fields have been defined (e.g. Rijndael) using polynomials but again doubt that all possible fields can be reached that way. At least not easily. Any suggestions?
I should explain what I want to do in more detail and the reasons. I know that all finite fields of a given size are isomorphic. That means that there is effectively only "one" field. However, they are NOT the same from a different standpoint. There has been a lot of work to find fields that have minimal implementation complexity. Mainly because of the obsession with implementing them entirely in very small hardware (minimum gates).
However, from an encryption standpoint, a very high level of complexity is desired. You want x * y to be highly non-affine. Minimum complexity is not optimum here. So the simple irreducible polynomials that encryption products are using are not suitable. They are explictly choosen to have minimum complexity. It is difficult to determine the complexity of a field from the polynomial. But, by generating random fields the odds of getting a highly complex field are very good. And it is a good way to make the encryption hard to break becuase the properties of a specific field cannot be directly used in cyptoanalysis.
So, yes the fields are are all the same. But (as an engineer would say) practice and theory are different. And it is that difference that is important.
My algorithm above is not quite correct. It turns out that the sub-algorithm for building the basis products is not right. I have solved some of it, but there are dependencies that I haven't identified yet. I don't know if that approach will work or not.
However, other approaches may be just as good. Since finite fields of the same size are isomorphic, an alternative is to build a random isomorphism. That appears to have a lot of the same problems.
So I am still looking for insights or suggestions. Thanks.
Poncho - you are the only one to answer so far that appears to have a clue about this (I am new to crypto.stackexchange and don't yet have the points to either comment or chat). I am unfortunately (for the time) stuck using a library computer in small town every couple of days and my reference library is not available (and it has been 40 years since abstract algebra in college which didn't even cover this area). I have picked up and read several books in the area (abstract algebra and finite fields), but none of them address this topic or even something close enough. They just address the standard theory, which except for information on bases is not very useful. I have not been able to find any online references on this direct topic. Do you have any suggestions?
Why the 8 4 3 2 0 polynomial? Or is that just the first one you picked? As far as generating a random field, generating a random bais for g01, g02, ..., g80 works fine. Then I only need to generate another random basis for g02, g03, ... g81. There are some constraints there that I don't currently have enough information to use to directly constrain the random generator, but brute force would work. I actually think that the main basis completely constrains the g02, g03, ... basis (the first row / column in the basis multiplication table - that sufficies to ensure distribution and all of the other properties) but I haven't determined an efficient way to do that. Possibly a genetic algorithm. However, I would like to be more intelligent about the process. If you are correct, I could create the basis, determine the affine mapping from the field generated by the 8 4 3 1 0 polynomial and then create the g02, g03, ... basis by applying the affine mapping. If that does, in fact, work then simply generating a random affine mapping should also work. That is trivial - just create a basis to ensure that the matrix is invertable and add a random vector.
I don't know if it will give a better non-affine result, but I suspect that it would (this is research!). Otherwise there would be no point in using different polynomials to obtain "simple" implementations. I simply want to do the opposite of "simple"!