数学知识杂烩

素数筛选——Eratosthenes筛法

从小素数开始，找到的素数的倍数一定是合数，

prime = []
is_prime = [False] * N

def Eratosthenes(n):
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        is_prime[i] = True
    for i in range(2, n + 1):
        if is_prime[i]:
            prime.append(i)
            if i * i > n:
                continue
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

向量子空间

在线性代数中的定义：
设V是定义在域 F上的向量空间，W是 V 的向量子空间：
0 ∈ W
W ⊆ V
W 对加法和乘法封闭

四个基本子空间

线性代数中四个子空间分为：行空间、列空间、零空间（核空间）、左零空间
列空间正交于左零空间、行空间正交于零空间

线性化多项式

重要定理：
如果一个向量空间的维度（秩）是 $d$，那么必定存在一个唯一的、最高次幂为 $x^{q^d}$ 的线性化多项式，使得这个空间里所有的元素代入该多项式后，结果全都是 0。

核的定义：
设线性化多项式：$L(x)=a_0x+a_1x^q+a_2x^{q^2}+…+a_dx^{q^d}$ （向量空间的秩是d）
定义一个映射：$L:$$F_{q^n} -> F_{q^n}$
那么它的核是：$ker(L)={x∈F_{q^n}​∣L(x)=0}$

拉格朗日插值多项式

构造公式：
(1)$$
P(x) = \sum_{i=1}^{n} y_i \prod_{\substack{j=1 \ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}
$$
(2)
$$
P(x) = \sum_{i=1}^{n} y_i*L(x),L(x)=\prod_{\substack{j=1 \ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}
$$

给定平面上的n个点(x1,y1)(x2,y2)...(xn,yn)（所有x不相同），拉格朗日插值多项式是唯一一个次数不超过n-1的多项式P(x)，满足：
$$
P(x_i)=y_i(i=1,…,k)
$$

同态

对于群同态，单位元一定映射到单位元

Sophie Germain 素数

p = 2q + 1，其中 p 和 q 都是素数，且 2 模 p 生成一个阶为 q 的群。

1. p 是安全素数（safe prime）：p = 2q+1 且 p、q 都素，此时 q 叫 Sophie Germain 素数。这意味着模 p 的乘法群 ℤₚ* 的阶为 p−1 = 2q，它的子群结构只有三种：阶 1、阶 2、阶 q——没有其他因子，这就是密码学里喜欢它的原因（比如 Schnorr 签名、DSA、ElGamal 取子群时，小的光滑因子攻击不存在）。

2. “2 生成阶为 q 的群”：即元素 2 在 ℤₚ* 中的阶是 q：

   $2^q≡1(modp)，且对任意0<k<q, 2^k≢1(modp)$

   也就是说 2 是二次剩余子群（QR subgroup）的生成元——QR 子群恰好有 q 个元素，2 是它的原根。

3. 隐含信息：既然 2^q ≡ 1 (mod p)，说明 2 是 QR（欧拉判别：2^((p−1)/2) = 2^q ≡ 1），等价于勒让德符号 (2/p) = 1，即 p ≡ ±1 (mod 8)。