catene di moltiplicazione che danno come risultato un modulo costante una potenza di 2

Question

Esiste un algoritmo pratico che fornisce " catene di moltiplicazione "

Per chiarire, l'obiettivo è produrre una variazione di moltiplicazione di una lunghezza arbitraria ed esatta
Le catene di moltiplicazione di lunghezza 1 sono banali.

A "catena di moltiplicazione" sarebbe definito come 2 numeri, {start} e {moltiplicatore}, usato nel codice:

 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.  

Vorrei trovare una routine che accetta tre parametri
     1. Potenza di 2
     2. Arresto {costante}
     3. {count}: numero di volte in cui il ciclo verrà ripetuto

La routine restituisce {start} e {moltiplicatore}.

Idealmente, un valore {Costante} di 0 dovrebbe essere valido.

Esempio di prova:

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

Esempio non banale:

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

Il massimo {count} per una determinata potenza di 2 può essere abbastanza piccolo.
    Ad esempio, 2 ^ 4 (16) sembra essere limitato a un conteggio di 4

Answer 1

Ecco un metodo per calcolare i valori per start e moltiplicatore per il caso in cui costante è dispari:

1. Trova tale m dispari (m = moltiplicatore) che l'ordine di m modulo 2 ^ D è almeno il conteggio, il che significa che il più piccolo n tale che m ^ n = 1 (mod 2 ^ D) è almeno il conteggio. Non conosco altro modo per trovare tale m se non fare un'ipotesi casuale, ma da un piccolo esperimento sembra che la metà dei numeri dispari tra 1 e 2 ^ D abbia un ordine 2 ^ (D-2) che è massimo. (Ho provato per D al massimo 12.)

2. Calcola x in modo tale che x * m ^ count = 1 (mod 2 ^ D) e imposta start = x * costante (mod 2 ^ D).

Tale x può essere trovato con "l'algoritmo euclideo esteso": dato aeb con nessun divisore comune, ti dà xey tale che a * x + b * y = 1. Qui a = m ^ count mod 2 ^ D e b = 2 ^ D.

modifica: se la costante sembra essere pari, puoi dividerla con una potenza di 2, diciamo 2 ^ k, per rendere dispari, quindi fai quanto sopra per input {costante / 2 ^ k, count, 2 ^ (Dk)} e infine restituisce {start * 2 ^ k, moltiplicatore}.

Answer 2

Stai chiedendo soluzioni non banali alla seguente equazione modulare:

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

dove

• s è la costante iniziale
• m è il moltiplicatore
• N è il numero di iterazioni (fornite dal problema)
• C è la costante finale (data dal problema)
• D è l'esponente della potenza di 2 (data dal problema)

Dai un'occhiata a Teorema di Eulero nella teoria dei numeri.

Per un dispari arbitrario m (che è primo con 2 ^ D), hai

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

così

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

e infine

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

Prendere

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

e il gioco è fatto. La la funzione phi di Euler di una potenza di 2 è metà quel potere di 2, cioè:

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

Esempio . Lasciate

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

Scegli arbitrariamente m = 7 (dispari) e calcola

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

Ora

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

Answer 3

Perché questo non soddisfa i requisiti?

start = constant;
multiplier = 1;

Aggiornamento: vedo ora che il numero di loop è uno dei parametri di input. Sembra che questo problema sia un caso speciale o almeno correlato al logaritmo discreto problema.