Stavo provando a risolvere “crittografia RSA” ma mi riconosce come output corretto solo le prime 2 subtask, alle altre da errore. Non riesco a capire dove ho sbagliato.
#include <iostream>
#include <cmath>
using namespace std;
void decifra(int N, int d, int L, int messaggio[], char plaintext[])
{
long long int c=0,i=0;
for (i=0; i<L;i++)
{
c=messaggio[i];
c=pow(c,d);
c=c%N;
plaintext[i]=c;
}
plaintext[L]= '\0';
cout<<endl;
i=0;
while(i<=L)
{
cout<<plaintext[i]<<" ";
i++;
}
}
Salve, prima di tutto buon natale 
.
Dati i valori di “c” e “d”, secondo le Assunzioni del problema, l’espressione c^d raggiunge valori che il long long int non può contenere (nessun tipo primitivo del c++ può contenere questi valori) quell’istruzione pow va in overflow
1 Mi Piace
In teoria non dovresti interagire con l’input e output essedo un esercizio con grader.
Giusto.
1 Mi Piace
Innanzi tutto grazie per gli auguri 
.
Non avevo pensato a questo possibile problema, comunque ho provato a risolvere utilizzano i suggerimenti presenti nel testo del problema: (A · B) mod M = (A mod M · B mod M) mod M;
Di conseguenza ho cambiato la parte di decifrazione del messaggio da:
for (i=0; i<L;i++)
{
c=messaggio[i];
c=pow(c,d);
c=c%N;
plaintext[i]=c;
}
a questo:
for (i=0; i<L;i++)
{
c=messaggio[i];
if(d%2==0){
A=d/2;
B=A;
} else {
A=d/2;
B=A+1;
}
A=pow(c,A);
B=pow(c,B);
A=A%N;
B=B%N;
c=(A*B)%N;
plaintext[i]=c;
}
in questo modo ho praticamente dimezzato le dimensioni dei valori, comunque mi continua a dare errore alle stesse subtask, potrei ripetere questo procedimento per suddividere ulteriormente ogni potenza, ma non credo sia la soluzione giusta.
Dividere in due non basta, se ti viene dato per esempio d = 100 e c =2, hai diviso il calcolo in 2^(99) * 2^(99) e considerando che nel long long int il massimo valore è tipo 2^(63) , siamo ancora fuori con i valori 
Comunque per questo problema si può fare 60/100 facendo la potenza in O(esponente) , cioè l’algoritmo basilare, per fare 100/100 bisogna fare solo log2(esponente) moltiplicazioni per ogni numero
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