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

$$53^{91}\mod 91$$

$53^{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}\cdot 53^{2^4} \cdot 53^{2^3} \cdot 53^{2^1} \cdot 53$$

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\cdot 2^3} = (53^{2^3})^2$$

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