素数与因式分解：数的基石

算术基本定理：每个整数 n > 1 都有唯一的素数分解 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ。

朴素判素法与优化

最直接的判素法：从 2 试除到 n-1。但我们只需要试到 √n——因为如果 n 有因子 d，那么 n/d 也是因子，d 和 n/d 中至少一个 ≤ √n。

package main

import (
    "fmt"
    "math"
)

// 朴素判素：O(√n)
func isPrime(n int) bool {
    if n < 2 { return false }
    if n == 2 { return true }
    if n%2 == 0 { return false }
    sqrtN := int(math.Sqrt(float64(n)))
    for i := 3; i <= sqrtN; i += 2 {
        if n%i == 0 { return false }
    }
    return true
}

// 试除法分解质因数
func factorize(n int) map[int]int {
    factors := map[int]int{}
    for p := 2; p*p <= n; p++ {
        for n%p == 0 {
            factors[p]++
            n /= p
        }
    }
    if n > 1 {
        factors[n]++
    }
    return factors
}

func main() {
    fmt.Println(isPrime(17), isPrime(18))  // true false
    fmt.Println(factorize(360))  // map[2:3 3:2 5:1]  360=2³×3²×5
}

埃拉托斯特尼筛法：批量生成素数

埃氏筛法的思路：从 2 开始，把每个素数的倍数标记为合数。时间复杂度 O(n log log n)，是生成 1 到 n 所有素数的最快实用算法。

package main

import "fmt"

// 埃拉托斯特尼筛法：返回 [2, n] 内的所有素数
func sieve(n int) []int {
    isComposite := make([]bool, n+1)
    primes := []int{}
    for i := 2; i <= n; i++ {
        if isComposite[i] {
            continue
        }
        primes = append(primes, i)
        // 从 i² 开始标记（i 以下的倍数已被更小的素数标记过）
        for j := i * i; j <= n; j += i {
            isComposite[j] = true
        }
    }
    return primes
}

func main() {
    primes := sieve(50)
    fmt.Println(primes)
    // [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47]
    fmt.Println("50 以内共", len(primes), "个素数")

    // 素数计数函数 π(n)：估计 ≈ n / ln(n)
    // π(50) ≈ 50/ln(50) ≈ 12.8，实际 15，误差合理
}

Miller-Rabin 概率素性测试

对大数（如 RSA 的 1024 位整数），试除法太慢。Miller-Rabin 是概率性测试——选 k 个随机基，如果都通过测试，那么 n 是素数的概率 ≥ 1 - 4^(-k)。实际使用 k=20 次就足够安全。

package main

import (
    "fmt"
    "math/rand"
)

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

// Miller-Rabin 单次测试
func millerTest(d, n int64) bool {
    a := 2 + rand.Int63n(n-4)
    x := powMod(a, d, n)
    if x == 1 || x == n-1 { return true }
    for d != n-1 {
        x = x * x % n
        d *= 2
        if x == 1 { return false }
        if x == n-1 { return true }
    }
    return false
}

func isPrimeMR(n int64, k int) bool {
    if n < 2 { return false }
    if n < 4 { return true }
    if n%2 == 0 { return false }
    d := n - 1
    for d%2 == 0 { d /= 2 }
    for i := 0; i < k; i++ {
        if !millerTest(d, n) { return false }
    }
    return true
}

func main() {
    fmt.Println(isPrimeMR(1_000_000_007, 20))  // true（大素数）
    fmt.Println(isPrimeMR(1_000_000_008, 20))  // false
}

RSA 加密的数论基础

RSA 的安全性依赖大整数分解的困难性：选两个大素数 p 和 q，公布 n = p×q，加密用 n 和公钥 e，解密需要知道 p 和 q——而从 n 分解出 p、q 在数学上没有已知的多项式时间算法。目前最快的分解算法是数域筛法（Number Field Sieve），复杂度是次指数级。

素数是数学中永恒的谜题，也是现代密码学的地基。

— 数论导引