Picking a bounded uniform random value in GF(2^M) without exponentiation or tables

Question

I am looking for a way to uniformly choose values in GF(2^M) between two bounds.

GF(2^M) is a Galois Field - See GF(4) as defined on this page - http://www.math.umbc.edu/~campbell/Math413Spr09/Notes/12-13_Finite_Fields.html
From a technical, non-math perspective, this is most similar to CRC operations.

For example:

ulong gf2step( ulong x, int bits, ulong p ) 
{  
    x = x << 1;   // "multiply" by x 
    if ( x >= (1 << bits)) x = x ^ p;   
    return x;
}

Expanding the example from below:

  12 is '1100  
 '1100 shifted left by 1 becomes `11000. Since bit 4 is set, xor with `10011 (p). 
  Next is `1011 or 11.

Similarly,

  9 is '1001
 '1001 shifted left by 1 becomes `10010. Since bit 4 is set, xor with `10011 (p). 
  Next is `0001.

My obvious method is to start with the integer exponents corresponding to the bounds, pick a random exponent between those and generate the value from that.

However, this has two problems --
1. Given arbitrary bounds, I can't find the corresponding integer exponent..
2. This will be repeated many, many times, so I am concerned about exponentiation speed.

Example:

 int gf2random( ulong low, ulong high, ulong p); 

 gf2random( 12, 13, 19) should return evenly from the set {12, 11,5,10,7,14,15, 13}
 gf2random( 9, 1, 19)  should return either 9 or 1

I can step the values in GF(2^M) fairly easily - but I'm not sure how to avoid overshooting the upper bound.

---

Does it simplify the problem if the low bound was always '1' ?

Answer 1

It doesn't seem like you're referring to an actual Galois field. First of all, GF(2^M) will have 2^M elements, and performing an xor with M won't accomplish this. Second of all, the additive group is not cyclic, which means that you can't actually "step" through the values in a conventional way. From the Wikipedia page,

The underlying additive group of the field (Z/2Z)[T]/(T^2+T+1) of size 4 is not cyclic but rather is isomorphic to the Klein four-group, (Z/2Z)^2.

You could pick a random value by taking a random bit string. Or, instead of GF(2^M), you might just want GF(p), which is cyclic and acts like the easily understood integers mod p.

Also I admit that I'm not a mathematician or particularly well-versed in Galois fields - feel free to correct me.

Answer 2

I'm not completely sure I understand your question, so I'll try to reformulate it. You are given a finite field GF(2^M) a generator g of the multiplicative group and two elements g^a and g^b. You may or may not know the exponents a and b. The question is to uniformly select elements g^c where a<= c < b. Since you say that tables are not an option I'd assume you want to work with a rather large M. Hope I got this right.

If M is large then discrete logarithm is hard to compute. Hence if you don't know a and b upfront you'll not be able to find them. The difficulty of the discrete logarithm also implies that given a random element h in GF(2^M) it is hard to decide whether h is one of the valid elements g^c, because if you had such an algorithm to make this kind of decision then this algorithm could be used to solve discrete logarithms. In particular if you have two elements g^a and g^c and don't know either a or c then you can't easily decide whether c < a or not.

From the comments above I'd expect that your problem is not easily solvable, even though what I wrote is not a proof. It might be helpful, if you also added a bigger picture of the problem that you want to solve. Maybe there is some other way to generate the random elements.

Answer 3

Note that exponentiation is the easy part -- the hard part is the discrete log operation of finding the exponents.

Exponentiation is fast by repeated squaring. (a^32 = (a^2)^16 = (a^4)^8 = (a^8)^4 = (a^16)^2 = (a^32). You could save some time by precomputing these values.

If you take in the exponent as the bound input (as in, if you want something between g^m and g^n, your inputs are m and n) that's pretty fast. Otherwise, I'm pretty sure it's as hard as discrete log on GF(2^M) -- to find n of a^n you could build a chain of O(n) elements with decreasing exponent and then build your way back up to n.