цепи умножения, которые приводят к постоянной по модулю степени 2 - PullRequest
Новая
       28

цепи умножения, которые приводят к постоянной по модулю степени 2

2 голосов
/ 01 ноября 2008

Есть ли практический алгоритм, который дает "цепочки умножения"

Чтобы уточнить, цель состоит в том, чтобы произвести изменение умножения на произвольной и точной длины
Цепочки умножения длины 1 тривиальны.

«Цепочка умножения» будет определяться как 2 числа {start} и {множитель}, используемые в коде: 

 Given a pointer to array of size [{count}]   // count is a parameter
 a = start;
 do 
 {
      a = a * multiplier;  // Really: a = (a * multiplier) MOD (power of 2
      *(pointer++) = a;   
 }
 while (a != {constant} )
 // Postcondition:  all {count} entries are filled.

Я бы хотел найти подпрограмму, которая принимает три параметра
1. Мощность 2
2. Остановка {постоянная}
3. {count} - количество итераций цикла

Подпрограмма вернет {start} и {множитель}.

В идеале значение {Константа} должно быть 0.

Тривиальный пример: 

power of 2 = 256  
stopping constant = 7
number of times for the loop = 1  
returns {7,1}

Нетривиальный пример: 

power of 2 = 256  
stopping constant = 1
number of times for the loop = 49
returns {25, 19}

Максимальный {count} для данной степени 2 может быть довольно маленьким.
Например, 2 ^ 4 (16), кажется, ограничен счетом 4

Ответы [ 3 ]

5 голосов
/ 01 ноября 2008

Вы запрашиваете нетривиальные решения для следующего модульного уравнения: 

s * m^N = C (mod 2^D)

, где

  • s - начальная константа
  • м - это множитель
  • N - количество итераций (задается задачей)
  • C - конечная константа (заданная задачей)
  • D - показатель степени 2 (задается задачей)

Взгляните на теорему Эйлера в теории чисел.

Для произвольного нечетного m (который прост с 2 ^ D), у вас есть 

m^phi(2^D) = 1 (mod 2^D)

Таким образом, 

C * m^phi(2^D) = C (mod 2^D)

и, наконец, 

C * m^(phi(2^D)-N) * m^N = C (mod 2^D)

Take 

s = C * m^(phi(2^D)-N)

и все готово. Функция Эйлера степени 2 равна половине этой степени 2, т. Е .:

phi(2^D) = 2^(D-1)

Пример . Пусть

  • N = 5
  • C = 3
  • 2 ^ D = 16
  • фи (16) = 8

Выберите произвольно m = 7 (нечетно) и вычислите 

3 * 7^(8-5) = 1029
s = 1029 mod 16 = 5

Теперь 

s * m^N = 5 * 7^5 = 84035
84035 mod 16 = 3 == C
2 голосов
/ 01 ноября 2008

Вот метод для вычисления значений для начала и множителя для случая, когда константа нечетна:

  1. Найдите такое нечетное m (m = множитель), чтобы порядок m по модулю 2 ^ D был, по крайней мере, счетчиком, а это означает, что наименьшее n такое, что m ^ n = 1 (mod 2 ^ D), - по крайней мере, счет Я не знаю другого способа найти такое m, кроме как сделать случайное предположение, но из небольшого эксперимента кажется, что половина нечетных чисел от 1 до 2 ^ D имеет порядок 2 ^ (D-2), который является максимальным. (Я пытался на D максимум 12).

  2. Вычислите x так, чтобы x * m ^ count = 1 (mod 2 ^ D) и установили start = x * constant (mod 2 ^ D).

Такой x может быть найден с помощью "расширенного евклидова алгоритма": если a и b не имеют общего делителя, он дает вам x и y такие, что a * x + b * y = 1. Здесь a = m ^ count mod 2 ^ D и b = 2 ^ D.

edit: Если константа оказывается четной, вы можете разделить ее на степень 2, скажем, 2 ^ k, чтобы сделать нечетным, а затем сделать то же самое для ввода {constant / 2 ^ k , считать, 2 ^ (Dk)} и, наконец, вернуть {start * 2 ^ k, множитель}.

1 голос
/ 01 ноября 2008

Почему это не удовлетворяет требованиям? 

start = constant;
multiplier = 1;

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

...