Esponenziale base fissa con precomputazioni

Question

Sto cercando di calcolare $ g^m $ mod $ n $ dove $ m, n $ sono numeri di 1024 bit. Il metodo che desidero utilizzare è l'esponentezione di base fissa con le precomputazioni, noto anche come finestra a base fissa. L'articolo che sto seguendo è Brickell ET. al. "Esponenziale rapida con precomputazione: algoritmi e limiti inferiori" che si possono trovare qui.

Fondamentalmente l'idea è di precomputare $ g^{b^i} $ dove $ b $ è un radix. Ora se scriviamo $ m $ nella base radix: $ m = sum_ {i = 0}^k e_i b^i $ quindi $ g^m = prod (g^{b^i})^{e_i} $. Ad esempio: diciamo che vogliamo calcolare $ g^{142} $ e abbiamo scelto come radix $ b = 3 $ (sono a conoscenza dell'esempio più naturale di Radix 2, ma sto sperimentando diversi radici da vedere Se c'è qualche accelerazione). Scrivo $ m = (12021) _3 $ e calcola $ g^{142} = g^{3^4} tempes (g^{3^3})^2 tempes (g^3)^2 tims G^3 $.

Il codice pseudo indicato nel documento è:

b ← 1
a ← 1
for d = h to 1 by −1
    for each i such that a_i = d
        b ← b ∗ g^{x_i}
    a ← a ∗ b.
return a.

dove $ h $ è l'intervallo di $ e_i $ e $ a_i = e_i $ e $ x_i = g^{b^i} $.

La mia domanda è: invece di passare attraverso $ e_i $ per livello come suggerito dal codice pseudo, perché non passiamo attraverso la rappresentazione di base $ b $ di $ m $ a cifre alla volta e moltipliciamo mentre andiamo?

Quando ho cercato l'esponenziazione a base fissa in Henk e Tilborg "Enciclopedia di crittografia e sicurezza", dicono che "c'è tempo risparmiato moltiplicando poteri insieme con coefficienti identici, quindi aumentando i prodotti intermedi a poteri passo per passo". Credo che questo stia accennando alla risposta alla mia domanda, ma non capisco il ragionamento.