chaînes de multiplication qui résultent en un modulo constant une puissance de 2

Question

Existe-t-il un algorithme pratique qui donne les "chaînes de multiplication"

Pour clarifier, l'objectif est de produire un changement de multiplication d'une longueur arbitraire et exacte

Les chaînes de multiplication de longueur 1 sont triviales.

Une "chaîne de multiplication" serait défini comme 2 nombres, {start} et {multiplier}, utilisés dans le code:

 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.  

J'aimerais trouver une routine qui prend trois paramètres
     1. Puissance de 2
     2. Arrêt {constant}
     3. {count} - Nombre de fois que la boucle itérera

La routine renverrait {début} et {multiplicateur}.

Idéalement, une valeur {constante} de 0 doit être valide.

Exemple trivial:

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

Exemple non déterminant:

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

Le {nombre} maximum pour une puissance donnée de 2 peut être assez petit.
    Par exemple, 2 ^ 4 (16) semble être limité à un nombre de 4

Answer 1

Voici une méthode pour calculer les valeurs de début et de multiplicateur pour le cas où la constante est impaire:

1. Trouvez un m impair (m = multiplicateur) tel que l'ordre de m modulo 2 ^ D soit au moins compte, ce qui signifie que n le plus petit tel que m ^ n = 1 (mod 2 ^ D) soit au moins compte. Je ne connais pas d'autre moyen de trouver un tel m que de faire une supposition aléatoire, mais d'après quelques expériences, il semble que la moitié des nombres impairs entre 1 et 2 ^ D ait l'ordre 2 ^ (D-2), qui est maximal. (J'ai essayé D au plus 12.)

2. Calculez x tel que x * m ^ compte = 1 (mod 2 ^ D) et définissez start = x * constant (mod 2 ^ D).

Ce x peut être trouvé avec "l'algorithme euclidien étendu": étant donné a et b sans diviseur commun, il vous donne x et y tels que a * x + b * y = 1. Ici a = m ^ compte mod 2 ^ D et b = 2 ^ D.

modifier: Si constante se trouve être pair, vous pouvez le diviser par une puissance de 2, disons 2 ^ k, pour rendre impair, puis procédez comme indiqué ci-dessus pour l'entrée {constant / 2 ^ k, count, 2 ^ (Dk)} et finalement retourne {début * 2 ^ k, multiplicateur}.

Answer 2

Vous demandez des solutions non triviales à l'équation modulaire suivante:

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

où

• s est la constante de départ
• m est le multiplicateur
• N est le nombre d'itérations (donné par le problème)
• C est la constante finale (donnée par le problème)
• D est l'exposant de la puissance de 2 (donnée par le problème)

Consultez le le théorème d'Euler dans la théorie des nombres.

Pour un impair m (qui est premier avec 2 ^ D), vous avez

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

donc

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

et enfin

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

Prenez

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

et vous avez terminé. La La fonction phi d'Euler d'une puissance de 2 est la moitié cette puissance de 2, à savoir:

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

Exemple . Laissez

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

Choisissez arbitrairement m = 7 (impair) et calculez

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

Maintenant

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

Answer 3

Pourquoi cela ne satisferait-il pas aux exigences?

start = constant;
multiplier = 1;

Mise à jour: Je vois maintenant que le nombre de boucles est l’un des paramètres d’entrée. Il semble que ce problème soit un cas particulier, ou du moins lié à, du logarithme discret . problème.