--- title: "Exponenciação Rápida em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/exponencia%C3%A7%C3%A3o-r%C3%A1pida-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/exponencia%C3%A7%C3%A3o-r%C3%A1pida-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda exponenciação rápida (fast exponentiation) implementada em Zig. Potência modular eficiente com código funcional." date: "2026-02-21" author: "Zig Brasil" --- # Exponenciação Rápida em Zig — Implementação e Explicação Aprenda exponenciação rápida (fast exponentiation) implementada em Zig. Potência modular eficiente com código funcional. # Exponenciação Rápida em Zig — Implementação e Explicação A **exponenciação rápida** (binary exponentiation) calcula a^n em O(log n) em vez de O(n). A ideia é que a^n pode ser decomposto usando a representação binária do expoente. É essencial em criptografia (RSA), aritmética modular e multiplicação de matrizes. ## Como Funciona ``` a^13 = a^(1101₂) = a^8 × a^4 × a^1 Em vez de 13 multiplicações → apenas 4 (3 ao quadrado + 1 multiplicação extra) ``` ### Visualização ``` Calcular 3^13: 13 em binário = 1101 Iteração 1: bit=1 → resultado *= 3 → resultado=3, base=3²=9 Iteração 2: bit=0 → nada → resultado=3, base=9²=81 Iteração 3: bit=1 → resultado *= 81 → resultado=243, base=81²=6561 Iteração 4: bit=1 → resultado *= 6561→ resultado=1594323 3^13 = 1594323 ✓ Calcular 2^10 mod 1000: resultado=1, base=2 bit=0: base=4 bit=1: resultado=4, base=16 bit=0: base=256 bit=1: resultado=1024 mod 1000 = 24 2^10 mod 1000 = 24 ✓ ``` ## Implementação em Zig ```zig const std = @import("std"); /// Exponenciação rápida — calcula base^exp em O(log exp). pub fn potencia(base_param: u64, exp_param: u64) u64 { var resultado: u64 = 1; var base = base_param; var exp = exp_param; while (exp > 0) { if (exp & 1 == 1) { resultado *= base; } base *= base; exp >>= 1; } return resultado; } /// Exponenciação modular — calcula (base^exp) mod m em O(log exp). pub fn potenciaMod(base_param: u64, exp_param: u64, m: u64) u64 { if (m == 1) return 0; var resultado: u64 = 1; var base = base_param % m; var exp = exp_param; while (exp > 0) { if (exp & 1 == 1) { resultado = mulMod(resultado, base, m); } base = mulMod(base, base, m); exp >>= 1; } return resultado; } /// Multiplicação modular segura (evita overflow). fn mulMod(a: u64, b: u64, m: u64) u64 { return @intCast(@as(u128, a) * @as(u128, b) % @as(u128, m)); } /// Multiplicação de matrizes 2x2 (para Fibonacci, etc.). const Mat2x2 = [2][2]u64; fn matMul(a: Mat2x2, b: Mat2x2, m: u64) Mat2x2 { var resultado: Mat2x2 = undefined; for (0..2) |i| { for (0..2) |j| { var soma: u128 = 0; for (0..2) |k| { soma += @as(u128, a[i][k]) * @as(u128, b[k][j]); } resultado[i][j] = @intCast(soma % @as(u128, m)); } } return resultado; } /// Exponenciação de matriz 2x2 — O(log n). pub fn matPow(mat: Mat2x2, exp_param: u64, m: u64) Mat2x2 { var resultado: Mat2x2 = .{ .{ 1, 0 }, .{ 0, 1 } }; // identidade var base = mat; var exp = exp_param; while (exp > 0) { if (exp & 1 == 1) { resultado = matMul(resultado, base, m); } base = matMul(base, base, m); exp >>= 1; } return resultado; } /// Teste de primalidade de Miller-Rabin (usa exponenciação modular). pub fn ehPrimo(n: u64) bool { if (n < 2) return false; if (n < 4) return true; if (n % 2 == 0 or n % 3 == 0) return false; // Escreve n-1 = d * 2^r var d = n - 1; var r: u32 = 0; while (d % 2 == 0) { d /= 2; r += 1; } // Testa com bases determinísticas para n < 3.317.044.064.679.887.385.961.981 const testemunhas = [_]u64{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 }; for (testemunhas) |a| { if (a >= n) continue; var x = potenciaMod(a, d, n); if (x == 1 or x == n - 1) continue; var encontrou = false; for (0..r - 1) |_| { x = mulMod(x, x, n); if (x == n - 1) { encontrou = true; break; } } if (!encontrou) return false; } return true; } pub fn main() !void { const stdout = std.io.getStdOut().writer(); // Exponenciação simples try stdout.print("=== Exponenciação Rápida ===\n", .{}); try stdout.print("2^10 = {d}\n", .{potencia(2, 10)}); try stdout.print("3^13 = {d}\n", .{potencia(3, 13)}); // Exponenciação modular try stdout.print("\n=== Exponenciação Modular ===\n", .{}); try stdout.print("2^10 mod 1000 = {d}\n", .{potenciaMod(2, 10, 1000)}); try stdout.print("7^256 mod 13 = {d}\n", .{potenciaMod(7, 256, 13)}); try stdout.print("2^1000000 mod 1000000007 = {d}\n", .{potenciaMod(2, 1_000_000, 1_000_000_007)}); // Teste de primalidade try stdout.print("\n=== Miller-Rabin (usa exp. modular) ===\n", .{}); const testes = [_]u64{ 2, 17, 100, 997, 1000000007 }; for (testes) |n| { try stdout.print("{d} é primo? {}\n", .{ n, ehPrimo(n) }); } // Fibonacci com exponenciação de matriz try stdout.print("\n=== Fibonacci via Matriz ===\n", .{}); const fib_mat: Mat2x2 = .{ .{ 1, 1 }, .{ 1, 0 } }; const m: u64 = 1_000_000_007; for ([_]u64{ 10, 50, 100 }) |n| { const resultado = matPow(fib_mat, n, m); try stdout.print("F({d}) mod 10^9+7 = {d}\n", .{ n, resultado[0][1] }); } } ``` ## Análise de Complexidade | Operação | Tempo | Espaço | |----------|-------|--------| | **Potência simples** | O(log n) | O(1) | | **Potência modular** | O(log n) | O(1) | | **Potência de matriz** | O(k^3 log n) | O(k^2) | Onde n = expoente e k = dimensão da matriz. ## Aplicações - **Criptografia RSA**: (mensagem^e) mod n - **Fibonacci em O(log n)**: exponenciação da matriz [[1,1],[1,0]] - **Aritmética modular**: cálculos em competições de programação - **Teste de primalidade**: Miller-Rabin usa exponenciação modular ## Recursos Relacionados - [Fibonacci por Matriz](/algoritmos/fibonacci-matrix/) — Fibonacci em O(log n) usando matrizes - [Euclides (MDC)](/algoritmos/euclides-mdc/) — Inverso modular - [Crivo de Eratóstenes](/algoritmos/crivo-eratostenes/) — Encontrar primos - [Fatoração de Primos](/algoritmos/fatoracao-primos/) — Decompor em fatores