Lũy thừa nhanh — Từ O(n) xuống O(log n)

Mỗi lần bạn mở một trang web qua HTTPS, trình duyệt thực hiện một phép lũy thừa modular — nền tảng của RSA encryption. Private exponent d trong RSA thực tế có khoảng 600 chữ số thập phân. Nếu tính message^d mod n bằng cách nhân lần lượt, bạn cần khoảng 10^600 phép nhân — lâu hơn tuổi vũ trụ gấp vô hạn lần.

Binary exponentiation rút con số đó xuống còn ~2000 phép nhân, hoàn thành trong vài mili-giây. Đây chính là thuật toán khiến toàn bộ hạ tầng bảo mật Internet vận hành được — từ TLS handshake, digital signature cho đến key exchange trong mọi giao thức mã hóa hiện đại.

Bài viết này sẽ đưa bạn từ ý tưởng "bình phương rồi nhân" cơ bản, qua lũy thừa ma trận cho Fibonacci, đến ứng dụng thực tế trong cryptography và competitive programming. Mỗi kỹ thuật đều có code hoàn chỉnh, biên dịch được trong 4 ngôn ngữ.

Bức tranh tư duy

Nhân đôi thay vì nhân từng cái một

Hãy nghĩ về việc gấp giấy: một tờ giấy dày 0.1 mm, gấp đôi 30 lần sẽ dày khoảng 107 km — vượt bầu khí quyển Trái Đất. Gấp 42 lần đạt tới Mặt Trăng. Sức mạnh nằm ở tăng trưởng theo cấp số nhân: mỗi bước gấp đôi kết quả hiện tại, thay vì cộng thêm một lớp.

Binary exponentiation hoạt động theo nguyên lý tương tự. Thay vì nhân a với chính nó n lần (O(n)), ta phân tích số mũ n thành tổng các lũy thừa của 2, rồi chỉ cần bình phương liên tiếp và nhân khi cần.

Phân tích square-and-multiply

Tính a^13:
  13 ở dạng nhị phân = 1101₂ = 8 + 4 + 0 + 1

  Bước │ Bit │ base (bình phương) │ Hành động     │ result
  ─────┼─────┼────────────────────┼───────────────┼────────
  Init │     │ a                  │               │ 1
    1  │  1  │ a → a²             │ result *= a   │ a
    2  │  0  │ a² → a⁴            │ (bỏ qua)      │ a
    3  │  1  │ a⁴ → a⁸            │ result *= a⁴  │ a⁵
    4  │  1  │ a⁸ → a¹⁶           │ result *= a⁸  │ a¹³ ✓

  Chỉ 4 bước (= số bit của 13) thay vì 12 phép nhân.
  Tổng quát: a^n cần ≤ 2·log₂(n) phép nhân.

Ví dụ cụ thể — tính 3^13 mod 1000:

  Bước │ exp (nhị phân) │ base    │ result
  ─────┼────────────────┼─────────┼────────
  Init │ 1101           │ 3       │ 1
    1  │ bit=1 → nhân   │ 3²=9   │ 1×3 = 3
    2  │ bit=0 → bỏ qua │ 9²=81  │ 3
    3  │ bit=1 → nhân   │ 81²=561│ 3×81 = 243
    4  │ bit=1 → nhân   │ —      │ 243×561 mod 1000 = 323

  Kiểm tra: 3^13 = 1594323, 1594323 mod 1000 = 323 ✓

Cốt lõi kỹ thuật

Binary Exponentiation — Phiên bản lặp (Iterative)

Đây là phiên bản production-ready — không đệ quy, không tốn stack, dễ kiểm soát overflow.

C++PythonJavaGo

cpp

long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

python

def power_mod(base: int, exp: int, mod: int) -> int:
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

# Python built-in tương đương: pow(base, exp, mod)

java

static long powerMod(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1)
            result = mulMod(result, base, mod);
        base = mulMod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

// Tránh overflow khi nhân 2 số long
static long mulMod(long a, long b, long mod) {
    return Math.floorMod(
        java.math.BigInteger.valueOf(a)
            .multiply(java.math.BigInteger.valueOf(b))
            .longValueExact(),
        mod
    );
}

func powerMod(base, exp, mod int64) int64 {
    result := int64(1)
    base %= mod
    for exp > 0 {
        if exp&1 == 1 {
            result = mulMod(result, base, mod)
        }
        base = mulMod(base, base, mod)
        exp >>= 1
    }
    return result
}

func mulMod(a, b, mod int64) int64 {
    // Dùng big.Int để tránh overflow
    ab := new(big.Int).Mul(big.NewInt(a), big.NewInt(b))
    ab.Mod(ab, big.NewInt(mod))
    return ab.Int64()
}

Binary Exponentiation — Phiên bản đệ quy (Recursive)

Phiên bản đệ quy giúp hiểu bản chất toán học rõ hơn: a^n = (a^(n/2))² nếu n chẵn, a × (a^(n/2))² nếu n lẻ.

C++PythonJavaGo

cpp

long long power_mod_rec(long long base, long long exp, long long mod) {
    if (exp == 0) return 1;
    long long half = power_mod_rec(base, exp / 2, mod);
    long long res = (__int128)half * half % mod;
    if (exp & 1)
        res = (__int128)res * base % mod;
    return res;
}

python

def power_mod_rec(base: int, exp: int, mod: int) -> int:
    if exp == 0:
        return 1
    half = power_mod_rec(base, exp // 2, mod)
    res = half * half % mod
    if exp & 1:
        res = res * base % mod
    return res

java

static long powerModRec(long base, long exp, long mod) {
    if (exp == 0) return 1;
    long half = powerModRec(base, exp / 2, mod);
    long res = mulMod(half, half, mod);
    if ((exp & 1) == 1)
        res = mulMod(res, base, mod);
    return res;
}

func powerModRec(base, exp, mod int64) int64 {
    if exp == 0 {
        return 1
    }
    half := powerModRec(base, exp/2, mod)
    res := mulMod(half, half, mod)
    if exp&1 == 1 {
        res = mulMod(res, base, mod)
    }
    return res
}

Nghịch đảo modular — Định lý Fermat nhỏ

Khi p là số nguyên tố và gcd(a, p) = 1, Định lý Fermat nhỏ cho ta: a^(p-1) ≡ 1 (mod p), suy ra a^(-1) ≡ a^(p-2) (mod p). Nghịch đảo modular biến phép chia thành phép nhân trong modular arithmetic.

C++PythonJavaGo

cpp

// Yêu cầu: mod phải là số nguyên tố
long long mod_inverse(long long a, long long mod) {
    return power_mod(a, mod - 2, mod);
}

long long mod_divide(long long a, long long b, long long mod) {
    return (__int128)a % mod * mod_inverse(b, mod) % mod;
}

python

def mod_inverse(a: int, mod: int) -> int:
    """Yêu cầu: mod phải là số nguyên tố."""
    return power_mod(a, mod - 2, mod)

def mod_divide(a: int, b: int, mod: int) -> int:
    return a % mod * mod_inverse(b, mod) % mod

java

static long modInverse(long a, long mod) {
    // Yêu cầu: mod phải là số nguyên tố
    return powerMod(a, mod - 2, mod);
}

static long modDivide(long a, long b, long mod) {
    return mulMod(a % mod, modInverse(b, mod), mod);
}

func modInverse(a, mod int64) int64 {
    // Yêu cầu: mod phải là số nguyên tố
    return powerMod(a, mod-2, mod)
}

func modDivide(a, b, mod int64) int64 {
    return mulMod(a%mod, modInverse(b, mod), mod)
}

Lũy thừa ma trận (Matrix Exponentiation)

Nhân ma trận 2×2 và nâng lên lũy thừa bằng binary exponentiation — kỹ thuật nền tảng cho mọi bài toán hệ thức truy hồi tuyến tính.

C++PythonJavaGo

cpp

using Matrix = std::array<std::array<long long, 2>, 2>;

Matrix mat_mul(const Matrix& A, const Matrix& B, long long mod) {
    Matrix C{};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + (__int128)A[i][k] * B[k][j]) % mod;
    return C;
}

Matrix mat_pow(Matrix M, long long exp, long long mod) {
    Matrix result = {{{1, 0}, {0, 1}}}; // Ma trận đơn vị
    while (exp > 0) {
        if (exp & 1)
            result = mat_mul(result, M, mod);
        M = mat_mul(M, M, mod);
        exp >>= 1;
    }
    return result;
}

python

def mat_mul(A: list, B: list, mod: int) -> list:
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod,
         (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod,
         (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]
    ]

def mat_pow(M: list, exp: int, mod: int) -> list:
    result = [[1, 0], [0, 1]]  # Ma trận đơn vị
    while exp > 0:
        if exp & 1:
            result = mat_mul(result, M, mod)
        M = mat_mul(M, M, mod)
        exp >>= 1
    return result

java

static long[][] matMul(long[][] A, long[][] B, long mod) {
    long[][] C = new long[2][2];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C[i][j] = (C[i][j]
                    + java.math.BigInteger.valueOf(A[i][k])
                        .multiply(java.math.BigInteger.valueOf(B[k][j]))
                        .mod(java.math.BigInteger.valueOf(mod))
                        .longValueExact()) % mod;
    return C;
}

static long[][] matPow(long[][] M, long exp, long mod) {
    long[][] result = {{1, 0}, {0, 1}}; // Ma trận đơn vị
    while (exp > 0) {
        if ((exp & 1) == 1)
            result = matMul(result, M, mod);
        M = matMul(M, M, mod);
        exp >>= 1;
    }
    return result;
}

type Matrix [2][2]int64

func matMul(A, B Matrix, mod int64) Matrix {
    var C Matrix
    for i := 0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            for k := 0; k < 2; k++ {
                ab := new(big.Int).Mul(big.NewInt(A[i][k]), big.NewInt(B[k][j]))
                ab.Mod(ab, big.NewInt(mod))
                C[i][j] = (C[i][j] + ab.Int64()) % mod
            }
        }
    }
    return C
}

func matPow(M Matrix, exp, mod int64) Matrix {
    result := Matrix{{1, 0}, {0, 1}} // Ma trận đơn vị
    for exp > 0 {
        if exp&1 == 1 {
            result = matMul(result, M, mod)
        }
        M = matMul(M, M, mod)
        exp >>= 1
    }
    return result
}

Fibonacci O(log n) bằng lũy thừa ma trận

Dãy Fibonacci thỏa mãn hệ thức truy hồi tuyến tính: F(n) = F(n-1) + F(n-2). Viết lại dưới dạng ma trận:

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

Áp dụng binary exponentiation cho ma trận, ta tính F(n) trong O(log n) — xử lý được n = 10^18 trong vài micro-giây.

C++PythonJavaGo

cpp

long long fibonacci(long long n, long long mod = 1000000007) {
    if (n <= 1) return n;
    Matrix M = {{{1, 1}, {1, 0}}};
    Matrix result = mat_pow(M, n, mod);
    return result[0][1];
}

python

def fibonacci(n: int, mod: int = 10**9 + 7) -> int:
    if n <= 1:
        return n
    M = [[1, 1], [1, 0]]
    result = mat_pow(M, n, mod)
    return result[0][1]

java

static long fibonacci(long n, long mod) {
    if (n <= 1) return n;
    long[][] M = {{1, 1}, {1, 0}};
    long[][] result = matPow(M, n, mod);
    return result[0][1];
}

func fibonacci(n, mod int64) int64 {
    if n <= 1 {
        return n
    }
    M := Matrix{{1, 1}, {1, 0}}
    result := matPow(M, n, mod)
    return result[0][1]
}

Tổ hợp modular — C(n, k) mod p

Tiền xử lý factorial và inverse_factorial trong O(n), sau đó trả lời mỗi truy vấn C(n, k) trong O(1). Kỹ thuật này thiết yếu trong competitive programming khi cần tính hàng triệu giá trị tổ hợp.

C++PythonJavaGo

cpp

const int MAXN = 1000001;
const long long MOD = 1000000007;
long long fact[MAXN], inv_fact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = (__int128)fact[i - 1] * i % MOD;
    inv_fact[MAXN - 1] = power_mod(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = (__int128)inv_fact[i + 1] * (i + 1) % MOD;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return (__int128)fact[n] % MOD * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}

python

MOD = 10**9 + 7

def precompute(max_n: int):
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i - 1] * i % MOD

    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = power_mod(fact[max_n], MOD - 2, MOD)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    return fact, inv_fact

def nCr(n: int, r: int, fact: list, inv_fact: list) -> int:
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

java

static final int MAXN = 1000001;
static final long MOD = 1000000007L;
static long[] fact = new long[MAXN];
static long[] invFact = new long[MAXN];

static void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;
    invFact[MAXN - 1] = powerMod(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}

static long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] % MOD * invFact[r] % MOD * invFact[n - r] % MOD;
}

const MAXN = 1000001
const MOD = 1000000007

var fact [MAXN]int64
var invFact [MAXN]int64

func precompute() {
    fact[0] = 1
    for i := int64(1); i < MAXN; i++ {
        fact[i] = fact[i-1] * i % MOD
    }
    invFact[MAXN-1] = powerMod(fact[MAXN-1], MOD-2, MOD)
    for i := int64(MAXN - 2); i >= 0; i-- {
        invFact[i] = invFact[i+1] * (i + 1) % MOD
    }
}

func nCr(n, r int) int64 {
    if r < 0 || r > n {
        return 0
    }
    return fact[n] % MOD * invFact[r] % MOD * invFact[n-r] % MOD
}

Thực chiến

Kịch bản 1: RSA Encryption/Decryption Demo

Dưới đây là quy trình RSA hoàn chỉnh (dùng số nguyên tố nhỏ cho mục đích minh họa — RSA thực tế dùng số nguyên tố 2048-bit trở lên).

Quy trình sinh khóa:

Chọn hai số nguyên tố p, q → n = p × q
Tính φ(n) = (p-1)(q-1)
Chọn e = 65537 (public exponent tiêu chuẩn)
Tính d = e^(-1) mod φ(n) (private exponent, dùng extended Euclidean)

Mã hóa: ciphertext = message^e mod nGiải mã: message = ciphertext^d mod n

C++PythonJavaGo

cpp

#include <iostream>
using namespace std;

// Giả sử power_mod() đã được định nghĩa ở trên

long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (a == 0) { x = 0; y = 1; return b; }
    long long x1, y1;
    long long g = extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return g;
}

long long mod_inverse_ext(long long a, long long mod) {
    long long x, y;
    extended_gcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

int main() {
    long long p = 61, q = 53;
    long long n = p * q;                // 3233
    long long phi = (p - 1) * (q - 1);  // 3120
    long long e = 17;                    // Public exponent (nhỏ để demo)
    long long d = mod_inverse_ext(e, phi); // 2753

    long long message = 42;
    long long encrypted = power_mod(message, e, n);
    long long decrypted = power_mod(encrypted, d, n);

    cout << "n = " << n << ", e = " << e << ", d = " << d << endl;
    cout << "Message:   " << message << endl;
    cout << "Encrypted: " << encrypted << endl;
    cout << "Decrypted: " << decrypted << endl;
    // Output: Decrypted: 42 ✓
    return 0;
}

python

def rsa_demo():
    p, q = 61, 53
    n = p * q                    # 3233
    phi = (p - 1) * (q - 1)      # 3120
    e = 17                        # Public exponent
    d = pow(e, -1, phi)           # 2753

    message = 42
    encrypted = pow(message, e, n)
    decrypted = pow(encrypted, d, n)

    print(f"n = {n}, e = {e}, d = {d}")
    print(f"Message:   {message}")
    print(f"Encrypted: {encrypted}")
    print(f"Decrypted: {decrypted}")
    assert message == decrypted
    # Output: Decrypted: 42 ✓

rsa_demo()

java

import java.math.BigInteger;

public class RSADemo {
    public static void main(String[] args) {
        long p = 61, q = 53;
        long n = p * q;                    // 3233
        long phi = (p - 1) * (q - 1);      // 3120
        long e = 17;
        long d = BigInteger.valueOf(e)
                .modInverse(BigInteger.valueOf(phi)).longValueExact(); // 2753

        long message = 42;
        long encrypted = powerMod(message, e, n);
        long decrypted = powerMod(encrypted, d, n);

        System.out.println("n = " + n + ", e = " + e + ", d = " + d);
        System.out.println("Message:   " + message);
        System.out.println("Encrypted: " + encrypted);
        System.out.println("Decrypted: " + decrypted);
        // Output: Decrypted: 42 ✓
    }
}

package main

import (
    "fmt"
    "math/big"
)

func rsaDemo() {
    p, q := int64(61), int64(53)
    n := p * q
    phi := (p - 1) * (q - 1)
    e := int64(17)
    d := new(big.Int).ModInverse(big.NewInt(e), big.NewInt(phi)).Int64()

    message := int64(42)
    encrypted := powerMod(message, e, n)
    decrypted := powerMod(encrypted, d, n)

    fmt.Printf("n = %d, e = %d, d = %d\n", n, e, d)
    fmt.Printf("Message:   %d\n", message)
    fmt.Printf("Encrypted: %d\n", encrypted)
    fmt.Printf("Decrypted: %d\n", decrypted)
    // Output: Decrypted: 42 ✓
}

Kịch bản 2: Fibonacci thứ 10^18 mod 10^9+7

Trong competitive programming, bài toán yêu cầu tính F(n) với n lên tới 10^18 là kinh điển. Sử dụng lũy thừa ma trận, ta giải trong O(log n) ≈ 60 phép nhân ma trận 2×2.

C++PythonJavaGo

cpp

#include <iostream>
using namespace std;
// Sử dụng Matrix, mat_mul, mat_pow, fibonacci đã định nghĩa ở trên

int main() {
    long long MOD = 1000000007;
    // F(10) = 55
    cout << "F(10) = " << fibonacci(10, MOD) << endl;
    // F(10^18) mod 10^9+7
    long long n = 1000000000000000000LL;
    cout << "F(10^18) mod 10^9+7 = " << fibonacci(n, MOD) << endl;
    return 0;
}

python

if __name__ == "__main__":
    MOD = 10**9 + 7
    print(f"F(10) = {fibonacci(10, MOD)}")        # 55
    print(f"F(10^18) mod 10^9+7 = {fibonacci(10**18, MOD)}")

java

public class FibDemo {
    public static void main(String[] args) {
        long MOD = 1000000007L;
        System.out.println("F(10) = " + fibonacci(10, MOD));
        long n = 1000000000000000000L;
        System.out.println("F(10^18) mod 10^9+7 = " + fibonacci(n, MOD));
    }
}

func main() {
    mod := int64(1000000007)
    fmt.Printf("F(10) = %d\n", fibonacci(10, mod))
    n := int64(1000000000000000000)
    fmt.Printf("F(10^18) mod 10^9+7 = %d\n", fibonacci(n, mod))
}

Sai lầm điển hình

❌ Sai lầm 1: Overflow khi nhân trước khi mod

cpp

// SAI — overflow khi a, b gần 10^18
long long res = (a * b) % mod;

// ĐÚNG — dùng __int128 (GCC/Clang) hoặc tách phép nhân
long long res = (__int128)a * b % mod;

Trong Java, dùng BigInteger. Trong Go, dùng math/big. Python tự động xử lý số lớn nên không gặp vấn đề này.

❌ Sai lầm 2: Quên base case exp = 0

python

# SAI — vòng lặp không thực thi, result chưa khởi tạo đúng
def power_bad(base, exp, mod):
    result = base  # ← Sai! Nếu exp=0 thì trả về base thay vì 1
    while exp > 0:
        ...

# ĐÚNG — luôn khởi tạo result = 1
def power_good(base, exp, mod):
    result = 1     # ← a^0 = 1 với mọi a
    base %= mod
    while exp > 0:
        ...

❌ Sai lầm 3: Dùng Fermat inverse khi mod không nguyên tố

python

# SAI — Fermat chỉ đúng khi mod là số nguyên tố
def bad_inverse(a, mod):
    return power_mod(a, mod - 2, mod)  # Sai nếu mod = 12 (hợp số)

# ĐÚNG — dùng Extended Euclidean cho mod tổng quát
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    return g, y1 - (b // a) * x1, x1

def general_inverse(a, mod):
    g, x, _ = extended_gcd(a % mod, mod)
    if g != 1:
        raise ValueError("Nghịch đảo không tồn tại")
    return x % mod

❌ Sai lầm 4: Dùng int thay vì long long

cpp

// SAI — int chỉ chứa đến ~2×10^9, tích trung gian tràn
int power_mod(int base, int exp, int mod) {
    int result = 1;
    result = result * base % mod; // overflow!
}

// ĐÚNG — dùng long long cho mọi biến trung gian
long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    // ...
}

⚠️ Quy tắc vàng

Trong modular arithmetic, luôn mod sau mỗi phép nhân, và luôn dùng kiểu dữ liệu đủ lớn cho tích trung gian. Một phép nhân 10^9 × 10^9 = 10^18 vượt giới hạn int nhưng nằm trong long long.

Under the Hood

Tại sao O(log n) hoạt động

Mọi số nguyên dương n đều biểu diễn được dưới dạng nhị phân với ⌊log₂(n)⌋ + 1 bit. Binary exponentiation duyệt qua từng bit, mỗi bit thực hiện tối đa 2 phép nhân (một cho bình phương, một cho nhân vào kết quả). Tổng cộng: ≤ 2·log₂(n) phép nhân.

n = 10^18 → log₂(10^18) ≈ 60 bit → tối đa 120 phép nhân
n = 10^600 (RSA) → ≈ 2000 bit → tối đa 4000 phép nhân

Chi phí phần cứng

Trên CPU hiện đại, phép nhân 64-bit mất khoảng 3-5 clock cycle. Phép mod (thực chất là phép chia) mất 20-40 cycle. Với 120 phép nhân-mod cho n = 10^18, tổng chi phí khoảng 5000 cycle ≈ 1-2 micro-giây trên CPU 3 GHz.

Bảng so sánh hiệu năng

Phương pháp	Độ phức tạp	n = 10^6	n = 10^18	n = 10^600
Naive (nhân lần lượt)	O(n)	~1ms	~10^6 năm	∞
Binary Exponentiation	O(log n)	~0.02μs	~1μs	~5μs
Python `pow(a, n, m)`	O(log n)	~0.03μs	~1.5μs	~8μs

Khi nào lũy thừa ma trận là quá mức cần thiết

Lũy thừa ma trận mạnh mẽ nhưng không phải lúc nào cũng cần thiết:

Fibonacci: Tồn tại công thức fast doubling (chỉ dùng scalar, không cần ma trận) cũng O(log n) nhưng nhanh hơn ~2-3 lần do ít phép nhân hơn.
Hệ thức truy hồi bậc k: Ma trận k×k, chi phí O(k³ log n). Với k lớn (>10), cân nhắc phương pháp Berlekamp-Massey + Kitamasa.
Bài toán chỉ cần F(n) mod m nhỏ: Pisano period có thể hiệu quả hơn.

Checklist ghi nhớ

✅ Checklist triển khai

[ ] Binary exponentiation tính a^n mod m trong O(log n) bằng kỹ thuật square-and-multiply
[ ] Luôn khởi tạo result = 1 (vì a^0 = 1)
[ ] Thực hiện base %= mod ở đầu hàm để tránh overflow ngay phép nhân đầu tiên
[ ] Mod sau mỗi phép nhân, không đợi đến cuối
[ ] Dùng __int128 (C++), BigInteger (Java), hoặc math/big (Go) cho tích trung gian lớn
[ ] Python xử lý big integer tự động — dùng pow(base, exp, mod) built-in là đủ
[ ] Nghịch đảo modular bằng Fermat: a^(-1) = a^(p-2) mod p — chỉ khi p nguyên tố
[ ] Cho mod tổng quát (hợp số), dùng Extended Euclidean Algorithm
[ ] Lũy thừa ma trận biến hệ thức truy hồi tuyến tính thành O(k³ log n) với ma trận k×k
[ ] Fibonacci: [[1,1],[1,0]]^n cho [F(n+1), F(n)] — kết quả ở vị trí [0][1]
[ ] Precompute fact[] và inv_fact[] để trả lời C(n,k) mod p trong O(1) mỗi truy vấn
[ ] Trick tính inv_fact[]: chỉ cần 1 lần gọi power_mod cho inv_fact[maxN], còn lại nhân ngược
[ ] RSA dùng binary exponentiation cho cả mã hóa (m^e mod n) lẫn giải mã (c^d mod n)
[ ] Kiểm tra giới hạn kiểu dữ liệu: 10^9 × 10^9 = 10^18 vừa khít long long, nhưng 10^18 × 10^18 tràn

Bài tập luyện tập

Bài 1 — Foundation: Tính 2^n mod 10^9+7

Cho số nguyên n (0 ≤ n ≤ 10^18), tính 2^n mod (10^9 + 7).

Input: Một dòng chứa n. Output: Giá trị 2^n mod 10^9+7.

🧠 Quiz

Với n = 10, kết quả 2^10 mod 10^9+7 bằng bao nhiêu?

[ ] 100
[x] 1024
[ ] 1023
[ ] 17

Giải thích: 2^10 = 1024 < 10^9+7, nên kết quả chính là 1024. Áp dụng trực tiếp binary exponentiation.

💡 Gợi ý tiếp cận

Đây là bài áp dụng trực tiếp power_mod(2, n, 10^9+7). Chú ý:

n lên tới 10^18 → phải dùng long long (C++/Java) hoặc int64 (Go).
Base case: 2^0 = 1.

python

n = int(input())
print(pow(2, n, 10**9 + 7))

Bài 2 — Intermediate: Tính C(n, k) mod p

Cho n, k (1 ≤ k ≤ n ≤ 10^6) và p = 10^9+7, tính C(n, k) mod p.

Input: Hai số n, k trên một dòng. Output: Giá trị C(n, k) mod p.

🧠 Quiz

Để tính C(n, k) mod p hiệu quả với nhiều truy vấn, kỹ thuật nào phù hợp nhất?

[ ] Dùng tam giác Pascal — O(n²)
[ ] Tính trực tiếp n!/(k!(n-k)!) rồi mod
[x] Precompute factorial + inverse factorial, trả lời O(1) mỗi truy vấn
[ ] Dùng Lucas theorem cho mọi trường hợp

Giải thích: Precompute fact[] trong O(n) và inv_fact[] trong O(n), sau đó C(n,k) = fact[n] × inv_fact[k] × inv_fact[n-k] mod p trong O(1). Lucas theorem chỉ cần khi p nhỏ.

💡 Gợi ý tiếp cận

Precompute fact[0..n] bằng vòng lặp.
Tính inv_fact[n] = power_mod(fact[n], p-2, p).
Tính ngược inv_fact[i] = inv_fact[i+1] × (i+1) mod p từ n-1 về 0.
Trả lời: fact[n] × inv_fact[k] × inv_fact[n-k] mod p.

python

n, k = map(int, input().split())
MOD = 10**9 + 7
fact, inv_fact = precompute(n)
print(nCr(n, k, fact, inv_fact))

Bài 3 — Advanced: Số bước đi trên lưới

Cho lưới m × m và ma trận kề A biểu diễn đồ thị có hướng. Tính số đường đi có đúng k bước từ đỉnh u đến đỉnh v, modulo 10^9+7. Giới hạn: m ≤ 50, k ≤ 10^18.

🧠 Quiz

Phương pháp tối ưu để đếm đường đi dài k trên đồ thị m đỉnh là gì?

[ ] DFS/BFS duyệt tất cả đường đi — O(m^k)
[ ] Quy hoạch động — O(m² × k)
[x] Lũy thừa ma trận kề — O(m³ log k)
[ ] Thuật toán Dijkstra

Giải thích: A^k[u][v] cho số đường đi dài đúng k từ u đến v. Tính A^k bằng binary exponentiation trên ma trận m×m trong O(m³ log k).

💡 Gợi ý tiếp cận

Đây là ứng dụng kinh điển của lũy thừa ma trận:

Ma trận kề A có A[i][j] = 1 nếu có cạnh từ i đến j.
A^k[i][j] = số đường đi dài đúng k bước từ i đến j.
Mở rộng hàm mat_mul và mat_pow cho ma trận m×m thay vì 2×2.
Chú ý: phép nhân ma trận m×m tốn O(m³), tổng cộng O(m³ log k).

Liên kết học tiếp

Thuật ngữ chính:

Thuật ngữ	Giải thích
Binary Exponentiation	Tính lũy thừa bằng cách phân tích số mũ thành nhị phân, bình phương liên tiếp
Modular Exponentiation	Tính `a^b mod m` — giữ kết quả trong phạm vi mod sau mỗi phép nhân
Matrix Exponentiation	Áp dụng binary exponentiation cho phép nhân ma trận
Fermat's Little Theorem	`a^(p-1) ≡ 1 (mod p)` khi `p` nguyên tố, `gcd(a,p) = 1`
Modular Inverse	Số `x` sao cho `a·x ≡ 1 (mod m)`, tính bằng `a^(m-2) mod m` khi `m` nguyên tố
Square-and-Multiply	Tên gọi khác của binary exponentiation — mô tả hai thao tác cơ bản
Pisano Period	Chu kỳ lặp lại của dãy Fibonacci modulo `m`

Lũy thừa nhanh — Từ O(n) xuống O(log n) ​

Bức tranh tư duy ​

Nhân đôi thay vì nhân từng cái một ​

Phân tích square-and-multiply ​

Cốt lõi kỹ thuật ​

Binary Exponentiation — Phiên bản lặp (Iterative) ​

Binary Exponentiation — Phiên bản đệ quy (Recursive) ​

Nghịch đảo modular — Định lý Fermat nhỏ ​

Lũy thừa ma trận (Matrix Exponentiation) ​

Fibonacci O(log n) bằng lũy thừa ma trận ​

Tổ hợp modular — C(n, k) mod p ​

Thực chiến ​

Kịch bản 1: RSA Encryption/Decryption Demo ​

Kịch bản 2: Fibonacci thứ 10^18 mod 10^9+7 ​

Sai lầm điển hình ​

❌ Sai lầm 1: Overflow khi nhân trước khi mod ​

❌ Sai lầm 2: Quên base case exp = 0 ​

❌ Sai lầm 3: Dùng Fermat inverse khi mod không nguyên tố ​

❌ Sai lầm 4: Dùng int thay vì long long ​

Under the Hood ​

Tại sao O(log n) hoạt động ​

Chi phí phần cứng ​

Bảng so sánh hiệu năng ​

Khi nào lũy thừa ma trận là quá mức cần thiết ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1 — Foundation: Tính 2^n mod 10^9+7 ​

Bài 2 — Intermediate: Tính C(n, k) mod p ​

Bài 3 — Advanced: Số bước đi trên lưới ​

Liên kết học tiếp ​

Lũy thừa nhanh — Từ O(n) xuống O(log n)

Bức tranh tư duy

Nhân đôi thay vì nhân từng cái một

Phân tích square-and-multiply

Cốt lõi kỹ thuật

Binary Exponentiation — Phiên bản lặp (Iterative)

Binary Exponentiation — Phiên bản đệ quy (Recursive)

Nghịch đảo modular — Định lý Fermat nhỏ

Lũy thừa ma trận (Matrix Exponentiation)

Fibonacci O(log n) bằng lũy thừa ma trận

Tổ hợp modular — C(n, k) mod p

Thực chiến

Kịch bản 1: RSA Encryption/Decryption Demo

Kịch bản 2: Fibonacci thứ 10^18 mod 10^9+7

Sai lầm điển hình

❌ Sai lầm 1: Overflow khi nhân trước khi mod

❌ Sai lầm 2: Quên base case exp = 0

❌ Sai lầm 3: Dùng Fermat inverse khi mod không nguyên tố

❌ Sai lầm 4: Dùng int thay vì long long

Under the Hood

Tại sao O(log n) hoạt động

Chi phí phần cứng

Bảng so sánh hiệu năng

Khi nào lũy thừa ma trận là quá mức cần thiết

Checklist ghi nhớ

Bài tập luyện tập

Bài 1 — Foundation: Tính 2^n mod 10^9+7

Bài 2 — Intermediate: Tính C(n, k) mod p

Bài 3 — Advanced: Số bước đi trên lưới

Liên kết học tiếp