Cadenas de multiplicación que dan como resultado un módulo constante de una potencia de 2.

Question

¿Existe un algoritmo práctico que proporcione " cadenas de multiplicación "

Para aclarar, el objetivo es producir un cambio de multiplicación de una longitud arbitraria y exacta
Las cadenas de multiplicación de longitud 1 son triviales.

Una " cadena de multiplicación " se definiría como 2 números, {inicio} y {multiplicador}, utilizados en el código:

 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.  

Me gustaría encontrar una rutina que tome tres parámetros
     1. Potencia de 2
     2. Deteniendo {constante}
     3. {count}: número de veces que el bucle se repetirá

La rutina devolvería {inicio} y {multiplicador}.

Idealmente, un valor {Constante} de 0 debería ser válido.

Ejemplo trivial:

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

Ejemplo no trivial:

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

El máximo {count} para una potencia dada de 2 puede ser bastante pequeño.
    Por ejemplo, 2 ^ 4 (16) parece estar limitado a un conteo de 4

Answer 1

Aquí hay un método para calcular los valores de inicio y multiplicador para el caso cuando la constante es impar:

1. Encuentre tal m impar (m = multiplicador) que el orden de m módulo 2 ^ D sea al menos cuenta, lo que significa que la n más pequeña tal que m ^ n = 1 (mod 2 ^ D) es al menos cuenta. No conozco otra forma de encontrar tal m que hacer una conjetura aleatoria, pero a partir de una pequeña experimentación parece que la mitad de los números impares entre 1 y 2 ^ D tienen un orden 2 ^ (D-2) que es el máximo. (Lo intenté para D a lo sumo 12.)

2. Calcule x de tal manera que x * m ^ count = 1 (mod 2 ^ D) y establezca start = x * constant (mod 2 ^ D).

Dicha x se puede encontrar con " algoritmo euclidiano extendido " ;: Dado a y b sin un divisor común, te da x e y tal que a * x + b * y = 1. Aquí a = m ^ recuento mod 2 ^ D y b = 2 ^ D.

editar: si la constante es par, puedes dividirla con una potencia de 2, digamos 2 ^ k, para hacer impar, luego haz lo anterior para la entrada {constante / 2 ^ k, cuenta, 2 ^ (Dk)} y finalmente devuelve {inicio * 2 ^ k, multiplicador}.

Answer 2

Solicita soluciones no triviales a la siguiente ecuación modular:

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

donde

• s es la constante de inicio
• m es el multiplicador
• N es el número de iteraciones (dado por el problema)
• C es la constante final (dada por el problema)
• D es el exponente de la potencia de 2 (dado por el problema)

Echa un vistazo a Teorema de Euler en teoría de números.

Para un impar m arbitrario (que es primo con 2 ^ D), tienes

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

por lo tanto

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

y finalmente

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

Tomar

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

y ya está. La función de phi de Euler de una potencia de 2 es la mitad ese poder de 2, es decir:

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

Ejemplo . Vamos

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

Elija arbitrariamente m = 7 (impar) y calcule

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

Ahora

s * m^N = 5 * 7^5 = 84035
84035 mod 16 = 3 == C

Answer 3

¿Por qué esto no cumple con los requisitos?

start = constant;
multiplier = 1;

Actualización: veo que el número de bucles es uno de los parámetros de entrada. Parece que este problema es un caso especial de, o al menos relacionado con, el logaritmo discreto problema.