algorithm - 在GF(2 ^ M)中选取有界的均匀随机值而无需取幂或表

我正在寻找一种方法，在两个边界之间统一地选择gf（2^m）中的值。
gf（2^m）是伽罗瓦场-见本页定义的gf（4）-http://www.math.umbc.edu/~campbell/Math413Spr09/Notes/12-13_Finite_Fields.html
从技术和非数学的角度来看，这与crc操作最为相似。
例如：

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

从下面展开示例：

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

同样地，

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

我的明显方法是从与边界对应的整数指数开始，在它们之间选择一个随机指数并从中生成值。
但是，这有两个问题--
一。给定任意边界，我找不到相应的整数指数。。
2.这会重复很多次，所以我担心指数化速度。
例子：

 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

我可以很容易地将GF（2^M）中的值步进-但我不确定如何避免超出上限。
如果下限总是'1'，这个问题会简单化吗？

最佳答案

我不完全确定我是否理解你的问题，所以我会努力重新提出。
给你一个有限域gf（2^m），一个乘法群的生成器g和两个元素g^a和g^b。你可能知道也可能不知道指数a和b。问题是在a<=c如果M很大，那么离散对数很难计算因此，如果你事先不知道a和b，你就找不到它们离散对数的困难还意味着在gf（2^m）中给定一个随机元素h，很难确定h是否是有效元素g^c之一，因为如果有这样的算法来做这种决定，那么这个算法可以用来求解离散对数。特别是如果你有两个元素g^a和g^c，并且不知道a或c，那么你就不能轻易地决定c是否从上面的评论来看，我认为你的问题不容易解决，即使我写的不是证据。如果你还对你想解决的问题有了更全面的了解，这可能会有帮助也许还有其他方法来生成随机元素。