Crittografia RSA subtask 3-4-5

Aiuto
7

L’algoritmo per farlo è molto noto e non è nemmeno troppo costruttivo ragionarci invece che impararlo, quindi è più funzionale spiegarlo direttamente.
Puoi farlo principalmente in 2 modi:

Metodo 1:

Stai cercando di calcolare a^b puoi sfruttare il fatto che a^b=a^{\lceil b/2 \rceil} * a^{\lfloor b/2 \rfloor} considerando che a^{\lceil b/2 \rceil} = a^{\lfloor b/2 \rfloor} per b pari e a^{\lceil b/2 \rceil} = a^{\lfloor b/2 \rfloor} * b per b dispari puoi notare come per ottenere a^b basta a^{\lfloor b/2 \rfloor} ed avendo come casi base a^0 = 1, a^1 = a allora ti basteranno log_2(b) chiamate per trovare a^b. Inoltre l’unica operazione utilizzata è la moltiplicazione che è compatibile con il modulo, infatti (a*b) MOD x = ((a MOD x)*(b MOD x)) MOD x

codice:

int fast_pow(int base, int esp, int MOD) {
	if(esp == 0)
		return 1;
	if(esp == 1)
		return base % MOD;
	long long half = fast_pow(base, esp / 2, MOD);
	long long ans = (half * half) % MOD;
	if(esp % 2)
		ans = (ans * base) % MOD;
	return ans;
}

Metodo 2:

Consideriamo la rappresentazione in base 2 di b= d_0*2^0+d_1*2^1+d_2*2^2+...+d_k*2^k con d_i = 0 o d_i = 1 per ogni i. Allora quello che stiamo cercando di calcolare è a^{d_0*2^0+d_1*2^1+d_2*2^2+...+d_k*2^k} che corrisponde a a^{d_0*2^0}*a^{d_1*2^1}*a^{d_2*2^2}*...*a^{d_k*2^k} ed essendo i numeri rappresentati in binario nel calcolatore il calcolo diventa comodo infatti possiamo seguire il seguente procedimento:

  • Iniziamo ponendo il risultato attuale r=1
  • Calcoliamo a^{(2^0)} =a e sappiamo che se d_0 = 1 allora dovremo moltiplicare r per a.
  • Calcoliamo a^{(2^1)} = a^2 e sappiamo che se d_1 = 1 allora dovremo moltiplicare r per a^2
  • Calcoliamo a^{(2^2)} = a^4 e sappiamo che se d_1 = 1 allora dovremo moltiplicare r per a^4
  • Procediamo in questo modo fino a quando non terminano i bit del numero che stiamo considerando. Il codice che implementa il metodo 2 è molto semplice, e leggermente più veloce del metodo 1 in quanto è iterativo:
    codice:
int fast_pow(int base, int esp, int MOD){
	long long r = 1; // risultato
	long long pot_base =  base; // a, a^2, a^4....
	while(esp > 0){
		if(esp % 2) // controllo l'ultimo bit (d_i)
			r = (r * pot_base) % MOD;
		pot_base = (pot_base * pot_base) % MOD; // elevo alla seconda
		esp >>= 1; // elimino l'ultimo bit
	}
	return r;
}
4 Mi Piace