Exponenciação Rápida em Rust

A Exponenciação Rápida (também chamada de exponenciação por quadratura ou binary exponentiation) é uma técnica que calcula a^n em apenas O(log n) multiplicações, em vez das O(n) multiplicações da abordagem ingênua. O truque fundamental é decompor o expoente em potências de 2 (sua representação binária) e usar a propriedade a^(2k) = (a^k)^2.

Essa técnica é absolutamente essencial em criptografia (RSA, Diffie-Hellman), onde se calcula a^n mod m com expoentes de centenas de dígitos. Também é a base para a multiplicação de matrizes em O(log n), permitindo calcular o n-ésimo número de Fibonacci, recorrências lineares e cadeias de Markov de forma ultra-eficiente.

Como Funciona

A ideia central é representar o expoente n em binário e aproveitar que a^n pode ser decomposto em produto de potências de a cujos expoentes são potências de 2.

Calcular 3^13:

Passo 1: Decompor 13 em binário
  13 = 1101 em binário = 8 + 4 + 1 = 2³ + 2² + 2⁰

Passo 2: 3^13 = 3^8 × 3^4 × 3^1

Passo 3: Calcular as potências por quadratura sucessiva
  3^1  = 3
  3^2  = 3^1 × 3^1 = 9
  3^4  = 3^2 × 3^2 = 81
  3^8  = 3^4 × 3^4 = 6561

Passo 4: Multiplicar apenas as potências cujo bit é 1
  13 = 1  1  0  1  (binário, lido da direita para esquerda)
       ↑  ↑     ↑
       3¹ 3⁴   3⁸    (bits ligados)

  3^13 = 3 × 81 × 6561 = 1.594.323

Visualização iterativa:
  n = 13 (1101)     base = 3      resultado = 1

  bit 0 = 1:  resultado = 1 × 3 = 3          base = 3² = 9
  bit 1 = 0:  (pula)                          base = 9² = 81
  bit 2 = 1:  resultado = 3 × 81 = 243       base = 81² = 6561
  bit 3 = 1:  resultado = 243 × 6561 = 1.594.323

  Resultado: 3^13 = 1.594.323 (apenas 4 iterações!)

Comparação:
  Método ingênuo: 12 multiplicações  (3 × 3 × 3 × ... × 3)
  Exponenciação rápida: 5 operações  (3 quadraturas + 2 multiplicações extras)

Para exponenciação modular (usada em criptografia):

Calcular 7^256 mod 13:

  Em vez de calcular 7^256 (número com ~217 dígitos!) e depois tirar mod,
  aplicamos mod a cada passo:

  7^1    mod 13 = 7
  7^2    mod 13 = 49 mod 13 = 10
  7^4    mod 13 = 10² mod 13 = 100 mod 13 = 9
  7^8    mod 13 = 9² mod 13 = 81 mod 13 = 3
  7^16   mod 13 = 3² mod 13 = 9
  7^32   mod 13 = 9² mod 13 = 81 mod 13 = 3
  7^64   mod 13 = 3² mod 13 = 9
  7^128  mod 13 = 9² mod 13 = 81 mod 13 = 3
  7^256  mod 13 = 3² mod 13 = 9

  256 = 100000000 (binário), apenas 1 bit ligado
  Resultado: 7^256 mod 13 = 9 (calculado com apenas 8 quadraturas!)

Complexidade

Operação	Tempo	Espaço
Exponenciação rápida (inteiros)	O(log n) multiplicações	O(1)
Exponenciação modular	O(log n) multiplicações	O(1)
Multiplicação de matrizes k×k	O(k^3 log n)	O(k^2)
Fibonacci via matriz	O(log n)	O(1)

O(log n): o número de bits de n determina o número de passos. Para n = 10^18, são apenas ~60 passos.
Espaço O(1): a versão iterativa usa apenas variáveis locais. A versão com matrizes usa O(k^2) para armazenar a matriz.
Overflow: sem módulo, os números crescem exponencialmente. Use u128 ou exponenciação modular para evitar overflow.

Implementação em Rust

/// Exponenciação rápida: calcula base^exp em O(log exp).
/// Cuidado com overflow para bases e expoentes grandes!
fn exp_rapida(mut base: u64, mut exp: u64) -> u64 {
    let mut resultado: u64 = 1;

    while exp > 0 {
        // Se o bit menos significativo de exp é 1
        if exp & 1 == 1 {
            resultado = resultado.wrapping_mul(base);
        }
        base = base.wrapping_mul(base);
        exp >>= 1; // Remove o bit menos significativo
    }

    resultado
}

/// Exponenciação modular: calcula (base^exp) mod modulo em O(log exp).
/// Nunca sofre overflow se modulo^2 cabe em u64 (modulo < ~4.3 × 10^9).
fn exp_modular(mut base: u64, mut exp: u64, modulo: u64) -> u64 {
    if modulo == 1 {
        return 0;
    }

    let mut resultado: u64 = 1;
    base %= modulo;

    while exp > 0 {
        if exp & 1 == 1 {
            resultado = resultado * base % modulo;
        }
        exp >>= 1;
        base = base * base % modulo;
    }

    resultado
}

/// Versão segura para módulos grandes usando u128 internamente.
fn exp_modular_seguro(mut base: u128, mut exp: u128, modulo: u128) -> u128 {
    if modulo == 1 {
        return 0;
    }

    let mut resultado: u128 = 1;
    base %= modulo;

    while exp > 0 {
        if exp & 1 == 1 {
            resultado = resultado * base % modulo;
        }
        exp >>= 1;
        base = base * base % modulo;
    }

    resultado
}

fn main() {
    // Exponenciação rápida básica
    println!("=== Exponenciação Rápida ===");
    let casos = [(2, 10), (3, 13), (5, 20), (7, 8)];
    for (base, exp) in casos {
        println!("{}^{} = {}", base, exp, exp_rapida(base, exp));
    }

    // Exponenciação modular
    println!("\n=== Exponenciação Modular ===");
    println!("7^256 mod 13 = {}", exp_modular(7, 256, 13));
    println!("2^100 mod 1000 = {}", exp_modular(2, 100, 1000));
    println!("3^1000 mod 10007 = {}", exp_modular(3, 1000, 10007));

    // Exemplo de criptografia: verificação simples
    println!("\n=== Simulação RSA simplificada ===");
    let p: u64 = 61;
    let q: u64 = 53;
    let n = p * q;  // 3233
    let e: u64 = 17;    // expoente público
    let d: u64 = 2753;  // expoente privado (e*d ≡ 1 mod phi(n))

    let mensagem: u64 = 42;
    let cifrada = exp_modular(mensagem, e, n);
    let decifrada = exp_modular(cifrada, d, n);

    println!("Mensagem original: {}", mensagem);
    println!("Cifrada (m^e mod n): {}", cifrada);
    println!("Decifrada (c^d mod n): {}", decifrada);
    println!("Mensagem recuperada: {}", decifrada == mensagem);
}

Exemplo de Execução

=== Exponenciação Rápida ===
2^10 = 1024
3^13 = 1594323
5^20 = 95367431640625
7^8 = 5764801

=== Exponenciação Modular ===
7^256 mod 13 = 9
2^100 mod 1000 = 376
3^1000 mod 10007 = 4950

=== Simulação RSA simplificada ===
Mensagem original: 42
Cifrada (m^e mod n): 2557
Decifrada (c^d mod n): 42
Mensagem recuperada: true

Trace de exp_modular(3, 13, 100):

base=3, exp=13 (1101 binário), mod=100, resultado=1

Iteração 1: exp=13, bit=1
  resultado = 1 * 3 % 100 = 3
  base = 3 * 3 % 100 = 9
  exp = 6

Iteração 2: exp=6, bit=0
  (pula resultado)
  base = 9 * 9 % 100 = 81
  exp = 3

Iteração 3: exp=3, bit=1
  resultado = 3 * 81 % 100 = 43
  base = 81 * 81 % 100 = 6561 % 100 = 61
  exp = 1

Iteração 4: exp=1, bit=1
  resultado = 43 * 61 % 100 = 2623 % 100 = 23
  base = 61 * 61 % 100 = 3721 % 100 = 21
  exp = 0

Resultado: 3^13 mod 100 = 23
Verificação: 3^13 = 1594323, 1594323 % 100 = 23 ✓

Variações e Otimizações

1. Fibonacci em O(log n) com Exponenciação de Matrizes

A recorrência de Fibonacci F(n) = F(n-1) + F(n-2) pode ser expressa como multiplicação de matrizes:

┌         ┐ⁿ   ┌           ┐
│  1   1  │  =  │ F(n+1)  F(n)  │
│  1   0  │     │  F(n)  F(n-1) │
└         ┘     └               ┘

/// Matriz 2x2 para cálculos de Fibonacci.
type Matriz = [[u64; 2]; 2];

/// Multiplicação de matrizes 2x2 com módulo.
fn mul_matriz(a: &Matriz, b: &Matriz, modulo: u64) -> Matriz {
    let mut c = [[0u64; 2]; 2];
    for i in 0..2 {
        for j in 0..2 {
            for k in 0..2 {
                c[i][j] = (c[i][j] + a[i][k] % modulo * (b[k][j] % modulo)) % modulo;
            }
        }
    }
    c
}

/// Exponenciação de matriz 2x2 em O(log n).
fn exp_matriz(mut base: Matriz, mut exp: u64, modulo: u64) -> Matriz {
    let mut resultado: Matriz = [[1, 0], [0, 1]]; // Matriz identidade

    while exp > 0 {
        if exp & 1 == 1 {
            resultado = mul_matriz(&resultado, &base, modulo);
        }
        base = mul_matriz(&base, &base, modulo);
        exp >>= 1;
    }

    resultado
}

/// Calcula o n-ésimo número de Fibonacci mod m em O(log n).
fn fibonacci(n: u64, modulo: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    if n == 1 {
        return 1 % modulo;
    }

    let base: Matriz = [[1, 1], [1, 0]];
    let resultado = exp_matriz(base, n - 1, modulo);
    resultado[0][0]
}

fn main() {
    let modulo = 1_000_000_007; // primo grande, comum em competições

    println!("=== Fibonacci via Exponenciação de Matrizes ===");
    println!("F(0) = {}", fibonacci(0, modulo));
    println!("F(1) = {}", fibonacci(1, modulo));
    println!("F(10) = {}", fibonacci(10, modulo));
    println!("F(50) = {}", fibonacci(50, modulo));
    println!("F(100) mod 10^9+7 = {}", fibonacci(100, modulo));
    println!("F(1000) mod 10^9+7 = {}", fibonacci(1000, modulo));
    println!("F(10^18) mod 10^9+7 = {}", fibonacci(1_000_000_000_000_000_000, modulo));

    // Verificação com os primeiros Fibonacci
    println!("\nPrimeiros 15 números de Fibonacci:");
    for i in 0..15 {
        print!("F({})={} ", i, fibonacci(i, modulo));
    }
    println!();
}

2. Recorrências Lineares Genéricas

A mesma técnica funciona para qualquer recorrência linear.

/// Resolve recorrências lineares de ordem k em O(k^3 log n).
/// Exemplo: tribonacci T(n) = T(n-1) + T(n-2) + T(n-3)

type Matriz3 = [[u64; 3]; 3];

fn mul_mat3(a: &Matriz3, b: &Matriz3, m: u64) -> Matriz3 {
    let mut c = [[0u64; 3]; 3];
    for i in 0..3 {
        for j in 0..3 {
            for k in 0..3 {
                c[i][j] = (c[i][j] + a[i][k] % m * (b[k][j] % m)) % m;
            }
        }
    }
    c
}

fn exp_mat3(mut base: Matriz3, mut exp: u64, m: u64) -> Matriz3 {
    let mut res: Matriz3 = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]; // identidade
    while exp > 0 {
        if exp & 1 == 1 {
            res = mul_mat3(&res, &base, m);
        }
        base = mul_mat3(&base, &base, m);
        exp >>= 1;
    }
    res
}

/// Calcula o n-ésimo Tribonacci: T(0)=0, T(1)=0, T(2)=1
/// T(n) = T(n-1) + T(n-2) + T(n-3)
fn tribonacci(n: u64, modulo: u64) -> u64 {
    if n < 2 { return 0; }
    if n == 2 { return 1 % modulo; }

    // Matriz de transição para T(n) = T(n-1) + T(n-2) + T(n-3):
    // ┌ T(n)   ┐   ┌ 1 1 1 ┐   ┌ T(n-1) ┐
    // │ T(n-1) │ = │ 1 0 0 │ × │ T(n-2) │
    // └ T(n-2) ┘   └ 0 1 0 ┘   └ T(n-3) ┘

    let base: Matriz3 = [
        [1, 1, 1],
        [1, 0, 0],
        [0, 1, 0],
    ];

    let resultado = exp_mat3(base, n - 2, modulo);
    // resultado[0][0] * T(2) + resultado[0][1] * T(1) + resultado[0][2] * T(0)
    resultado[0][0] % modulo
}

fn main() {
    let modulo = 1_000_000_007;

    println!("=== Tribonacci via Exponenciação de Matrizes ===");
    println!("Primeiros 15 Tribonacci:");
    for i in 0..15 {
        print!("T({})={} ", i, tribonacci(i, modulo));
    }
    println!();

    println!("\nT(100) mod 10^9+7 = {}", tribonacci(100, modulo));
    println!("T(10^18) mod 10^9+7 = {}", tribonacci(1_000_000_000_000_000_000, modulo));
}

3. Teste de Primalidade Miller-Rabin (Usa Exponenciação Modular)

/// Exponenciação modular com u128 para evitar overflow.
fn exp_mod(mut base: u128, mut exp: u128, modulo: u128) -> u128 {
    let mut resultado: u128 = 1;
    base %= modulo;
    while exp > 0 {
        if exp & 1 == 1 {
            resultado = resultado * base % modulo;
        }
        exp >>= 1;
        base = base * base % modulo;
    }
    resultado
}

/// Teste de primalidade Miller-Rabin determinístico para n < 3.3 × 10^24.
/// Usa testemunhas fixas que garantem resultado correto nesse intervalo.
fn eh_primo(n: u64) -> bool {
    if n < 2 { return false; }
    if n == 2 || n == 3 { return true; }
    if n % 2 == 0 { return false; }

    // Escrever n-1 como 2^r × d, onde d é ímpar
    let mut d = n - 1;
    let mut r = 0u32;
    while d % 2 == 0 {
        d /= 2;
        r += 1;
    }

    // Testemunhas suficientes para n < 3.3 × 10^24
    let testemunhas = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];

    'proximo: for &a in &testemunhas {
        if a >= n { continue; }

        let mut x = exp_mod(a as u128, d as u128, n as u128) as u64;

        if x == 1 || x == n - 1 {
            continue 'proximo;
        }

        for _ in 0..r - 1 {
            x = exp_mod(x as u128, 2, n as u128) as u64;
            if x == n - 1 {
                continue 'proximo;
            }
        }

        return false; // Composto
    }

    true // Provavelmente primo (determinístico para n < 3.3 × 10^24)
}

fn main() {
    println!("=== Teste de Primalidade Miller-Rabin ===");
    let testes = [
        2, 3, 17, 561, 997, 1009, 104729,
        1_000_000_007, 1_000_000_009,
    ];

    for &n in &testes {
        println!("{}: {}", n, if eh_primo(n) { "primo" } else { "composto" });
    }

    // 561 é um número de Carmichael (pseudoprimo de Fermat), mas Miller-Rabin o detecta
    println!("\n561 é número de Carmichael (pseudoprimo de Fermat)");
    println!("Miller-Rabin corretamente identifica como composto: {}", !eh_primo(561));
}

Aplicações Práticas

Criptografia RSA: calcular m^e mod n (cifragem) e c^d mod n (decifragem) com expoentes de 2048+ bits requer exponenciação modular rápida.
Protocolo Diffie-Hellman: troca segura de chaves usa g^a mod p onde a é secreto.
Testes de primalidade: Miller-Rabin e Fermat dependem criticamente da exponenciação modular.
Fibonacci e recorrências: calcular o n-ésimo termo de qualquer recorrência linear em O(k^3 log n) com exponenciação de matrizes.
Cadeias de Markov: elevar a matriz de transição à n-ésima potência para calcular probabilidades após n passos.
Computação de hashes: funções hash baseadas em polinômios usam exponenciação modular.

Comparação com Alternativas

Método	Tempo	Quando usar
Exponenciação ingênua	O(n)	Expoentes muito pequenos (n < 20)
Exponenciação rápida	O(log n)	Caso geral
Exponenciação modular	O(log n)	Quando precisa de resultado mod m
Exponenciação com u128	O(log n)	Módulos grandes (até ~10^18)
Biblioteca num-bigint	O(log n * k)	Números arbitrariamente grandes
Exponenciação de matrizes	O(k^3 log n)	Recorrências lineares de ordem k

Exercícios Práticos

Torre de potências: Implemente o cálculo de a^(b^c) mod m (torre de exponenciação). Dica: use o Teorema de Euler: a^phi(m) ≡ 1 (mod m) quando mdc(a,m)=1, então a^x mod m = a^(x mod phi(m)) mod m.
Potência de grafo: Dada a matriz de adjacência de um grafo, use exponenciação de matrizes para calcular o número de caminhos de comprimento exatamente k entre todos os pares de vértices.
Exponenciação rápida genérica: Implemente uma versão genérica da exponenciação rápida que funcione para qualquer tipo que implemente Mul e tenha um elemento identidade. Teste com inteiros, matrizes e polinômios.
Período de Pisano: O período de Pisano pi(m) é o período da sequência de Fibonacci mod m. Usando a exponenciação de matrizes, encontre pi(m) para m = 2, 3, …, 20. Dica: calcule F(k) mod m para k crescente até F(k) mod m = 0 e F(k+1) mod m = 1.

Veja Também

Algoritmo de Euclides (MDC) em Rust — inverso modular, base para RSA
Crivo de Eratóstenes em Rust — encontrar primos para criptografia
Tipos Numéricos — u64, u128, overflow e wrapping
Vec — Vetores Dinâmicos — armazenamento de matrizes
Arrays — Arrays de Tamanho Fixo — matrizes de tamanho fixo para exponenciação