数论基础教程¶

数论是研究整数性质的数学分支，是计算机科学和密码学的重要基础。本教程将带你学习数论的基本概念和算法。

第一章：数论基本概念¶

（一）整除和约数¶

整除的定义：对于整数 a 和 b（b ≠ 0），如果存在整数 q，使得 a = b × q，则称 b 整除 a，记作 b | a。此时，a 称为 b 的倍数，b 称为 a 的约数（或因数）。

基本性质：

如果 a | b 且 b | c，则 a | c（传递性）
如果 a | b 且 a | c，则 a | (b ± c)
如果 a | b，则对于任意整数 k，有 a | (k × b)

代码实现（判断整除）：

def is_divisible(a, b):
    """判断 b 是否整除 a"""
    if b == 0:
        return False
    return a % b == 0

# 示例
print(is_divisible(12, 3))  # True
print(is_divisible(12, 5))  # False

求约数：

def get_divisors(n):
    """获取 n 的所有约数"""
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

# 示例
print(get_divisors(12))  # [1, 2, 3, 4, 6, 12]
print(get_divisors(16))  # [1, 2, 4, 8, 16]

约数个数：

def count_divisors(n):
    """计算 n 的约数个数"""
    count = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            if i == n // i:
                count += 1
            else:
                count += 2
    return count

# 示例
print(count_divisors(12))  # 6
print(count_divisors(16))  # 5

（二）质数和合数¶

质数的定义：大于 1 的正整数，如果只有 1 和它本身两个约数，则称为质数（素数）。否则称为合数。

质数的性质：

2 是唯一的偶质数
大于 2 的质数都是奇数
任何大于 1 的整数都可以唯一地表示为质数的乘积（算术基本定理）

质数判断：

import math

def is_prime(n):
    """判断 n 是否为质数"""
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# 示例
print(is_prime(2))    # True
print(is_prime(17))   # True
print(is_prime(15))   # False

埃拉托斯特尼筛法（求质数）：

def sieve_of_eratosthenes(n):
    """埃拉托斯特尼筛法：求小于等于 n 的所有质数"""
    if n < 2:
        return []

    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False

    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, n + 1, i):
                sieve[j] = False

    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

# 示例
print(sieve_of_eratosthenes(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

线性筛法（欧拉筛）：

def linear_sieve(n):
    """线性筛法：求小于等于 n 的所有质数"""
    if n < 2:
        return []

    primes = []
    is_composite = [False] * (n + 1)

    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)

        for p in primes:
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                break

    return primes

# 示例
print(linear_sieve(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

（三）最大公约数和最小公倍数¶

最大公约数（GCD）：能够同时整除两个或多个整数的最大正整数。

最小公倍数（LCM）：能够被两个或多个整数同时整除的最小正整数。

GCD 与 LCM 的关系：对于正整数 a 和 b：

GCD(a, b) × LCM(a, b) = a × b

欧几里得算法（求 GCD）：

def gcd(a, b):
    """使用欧几里得算法求最大公约数"""
    while b:
        a, b = b, a % b
    return abs(a)

# 示例
print(gcd(12, 18))  # 6
print(gcd(15, 25))  # 5

扩展欧几里得算法：

def extended_gcd(a, b):
    """扩展欧几里得算法
    返回 (gcd, x, y)，使得 a*x + b*y = gcd(a, b)
    """
    if b == 0:
        return abs(a), 1 if a > 0 else -1, 0

    gcd_val, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1

    return gcd_val, x, y

# 示例
gcd_val, x, y = extended_gcd(12, 18)
print(f"GCD: {gcd_val}, x: {x}, y: {y}")  # GCD: 6, x: -1, y: 1
print(f"验证: 12*{x} + 18*{y} = {12*x + 18*y}")  # 验证: 12*-1 + 18*1 = 6

求最小公倍数（LCM）：

def lcm(a, b):
    """求最小公倍数"""
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)

# 示例
print(lcm(12, 18))  # 36
print(lcm(15, 25))  # 75

第二章：模运算¶

（一）模运算的基本概念¶

同余的定义：对于整数 a、b 和正整数 m，如果 m | (a - b)，则称 a 与 b 模 m 同余，记作 a ≡ b (mod m)。

模运算的性质：

自反性：a ≡ a (mod m)
对称性：如果 a ≡ b (mod m)，则 b ≡ a (mod m)
传递性：如果 a ≡ b (mod m) 且 b ≡ c (mod m)，则 a ≡ c (mod m)
加法性质：如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则 a + c ≡ b + d (mod m)
乘法性质：如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则 a × c ≡ b × d (mod m)

代码实现：

def mod_add(a, b, m):
    """模加法：(a + b) mod m"""
    return (a + b) % m

def mod_sub(a, b, m):
    """模减法：(a - b) mod m"""
    return (a - b) % m

def mod_mul(a, b, m):
    """模乘法：(a × b) mod m"""
    return (a * b) % m

def mod_pow(a, b, m):
    """模幂运算：a^b mod m（快速幂）"""
    result = 1
    a = a % m
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % m
        a = (a * a) % m
        b = b // 2
    return result

# 示例
print(mod_add(5, 7, 10))    # 2
print(mod_sub(5, 7, 10))    # 8
print(mod_mul(5, 7, 10))    # 5
print(mod_pow(2, 10, 1000)) # 24

（二）模逆元¶

模逆元的定义：对于整数 a 和正整数 m，如果存在整数 x，使得 a × x ≡ 1 (mod m)，则称 x 为 a 模 m 的逆元，记作 a^(-1) (mod m)。

存在的条件： a 模 m 有逆元的充分必要条件是 gcd(a, m) = 1。

求模逆元（扩展欧几里得算法）：

def mod_inverse(a, m):
    """求 a 模 m 的逆元"""
    gcd_val, x, y = extended_gcd(a, m)
    if gcd_val != 1:
        return None  # 逆元不存在
    else:
        return x % m

# 示例
print(mod_inverse(3, 7))   # 5 (因为 3 × 5 = 15 ≡ 1 (mod 7))
print(mod_inverse(10, 17)) # 12 (因为 10 × 12 = 120 ≡ 1 (mod 17))

费马小定理求逆元（仅当 m 为质数时）：

def mod_inverse_fermat(a, m):
    """使用费马小定理求模逆元（m 必须是质数）"""
    if not is_prime(m):
        return None
    return mod_pow(a, m - 2, m)

# 示例
print(mod_inverse_fermat(3, 7))   # 5
print(mod_inverse_fermat(10, 17)) # 12

第三章：同余方程¶

（一）线性同余方程¶

线性同余方程的形式：

a × x ≡ b (mod m)

解的条件：方程有解的充分必要条件是 gcd(a, m) | b。

求解方法：

def solve_linear_congruence(a, b, m):
    """求解线性同余方程 a × x ≡ b (mod m)"""
    gcd_val, x, y = extended_gcd(a, m)

    if b % gcd_val != 0:
        return []  # 无解

    # 通解
    x0 = (x * (b // gcd_val)) % m
    solutions = []

    # 求所有解（在 [0, m) 范围内）
    for k in range(gcd_val):
        solution = (x0 + k * (m // gcd_val)) % m
        solutions.append(solution)

    return sorted(solutions)

# 示例
print(solve_linear_congruence(3, 5, 7))  # [4]
print(solve_linear_congruence(2, 4, 6))  # [2, 5]
print(solve_linear_congruence(4, 2, 6))  # [2, 5]

（二）中国剩余定理¶

中国剩余定理：对于一组两两互质的模数 m₁, m₂, ..., mₙ，同余方程组：

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)

在模 M = m₁ × m₂ × ... × mₙ 下有唯一解。

实现方法：

def crt(equations):
    """中国剩余定理
    equations: [(a₁, m₁), (a₂, m₂), ..., (aₙ, mₙ)]
    返回：最小正整数解和模数
    """
    if not equations:
        return None, None

    # 初始解
    x = equations[0][0]
    m = equations[0][1]

    for a, mi in equations[1:]:
        # 解方程：m × k ≡ a - x (mod mi)
        gcd_val, p, q = extended_gcd(m, mi)

        if (a - x) % gcd_val != 0:
            return None, None  # 无解

        # 计算新解
        lcm = m // gcd_val * mi
        temp = ((a - x) // gcd_val) * p % (mi // gcd_val)
        x = x + m * temp
        x %= lcm
        m = lcm

    return x % m, m

# 示例
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)
equations = [(2, 3), (3, 5), (2, 7)]
solution, modulus = crt(equations)
print(f"解：{solution} (mod {modulus})")  # 解：23 (mod 105)

第四章：数论函数¶

（一）欧拉函数¶

欧拉函数 φ(n) 的定义：小于等于 n 的正整数中与 n 互质的数的个数。

性质：

如果 p 是质数，则 φ(p) = p - 1
如果 p 是质数，k ≥ 1，则 φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p)
如果 gcd(m, n) = 1，则 φ(m × n) = φ(m) × φ(n)
对于任意 n ≥ 3，φ(n) 是偶数

计算欧拉函数：

def euler_phi(n):
    """计算欧拉函数 φ(n)"""
    if n == 0:
        return 0

    result = n
    p = 2

    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n = n // p
            result = result // p * (p - 1)
        p += 1

    if n > 1:
        result = result // n * (n - 1)

    return result

# 示例
print(euler_phi(1))   # 1
print(euler_phi(7))   # 6
print(euler_phi(12))  # 4 (1, 5, 7, 11)
print(euler_phi(100)) # 40

筛法求欧拉函数：

def euler_phi_sieve(n):
    """筛法求 1 到 n 的欧拉函数"""
    phi = list(range(n + 1))
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, n + 1):
        if is_prime[i]:
            for j in range(i, n + 1, i):
                is_prime[j] = (j == i)
                phi[j] = phi[j] // i * (i - 1)

    return phi

# 示例
phi_values = euler_phi_sieve(20)
print(phi_values)  # [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]

（二）莫比乌斯函数¶

莫比乌斯函数 μ(n) 的定义： - μ(1) = 1 - 如果 n 有平方因子（即存在质数 p，使 p² | n），则 μ(n) = 0 - 如果 n 是 k 个不同质数的乘积，则 μ(n) = (-1)ᵏ

计算莫比乌斯函数：

def mobius(n):
    """计算莫比乌斯函数 μ(n)"""
    if n == 1:
        return 1

    prime_factors = set()
    temp = n

    # 分解质因数
    for i in range(2, int(n**0.5) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp = temp // i
            if count > 1:
                return 0
            prime_factors.add(i)

    if temp > 1:
        prime_factors.add(temp)

    return (-1) ** len(prime_factors)

# 示例
print(mobius(1))   # 1
print(mobius(2))   # -1
print(mobius(4))   # 0
print(mobius(6))   # 1
print(mobius(30))  # -1

第五章：数论算法¶

（一）质因数分解¶

质因数分解：

def prime_factorization(n):
    """质因数分解"""
    factors = {}

    # 处理 2 的因子
    count = 0
    while n % 2 == 0:
        count += 1
        n = n // 2
    if count > 0:
        factors[2] = count

    # 处理奇数因子
    for i in range(3, int(n**0.5) + 1, 2):
        count = 0
        while n % i == 0:
            count += 1
            n = n // i
        if count > 0:
            factors[i] = count

    # 如果剩下的 n 是质数
    if n > 1:
        factors[n] = 1

    return factors

# 示例
print(prime_factorization(12))  # {2: 2, 3: 1}
print(prime_factorization(100)) # {2: 2, 5: 2}
print(prime_factorization(17))  # {17: 1}

（二）勒让德符号¶

勒让德符号 (a/p) 的定义：对于奇质数 p 和整数 a： - 如果 a ≡ 0 (mod p)，则 (a/p) = 0 - 如果 a 是模 p 的二次剩余，则 (a/p) = 1 - 如果 a 是模 p 的二次非剩余，则 (a/p) = -1

计算勒让德符号：

def legendre_symbol(a, p):
    """计算勒让德符号 (a/p)"""
    a = a % p
    if a == 0:
        return 0

    # 欧拉判别法
    result = mod_pow(a, (p - 1) // 2, p)
    if result == p - 1:
        return -1
    return result

# 示例
print(legendre_symbol(2, 7))   # 1 (2 是模 7 的二次剩余)
print(legendre_symbol(3, 7))   # -1 (3 是模 7 的二次非剩余)
print(legendre_symbol(5, 11))  # 1

（三）离散对数¶

离散对数问题：给定质数 p、原根 g 和整数 y，求 x 使得 gˣ ≡ y (mod p)。

婴儿-巨步算法（求解离散对数）：

def baby_step_giant_step(g, y, p):
    """婴儿-巨步算法求解离散对数
    求 x 使得 g^x ≡ y (mod p)
    """
    import math

    m = int(math.ceil(math.sqrt(p - 1)))

    # 婴儿步：计算 g^j (mod p)，j ∈ [0, m-1]
    table = {}
    current = 1
    for j in range(m):
        if current not in table:
            table[current] = j
        current = (current * g) % p

    # 巨步：计算 y * g^(-im) (mod p)，i ∈ [0, m-1]
    inv_g_m = mod_inverse(mod_pow(g, m, p), p)
    current = y

    for i in range(m):
        if current in table:
            x = i * m + table[current]
            if mod_pow(g, x, p) == y:
                return x
        current = (current * inv_g_m) % p

    return None  # 无解

# 示例
# 2^x ≡ 3 (mod 13)
g, y, p = 2, 3, 13
x = baby_step_giant_step(g, y, p)
print(f"离散对数：{x}")  # 4 (因为 2^4 = 16 ≡ 3 (mod 13))

第六章：应用实例¶

实例1：RSA 加密算法¶

import random

def generate_keypair(p, q):
    """生成 RSA 密钥对"""
    n = p * q
    phi = (p - 1) * (q - 1)

    # 选择 e
    e = 65537  # 常用值
    while gcd(e, phi) != 1:
        e = random.randrange(2, phi)

    # 计算 d
    d = mod_inverse(e, phi)

    # 公钥 (e, n)，私钥 (d, n)
    return ((e, n), (d, n))

def encrypt(message, public_key):
    """RSA 加密"""
    e, n = public_key
    # 将消息转换为数字
    m = int.from_bytes(message.encode(), 'big')
    c = mod_pow(m, e, n)
    return c

def decrypt(ciphertext, private_key):
    """RSA 解密"""
    d, n = private_key
    m = mod_pow(ciphertext, d, n)
    # 将数字转换回消息
    try:
        message = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
        return message
    except:
        return None

# 示例
p, q = 61, 53  # 选择两个质数
public_key, private_key = generate_keypair(p, q)

message = "Hello, World!"
print(f"原始消息：{message}")

ciphertext = encrypt(message, public_key)
print(f"加密后的密文：{ciphertext}")

decrypted = decrypt(ciphertext, private_key)
print(f"解密后的消息：{decrypted}")

实例2：线性同余生成器（伪随机数）¶

class LCG:
    """线性同余生成器（伪随机数生成器）"""

    def __init__(self, seed, a=1103515245, c=12345, m=2**31):
        self.seed = seed
        self.a = a
        self.c = c
        self.m = m

    def next(self):
        """生成下一个随机数"""
        self.seed = (self.a * self.seed + self.c) % self.m
        return self.seed

    def random(self):
        """生成 [0, 1) 范围内的随机浮点数"""
        return self.next() / self.m

# 示例
lcg = LCG(seed=12345)
for _ in range(10):
    print(lcg.random())

第七章：练习题目¶

基础练习¶

判断一个数是否为质数
求一个数的所有约数
求两个数的最大公约数和最小公倍数
判断两个数是否互质
计算欧拉函数 φ(n)

进阶练习¶

使用筛法求一定范围内的所有质数
求解线性同余方程
使用中国剩余定理解同余方程组
计算莫比乌斯函数
质因数分解

竞赛练习¶

实现 RSA 加密算法
求解离散对数问题
实现线性同余生成器
计算 Legendre 符号
实现模幂运算（快速幂）

恭喜你完成了数论基础教程！数论是密码学和算法竞赛的重要基础，继续深入学习吧！