Potenze e moduli

Ci sono vari algoritmi, perlopiù nell'ambito della crittografia, che richiedono di calcolare delle potenze in aritmetica modulare. Senza entrare troppo nel contesto, prendiamo subito un esempio: per due interi positivi a e p piuttosto grandi, vogliamo calcolare il modulo seguente, con dei numeri a 32 bit (uint32_t).

$a^p''mod''p$

Facciamo finta che 53 e 91 siano numeri grandi, per cui vogliamo calcolare

${\mathrm{53}}^{\mathrm{91}}''mod''\mathrm{91}$
${\mathrm{53}}^{\mathrm{91}}$ è un numero astronomico, che richiederebbe oltre 500 bit per essere rappresentato, per cui bisogna trovare un modo indiretto per ottenerne il valore modulo 91. Il primo algoritmo che potrebbe venire a mente è questo, che esegue delle moltiplicazioni consecutive e ne prende il modulo ad ogni iterazione.

// supponiamo mod > 1, tralasciamo 0^0
uint32_t potenza_modulo(uint32_t base, uint32_t esp, uint32_t mod) {
    base %= mod;
    if (base == 0) return 0;

    uint32_t risultato = 1;
    for (uint32_t i = 0; i < esp; ++i) {
        risultato = (risultato * base) % mod;
    }

    return risultato;
}

Qui bisogna tenere a mente che risultato * base potrebbe non entrare in 32 bit. Siccome sia risultato che base possono essere al massimo mod - 1, basta verificare all'inizio che (mod - 1) * (mod - 1) sia rappresentabile.

Ma non esiste un algoritmo più efficiente? Sì: su questa pagina trovate dello pseudocodice, ma proverò a spiegarlo qui sotto.

uint32_t potenza_modulo(uint32_t base, uint32_t esp, uint32_t mod) {

    base %= mod;
    if (base == 0) return 0;

    uint32_t risultato = 1;
    while (true) {
        if (esp & 1) risultato = (risultato * base) % mod;
        esp >>= 1;
        if (esp == 0) break;
        base = (base * base) % mod;
    }

    return risultato;
}

Il trucco sta nel convertire l'esponente (91) in binario (1011011):

$91=2^6+2^4+2^3+2^1+2^0$
$''\Rightarrow ''{53}^{91}={53}^{2^6}·{53}^{2^4}·{53}^{2^3}·{53}^{2^1}·{53}^{2^0}$

Possiamo quindi accumulare il risultato moltiplicandolo per il valore corrispondente ad ogni bit 1 dell'esponente, saltando gli zeri. Guardiamo meglio il contenuto del ciclo while:

• if (esp & 1): se l'esponente è dispari, moltiplichiamo il risultato per la base, ricordando che a * b % p == (a % p) * (b % p), quindi possiamo prendere il modulo quando vogliamo in sostanza.
• esp >>= 1: passiamo al bit successivo dell'esponente.
• base = (base * base) % mod: il bit successivo corrisponde al quadrato della base attuale. Per esempio, il quinto bit corrisponde a:

${53}^{2^4}={53}^{2·2^3}={\left({53}^{2^3}\right)}^2$

Tutto qua! Il primo algoritmo è O(esp), mentre il secondo è O(log(esp)), quindi decisamente più efficiente.