multiplicação cadeias que resulta numa constante Modulo uma potência de dois

Question

Existe um algoritmo prático que dá "cadeias de multiplicação"

Para esclarecer, o objetivo é produzir uma mudança multiplicação de um arbitrária e exata comprimento
Multiplicação cadeias de comprimento 1 são triviais.

A "cadeia de multiplicação" pode ser definido como 2 números, {início} e {multiplicador}, utilizados em 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.  

Eu gostaria de encontrar uma rotina que leva três parâmetros
1. Power of 2 | 2. Parar {constante}
3. {count} - Número de vezes que o loop irá iterar

A rotina voltaria {começo} e {multiplicador}.

O ideal é que a {} Constante valor 0 deve ser válido.

Trivial exemplo:

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

exemplo trivial:

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

A máxima {count} para uma determinada potência de 2 pode ser relativamente pequeno.
Por exemplo, 2 ^ 4 (16) parece estar limitada a uma contagem de 4

Answer 1

Aqui é um método para calcular os valores de início e multiplicador para o caso quando constante é estranho:

1. encontrar tais m impar (m = multiplicador) que fim de m módulo 2 ^ D é pelo menos de contagem, o que significa que mais pequeno n tal que m ^ n = 1 (mod 2 ^ D) é pelo menos contagem. Eu não conheço nenhuma outra maneira de encontrar tais m do que para fazer uma suposição aleatória, mas de um pouco de experimentação parece que metade dos números ímpares entre 1 e 2 ^ D têm ordem 2 ^ (D-2), que é máxima. (Eu tentei por D, no máximo, 12).

2. Computar x tais que x m * ^ = contagem de 1 (2 ^ mod D) e de arranque definida = x * constante (modificação 2 ^ D).

Tais x pode ser encontrado com "Algoritmo de Euclides estendido": Dado um e b sem divisor comum, dá-lhe x e y tal que a * x + b * y = 1. Aqui a = m ^ contagem mod 2 ^ D e b = 2 ^ D.

Editar: Se constante passa a ser ainda, você pode dividi-lo com uma potência de 2, digamos 2 ^ k, para fazer no ímpar, então fazer o descrito acima para a entrada {constante / 2 ^ k, contagem, 2 ^ (Dk)} e finalmente voltar {começar * 2 ^ k,} multiplicador.

Answer 2

Você está pedindo soluções não triviais à equação modular seguinte:

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

onde

• s é a constante de iniciar
• m é o multiplicador
• N é o número de iterações (dado pelo problema)
• C é a constante final (determinado pelo problema)
• D é o expoente da potência de 2 (dada pelo problema)

Tenha um olhar em Euler do teorema na teoria dos números.

Para uma arbitrária estranho m (que é privilegiada, com 2 ^ D), você tem

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

assim

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

e, finalmente,

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

Tome

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

e está feito. A função phi de Euler de uma potência de 2 é metade que o poder de 2, ou seja:

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

Exemplo . Vamos

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

Escolha arbitrariamente m = 7 (ímpar), e computar

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

Agora

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

Answer 3

Por isso não iria satisfazer os requisitos?

start = constant;
multiplier = 1;

Update: Vejo agora que o número de loops é um dos parâmetros de entrada. Parece que este problema é um caso especial de, ou pelo menos relacionado, o logaritmo discreto problema.