Выбор ограниченного равномерного случайного значения в GF (2 ^ M) без возведения в степень или таблиц - PullRequest
Новая
       10

Выбор ограниченного равномерного случайного значения в GF (2 ^ M) без возведения в степень или таблиц

1 голос
/ 10 июня 2009

Я ищу способ равномерного выбора значений в 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.

Мой очевидный метод - начать с целочисленных показателей, соответствующих границам, выбрать случайный показатель между ними и сгенерировать из этого значение.

Однако у этого есть две проблемы -
1. Учитывая произвольные границы, я не могу найти соответствующий целочисленный показатель ..
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»?

Ответы [ 3 ]

2 голосов
/ 10 июня 2009

Я не совсем уверен, что понимаю ваш вопрос, поэтому постараюсь переформулировать его. Вам дано конечное поле GF (2 ^ M), генератор g мультипликативной группы и два элемента g ^ a и g ^ b. Вы можете или не можете знать показатели a и b. Вопрос состоит в том, чтобы равномерно выбирать элементы g ^ c, где a <= c <b. Поскольку вы говорите, что таблицы - не вариант, я предполагаю, что вы хотите работать с довольно большим M. Надеюсь, я понял это правильно. </p>

Если M большое, то дискретный логарифм трудно вычислить. Следовательно, если вы не знаете a и b заранее, вы не сможете их найти. Сложность дискретного логарифма также подразумевает, что, учитывая случайный элемент h в GF (2 ^ M), трудно решить, является ли h одним из допустимых элементов g ^ c, потому что, если у вас был такой алгоритм, чтобы сделать такой Решение затем этот алгоритм может быть использован для решения дискретных логарифмов. В частности, если у вас есть два элемента g ^ a и g ^ c и вы не знаете ни a, ни c, то вы не можете легко решить, является ли c

Исходя из комментариев, приведенных выше, я ожидаю, что вашу проблему нелегко решить, хотя то, что я написал, не является доказательством. Это может быть полезно, если вы также добавили более широкую картину проблемы, которую хотите решить. Возможно, есть какой-то другой способ генерирования случайных элементов.

0 голосов
/ 12 июня 2009

Обратите внимание, что возведение в степень - это простая часть, а сложная часть - это дискретная логарифмическая операция поиска показателей.

Экспонирование выполняется быстро при повторном возведении в квадрат. (a ^ 32 = (a ^ 2) ^ 16 = (a ^ 4) ^ 8 = (a ^ 8) ^ 4 = (a ^ 16) ^ 2 = (a ^ 32). Вы можете сэкономить некоторое время, предварительно вычислив эти значения.

Если вы возьмете экспоненту в качестве ограниченного входа (например, если вы хотите что-то между g ^ m и g ^ n, ваши входы будут m и n), это довольно быстро. В противном случае, я почти уверен, что это так же сложно, как дискретный вход в GF (2 ^ M) - чтобы найти n из ^ n, вы могли бы построить цепочку из O (n) элементов с уменьшающимся показателем, а затем вернуться обратно по номеру

0 голосов
/ 10 июня 2009

Не похоже, что вы имеете в виду фактическое поле Галуа. Прежде всего, GF (2 ^ M) будет иметь 2 ^ M элементов, и выполнение xor с M не достигнет этого. Во-вторых, аддитивная группа не является циклической, что означает, что вы не можете «шагнуть» через значения обычным способом. Со страницы Википедии ,

Основная аддитивная группа поля (Z / 2Z) [T] / (T ^ 2 + T + 1) размера 4 не является циклической, а скорее изоморфна четырехгруппе Клейна, (Z / 2Z) ^ 2.

Вы можете выбрать случайное значение, взяв случайную строку битов. Или вместо GF (2 ^ M) вы можете просто захотеть GF (p), который является циклическим и действует как легко понимаемый мод целых чисел p.

Также я признаю, что я не математик и не особенно разбираюсь в полях Галуа - не стесняйтесь меня поправлять.

...