网站 设计 案例 简单,小程序如何快速推广,合肥新闻 今天 最新消息,培训网页制作机构信息安全中的数论速通
此版数论增加了#xff0c;丰富了相关内容#xff0c;更加精炼 md文档自取#xff0c;可以私我#xff0c;公式懒得调了#xff0c;vsc打开没问题
数论中重要定理速览 算术基本定理#xff1a;每一个大于1的自然数都可以唯一地分解为素数的乘积。…信息安全中的数论速通
此版数论增加了丰富了相关内容更加精炼 md文档自取可以私我公式懒得调了vsc打开没问题
数论中重要定理速览 算术基本定理每一个大于1的自然数都可以唯一地分解为素数的乘积。 素数定理描述了素数在自然数中的分布。(会单独讲解) 费马小定理如果$ p 是一个素数 , 是一个素数, 是一个素数,a$是任意整数那么 a p ≡ a ( m o d p ) a^p \equiv a \pmod{p} ap≡a(modp)。 欧拉定理如果 a a a和 n n n互质那么 a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)} \equiv 1 \pmod{n} aϕ(n)≡1(modn)其中$ \phi(n) $是欧拉函数。 贝祖等式对于任意整数$ a 和 和 和 b 存在整数 存在整数 存在整数 x 和 和 和 y 使得 使得 使得 ax by \gcd(a, b) $。 中国剩余定理如果$ n_1, n_2, \ldots, n_k 是两两互质的整数那么对于任意整数 是两两互质的整数那么对于任意整数 是两两互质的整数那么对于任意整数 a_1, a_2, \ldots, a_k 存在一个整数 存在一个整数 存在一个整数 x 使得 使得 使得 x \equiv a_i \pmod{n_i} 对于所有的 对于所有的 对于所有的 i $。 狄利克雷定理对于任意两个互质的正整数$ a 和 和 和 d 存在无穷多个形如 存在无穷多个形如 存在无穷多个形如 a nd $的素数。 二次互反律描述了两个不同素数的勒让德符号之间的关系。 高斯整数环的基本定理每一个非零的高斯整数都可以唯一地分解为素数的乘积。 莫比乌斯反演公式如果 f ( n ) f(n) f(n)和$ g(n) 是算术函数并且它们满足 是算术函数并且它们满足 是算术函数并且它们满足 f(n) \sum_{d|n} g(d) 那么 那么 那么 g(n) \sum_{d|n} \mu(d) f\left(\frac{n}{d}\right) 其中 其中 其中 \mu $是莫比乌斯函数。 素数分布的切比雪夫界限提供了素数分布的上界和下界。 哥德巴赫猜想每一个大于2的偶数都可以写成两个素数之和。这是一个猜想尚未被证明或证伪 孪生素数猜想存在无穷多对素数它们之间的差为2。这也是一个猜想 四平方和定理每一个自然数都可以表示为四个整数平方的和。 五次方程的阿贝尔-鲁菲尼定理五次或更高次的多项式方程没有一般的代数解法。
素数在自然数中的分布是数论中一个非常重要的研究领域。素数是指只能被1和它本身整除的大于1的自然数例如2、3、5、7、11等。以下是一些描述素数分布的重要定理和猜想 素数定理Prime Number Theorem 素数定理描述了素数在自然数中的渐近分布。它指出小于或等于给定数$ x 的素数数量记作 的素数数量记作 的素数数量记作 \pi(x) 大约等于 大约等于 大约等于 \frac{x}{\ln(x)} $。数学上表达为 $ \pi(x) \sim \frac{x}{\ln(x)} $ 这意味着当$ x 趋向于无穷大时 趋向于无穷大时 趋向于无穷大时 \pi(x) 与 与 与 \frac{x}{\ln(x)} $的比值趋向于1。 素数定理的精确形式 素数定理的精确形式给出了误差项。它表明 $ \pi(x) \text{Li}(x) O\left(\frac{x}{\ln^2(x)}\right) $ 其中$ \text{Li}(x) 是 L o g a r i t h m i c I n t e g r a l 函数 是Logarithmic Integral函数 是LogarithmicIntegral函数 O $表示大O符号描述了误差的上界。 素数定理的强形式 素数定理的强形式进一步细化了误差项例如 $ \pi(x) \text{Li}(x) O\left(x \exp(-c (\ln x)^{3/5} (\ln \ln x)^{-1/5})\right) $ 其中$ c $是一个常数。 素数定理的等分布性质 素数定理还涉及到素数在算术级数中的分布。例如对于任意固定的整数$ a 和 和 和 q 如果 如果 如果 \gcd(a, q) 1 那么在 1 到 那么在1到 那么在1到 x 之间形如 之间形如 之间形如 a nq 其中 其中 其中 n $是非负整数的素数数量也大致符合素数定理的形式。 切比雪夫界限 切比雪夫给出了素数分布的两个重要界限。他证明了存在常数$ A 和 和 和 B $使得 $ A \frac{x}{\ln(x)} \pi(x) B \frac{x}{\ln(x)} $ 对于足够大的$ x $。 素数定理的推广 素数定理可以推广到更广泛的数域和代数结构中例如代数数域中的素理想分布。 素数分布的猜想 还有一些关于素数分布的重要猜想例如 哥德巴赫猜想每一个大于2的偶数都可以写成两个素数之和。孪生素数猜想存在无穷多对素数它们之间的差为2。
质数与互质数
质数Prime Number
质数也称为素数是指大于1的自然数中除了1和它本身以外没有其他因数的数。换句话说一个质数只有两个正因数1和它本身。例如2、3、5、7、11都是质数。最小的质数是2它也是唯一的偶数质数因为除了2之外的所有偶数都至少可以被2整除因此不是质数。
质数的特点
质数大于1。质数只有两个正因数1和它本身。1不是质数因为它只有一个因数。除了2以外所有的质数都是奇数。
判断一个数是否为质数的方法
检查这个数是否能够被2到它的平方根之间的任何整数整除。如果不能被整除则该数是质数。
互质数Coprime Numbers
互质数也称为互素数是指两个或多个整数的最大公约数GCD为1的数。如果两个整数的公因数只有1那么这两个整数就是互质的。
互质数的特点
两个连续的正整数总是互质的。如果两个数互质那么它们的任何倍数也是互质的。如果两个数互质且其中一个数与第三个数互质那么另外两个数也互质。
判断两个数是否互质的方法
使用辗转相除法欧几里得算法来计算两个数的最大公约数。如果最大公约数是1那么这两个数就是互质的。检查两个数是否有共同的质因数。如果没有那么这两个数就是互质的。
互质数的特殊情况
1和任何大于1的自然数都是互质的。两个不同的质数总是互质的。相邻的两个自然数是互质的。2和任何奇数都是互质的。一个奇数和因数只有2的偶数都是互质的。两个数中的较大一个是质数这两个数一定是互质的。两个数中的较小一个是质数而较大数是合数且不是较小数的倍数这两个数一定是互质的。较大数比较小数的2倍多1或少1这两个数一定是互质的。
欧拉函数
欧拉函数记作 φ ( n ) \varphi(n) φ(n)是数论中的一个重要概念它表示小于或等于 n n n 的正整数中与 n n n 互质的数的个数。以下是关于欧拉函数的详细教程
定义
对于任意正整数 n n n φ ( n ) \varphi(n) φ(n) 表示在 1 1 1 到 n − 1 n-1 n−1 范围内与 n n n 互质的正整数的个数。例如 φ ( 10 ) 4 \varphi(10) 4 φ(10)4因为 1 , 3 , 7 , 9 1, 3, 7, 9 1,3,7,9 与 10 10 10 互质。
性质
基本性质 1若 p p p 为质数则 φ ( p ) p − 1 \varphi(p) p - 1 φ(p)p−1。特别的 φ ( 1 ) 1 \varphi(1) 1 φ(1)1。基本性质 2设 n p k n p^k npk 且 p p p 为质数则 φ ( n ) n − n p p k − 1 × ( p − 1 ) p k − 1 × φ ( p ) \varphi(n) n - \frac{n}{p} p^{k-1} \times (p - 1) p^{k-1} \times \varphi(p) φ(n)n−pnpk−1×(p−1)pk−1×φ(p)。基本性质 3欧拉函数是积性函数即对于任意互质的两个正整数 m m m 和 n n n有 φ ( m n ) φ ( m ) φ ( n ) \varphi(mn) \varphi(m)\varphi(n) φ(mn)φ(m)φ(n)。基本性质 4对于数 n n n将其质因数分解为 ∏ i 1 k p i r i \prod_{i1}^{k}{p_i}^{r_i} ∏i1kpiri则 φ ( n ) ∏ i 1 k φ ( p i r i ) ∏ i 1 k ( p i r i − 1 × ( p i − 1 ) ) n × ∏ i 1 k ( 1 − 1 p i ) \varphi(n) \prod_{i1}^{k}\varphi(p_i^{r_i}) \prod_{i1}^{k}(p_i^{r_i-1} \times (p_i - 1)) n \times \prod_{i1}^{k}(1 - \frac{1}{p_i}) φ(n)∏i1kφ(piri)∏i1k(piri−1×(pi−1))n×∏i1k(1−pi1)。
公式
欧拉函数的计算公式为 $ \varphi(n) n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_n}\right) $ 其中 p 1 , p 2 , ⋯ , p n p_1, p_2, \cdots, p_n p1,p2,⋯,pn 是 n n n 的质因数。
证明
容斥原理对于任意正整数 n n n如果 n n n 只存在质因子 p p p 和 q q q则与 n n n 互质的数的集合需要除去 p , 2 p , 3 p , ⋯ , ⌊ n p ⌋ p p, 2p, 3p, \cdots, \lfloor \frac{n}{p} \rfloor p p,2p,3p,⋯,⌊pn⌋p 以及 q , 2 q , ⋯ , ⌊ n q ⌋ q q, 2q, \cdots, \lfloor \frac{n}{q} \rfloor q q,2q,⋯,⌊qn⌋q。根据容斥原理需要补回 p q pq pq 的倍数 p q , 2 p q , ⋯ , ⌊ n p q ⌋ p q pq, 2pq, \cdots, \lfloor \frac{n}{pq} \rfloor pq pq,2pq,⋯,⌊pqn⌋pq。即 φ ( n ) n − n p − n q n p q n ( 1 − 1 p ) ( 1 − 1 q ) \varphi(n) n - \frac{n}{p} - \frac{n}{q} \frac{n}{pq} n(1 - \frac{1}{p})(1 - \frac{1}{q}) φ(n)n−pn−qnpqnn(1−p1)(1−q1)。中国剩余定理可以证明欧拉函数是积性函数即对于任意互质的两个正整数 m m m 和 n n n有 φ ( m n ) φ ( m ) φ ( n ) \varphi(mn) \varphi(m)\varphi(n) φ(mn)φ(m)φ(n)。
此外还可以使用筛法来高效地计算一定范围内所有整数的欧拉函数值这种方法的时间复杂度可以达到 O ( n log log n ) O(n \log \log n) O(nloglogn)比单个计算的方法 O ( n ) O(\sqrt{n}) O(n ) 更优。
模运算
模运算涉及到整数运算其中运算的结果不是通常的整数而是除以某个正整数 $ n $ 后得到的余数。这个正整数 $ n $ 被称为模数。
定义
给定三个整数 $ a b $和 $ n $其中 $ n 0 $如果存在整数 $ k $ 使得 $ a b kn $ 则称 $ a $ 同 $ b $ 模 $ n $ 同余记作 $ a \equiv b \pmod{n} $
符号 “≡” 在数学中通常用来表示同余关系。具体来说如果两个整数 a a a 和 b b b 除以正整数 n n n 后余数相同那么我们说 a a a 同余于 b b b 模 n n n可以写作
这意味着 n n n 能够整除 a − b a - b a−b或者说 a a a 和 b b b 之间的差是 n n n 的倍数。
基本性质
自反性对于任何整数 $ a $ 和正整数 $ n $有 $ a \equiv a \pmod{n} $。对称性如果 $ a \equiv b \pmod{n} $则 $ b \equiv a \pmod{n} $。传递性如果 $ a \equiv b \pmod{n} $ 且 $ b \equiv c \pmod{n} $则 $ a \equiv c \pmod{n} $。加法性质如果 $ a \equiv b \pmod{n} $ 且 $ c \equiv d \pmod{n} $则 $ a c \equiv b d \pmod{n} $。乘法性质如果 $ a \equiv b \pmod{n} $ 且 $ c \equiv d \pmod{n} $则 $ ac \equiv bd \pmod{n} $。幂的性质如果 $ a \equiv b \pmod{n} $则对于任何正整数 $ k $有 $ a^k \equiv b^k \pmod{n} $。
应用
密码学在RSA加密算法中模运算用于加密和解密信息。算法在算法中模运算用于处理循环数组或循环链表的问题。编程语言许多编程语言提供了模运算的运算符如 %。
扩展欧几里得算法
在模运算中经常需要解决一类问题给定整数 $ a $ 和 $ n $找到一个整数 $ x $ 使得 $ ax \equiv 1 \pmod{n} $ 如果这样的 $ x $ 存在我们说 $ a $ 在模 $ n $ 下有逆元并且 $ x $ 就是 $ a $ 的模 $ n $ 逆元。扩展欧几里得算法可以用来找到这个逆元。
费马小定理
费马小定理是模运算中的一个重要定理它指出如果 $ p $ 是一个质数$ a $ 是一个不被 $ p $ 整除的整数则 $ a^{p-1} \equiv 1 \pmod{p} $ 这个定理在密码学中非常有用尤其是在RSA算法中。
欧拉定理
欧拉定理是费马小定理的推广它指出如果 $ n $ 是一个正整数$ a $ 是一个与 $ n $ 互质的整数则 $ a^{\varphi(n)} \equiv 1 \pmod{n} $ 其中 $ \varphi(n) $ 是欧拉函数表示小于或等于 $ n $ 的正整数中与 $ n $ 互质的数的个数。
同余理论
同余理论是数论中的一个核心概念它涉及到整数在模运算下的性质和行为。以下是同余理论的详细教程
定义
同余如果 m m m 是 x − a x-a x−a 的一个因子就说 x x x 和 a a a 关于模 m m m 同余并记为 x ≡ a ( m o d m ) x \equiv a \pmod{m} x≡a(modm)也等价于 m ∥ ( x − a ) m\|(x-a) m∥(x−a) 。剩余如果 x ≡ a ( m o d m ) x \equiv a \pmod{m} x≡a(modm)那么 a a a 就叫做 x x x 模 m m m 的一个剩余。最小剩余如果 0 ≤ a m 0 \le a m 0≤am那么就称 a a a 为 x x x 模 m m m 的最小剩余。同余类由与某个给定的剩余同余的所有数组成的一个类叫做同余类。完全剩余系总共有 m m m 个同余类它们分别以 0 , 1 , ⋯ , m − 1 0, 1, \cdots, m-1 0,1,⋯,m−1 作为代表任何 m m m 个分别属于这 m m m 个剩余类的数组成一个集合称为模 m m m 的一个完全剩余系简称完系 。
性质
自反性 a ≡ a ( m o d m ) a \equiv a \pmod{m} a≡a(modm)。对称性若 a ≡ b ( m o d m ) a \equiv b \pmod{m} a≡b(modm)则 b ≡ a ( m o d m ) b \equiv a \pmod{m} b≡a(modm)。传递性若 a ≡ b ( m o d m ) a \equiv b \pmod{m} a≡b(modm) b ≡ c ( m o d m ) b \equiv c \pmod{m} b≡c(modm)则 a ≡ c ( m o d m ) a \equiv c \pmod{m} a≡c(modm)。加法性质若 a 1 ≡ b 1 ( m o d m ) a_1 \equiv b_1 \pmod{m} a1≡b1(modm) a 2 ≡ b 2 ( m o d m ) a_2 \equiv b_2 \pmod{m} a2≡b2(modm)则 a 1 a 2 ≡ b 1 b 2 ( m o d m ) a_1 a_2 \equiv b_1 b_2 \pmod{m} a1a2≡b1b2(modm)。乘法性质若 a 1 ≡ b 1 ( m o d m ) a_1 \equiv b_1 \pmod{m} a1≡b1(modm) a 2 ≡ b 2 ( m o d m ) a_2 \equiv b_2 \pmod{m} a2≡b2(modm)则 a 1 a 2 ≡ b 1 b 2 ( m o d m ) a_1a_2 \equiv b_1b_2 \pmod{m} a1a2≡b1b2(modm)。特别地若 a ≡ b ( m o d m ) a \equiv b \pmod{m} a≡b(modm)则 k a ≡ k b ( m o d m ) ka \equiv kb \pmod{m} ka≡kb(modm) 。
定理
定理1如果 a ≡ b ( m o d m ) a \equiv b \pmod{m} a≡b(modm) a ≡ b ( m o d n ) a \equiv b \pmod{n} a≡b(modn)那么 a ≡ b ( m o d [ m , n ] ) a \equiv b \pmod{[m, n]} a≡b(mod[m,n]) 。定理2如果 k a ≡ k b ( m o d m ) ka \equiv kb \pmod{m} ka≡kb(modm)那么 a ≡ b ( m o d m ( k , m ) ) a \equiv b \pmod{\frac{m}{(k, m)}} a≡b(mod(k,m)m) 。定理3如果 a 1 , a 2 , ⋯ , a m a_1, a_2, \cdots, a_m a1,a2,⋯,am 是模 m m m 的一个完全剩余系且有 ( k , m ) 1 (k, m) 1 (k,m)1那么 k a 1 , k a 2 , ⋯ , k a m ka_1, ka_2, \cdots, ka_m ka1,ka2,⋯,kam 也是模 m m m 的一个完全剩余系 。
Euler函数
Euler函数 ϕ ( m ) \phi(m) ϕ(m) 表示不大于 m m m 的正整数中与 m m m 互质的个数。如果 a a a 和 m m m 互素那么在模 m m m 意义上的每一个和 a a a 同余的数都和 m m m 互素于是就有 ϕ ( m ) \phi(m) ϕ(m) 个与 m m m 互素的剩余类 。
抽象代数群、环、域
群、环和域是抽象代数中的基本概念它们是数学中研究集合和它们上定义的运算的代数结构。
群Group
定义 群是一个集合 $ G $配备一个运算通常是加法或乘法满足以下四个条件
封闭性对于所有 $ a, b \in G $运算 $ a \cdot b $ 的结果也在 $ G $ 中。结合律对于所有 $ a, b, c \in G $满足 $ (a \cdot b) \cdot c a \cdot (b \cdot c) $。单位元存在一个元素 $ e \in G $使得对于所有 $ a \in G $有 $ e \cdot a a \cdot e a $。逆元对于每个 $ a \in G $存在一个元素 $ b \in G $使得 $ a \cdot b b \cdot a e $其中 $ e $ 是单位元。
例子
整数集合 $ \mathbb{Z} $ 配合通常的加法运算构成一个群。非零有理数集合 $ \mathbb{Q}^* $ 配合乘法运算构成一个群。
性质
群的运算通常是可交换的即 $ a \cdot b b \cdot a $这样的群称为阿贝尔群Abelian group。群可以有限也可以无限。
环Ring
定义 环是一个集合 $ R $配备两个运算通常称为加法和乘法满足以下条件
$ (R, ) $ 是一个交换群。乘法运算是结合的。分配律对于所有 $ a, b, c \in R $满足 $ a \cdot (b c) a \cdot b a \cdot c $ 和 $ (a b) \cdot c a \cdot c b \cdot c $。
例子
整数集合 $ \mathbb{Z} $ 配合通常的加法和乘法运算构成一个环。多项式集合 $ \mathbb{R}[x] $ 配合多项式的加法和乘法运算构成一个环。
性质
环中的乘法运算不一定是可交换的。环可以有单位元称为环的乘法单位元也可以没有。
域Field
定义 域是一个环 $ F $其中每个非零元素都有一个乘法逆元并且满足以下条件
$ (F, ) $ 是一个阿贝尔群。$ (F \setminus {0}, \cdot) $ 是一个阿贝尔群。乘法运算是结合的。分配律对于所有 $ a, b, c \in F $满足 $ a \cdot (b c) a \cdot b a \cdot c $ 和 $ (a b) \cdot c a \cdot c b \cdot c $。
例子
有理数集合 $ \mathbb{Q} $、实数集合 $ \mathbb{R} $ 和复数集合 $ \mathbb{C} $ 都是域。有限域 $ \mathbb{F}_p $其中 $ p $ 是一个质数由 $ p $ 个元素组成也是域。
性质
域中的乘法运算是可交换的。域中的每个非零元素都有一个乘法逆元。域没有零因子即如果 $ a \cdot b 0 $则 $ a 0 $ 或 $ b 0 $。 在数学中特别是在抽象代数的域Field和环Ring理论中逆元是一个重要的概念。以下是逆元的定义和一些相关解释
域中的逆元
在域 $ F $ 中对于任意非零元素 $ a $如果存在一个元素 $ b $ 使得 $ a \cdot b b \cdot a 1 $ 其中 $ 1 $ 是域中的乘法单位元则称 $ b $ 是 $ a $ 的乘法逆元通常记作 $ a^{-1} $ 或 $ \frac{1}{a} $。
椭圆曲线
椭圆曲线的定义
椭圆曲线是定义在某个域上的曲线通常由一个三次方程定义。最常用的形式是Weierstrass方程 $ y^2 x^3 ax b $ 其中 $ a $ 和 $ b $ 是定义在该域上的常数且判别式 $ \Delta -16(4a^3 27b^2) \neq 0 $ 以确保曲线是非奇异的。这种形式的曲线称为Weierstrass正常形式 。
椭圆曲线的性质
群结构椭圆曲线上的点可以定义加法运算形成一个阿贝尔群。这个群的运算满足封闭性、结合律、存在单位元和逆元 。几何性质椭圆曲线具有水平对称性任何非垂直线与曲线的交点最多有三个 。有限域上的椭圆曲线在有限域上椭圆曲线的点集构成的群要么是循环群要么是两个循环群的直积 。
椭圆曲线上的点的操作
在椭圆曲线上定义了一种特殊的加法运算这使得曲线上的点可以进行群运算。给定两个点 $ P $ 和 $ Q $可以定义 $ P Q $ 为通过 $ P $ 和 $ Q $ 的直线与曲线的第三个交点。如果 $ P $ 和 $ Q $ 重合则通过 $ P $ 的切线与曲线的交点定义为 $ 2P $ 。
椭圆曲线的可视化
椭圆曲线可以通过格点来可视化。在复数域中存在一个从格点到椭圆曲线的双射对应关系。通过这个关系可以在椭圆曲线上进行加法运算这相当于在格点上进行模运算 。
椭圆曲线在密码学中的应用
椭圆曲线的难解问题如离散对数问题是密码学中椭圆曲线密码体制的基础。在椭圆曲线上给定一个点 $ P $ 和一个整数 $ n $找到 $ nP $ 是容易的但是反过来给定 $ P $ 和 $ nP $找到 $ n $ 却是困难的。这个单向性质使得椭圆曲线可以用于构建公钥密码体系 。 选择合适的椭圆曲线和参数在选择椭圆曲线时需要确保曲线是非奇异的并且参数 $ p $素数足够大以提供足够的安全性。同时需要确保 $ p \neq n \times h p^t \neq 1 \mod n $对于 $ 1 \leq t 20 $以及 $ 4a^3 27b^2 \neq 0 \mod p $其中 $ n $ 是基点 $ G $ 的阶$ h $ 是椭圆曲线上所有点的个数 $ m $ 与 $ n $ 相除的整数部分且 $ h \leq 4 $ 。 密钥长度ECC的一个显著优势是其密钥长度较短但仍然能提供与RSA等传统公钥密码体系相当的安全性。例如256位的ECC密钥与3072位的RSA密钥具有相似的安全级别。密钥长度的选择应基于当前的安全需求和计算能力 。 抗攻击性ECC算法需要能够抵抗各种攻击包括但不限于离散对数问题攻击、侧信道攻击如时序攻击和差分功耗分析。为了防御这些攻击可以采用恒定时间代码Constant Time Code、随机化投影坐标Randomized Projective Coordinates和标量盲化Scalar Blinding等技术 。 密钥的生成和管理密钥的生成和管理对于ECC的安全性至关重要。私钥应该是随机生成的并且保密。公钥是私钥在椭圆曲线上的点的倍数可以通过公钥进行加密但解密需要私钥 。 加密和解密过程在加密过程中发送方会使用接收方的公钥和一些随机数来加密信息。在解密过程中接收方使用自己的私钥来解密信息。这个过程的安全性依赖于椭圆曲线离散对数问题的难度 。 结合其他加密技术在某些应用中ECC可以与其他加密技术如AES结合使用以提供更高层次的安全性。例如ECC可以用于密钥交换而AES可以用于实际的数据加密和解密这种混合算法可以提高数据在云存储和传输过程中的安全性 。
编码理论
编码理论Coding Theory是信息论的一个分支它主要研究如何设计和分析编码以确保在各种信道中传输信息的可靠性和效率。编码理论的核心目标是最小化传输错误同时最大化传输速率。
1. 基本概念
信源Source产生信息的源头可以是数字、文字、图像或声音等。信道Channel信息传输的媒介可以是有线或无线的。编码Coding将信源的符号转换为适合在信道上传输的信号的过程。解码Decoding接收端将接收到的信号还原为原始信源符号的过程。错误检测和纠正Error Detection and Correction在接收端检测和修正传输过程中可能发生的错误。
2. 信源编码
无失真编码目标是无损压缩即在接收端能够完全恢复原始信息。有失真编码允许一定程度的信息失真以实现更高的压缩率。熵Entropy衡量信源信息量的一个度量理想的无失真编码长度接近信源熵。
3. 信道编码
错误检测码能够检测错误的编码如奇偶校验码。错误纠正码不仅能够检测错误还能在一定程度上纠正错误的编码如汉明码、里德-所罗门码等。信道容量Channel Capacity在特定的信道条件下能够实现无误差传输的最大数据速率。
4. 编码类型
线性码编码向量中任意两个合法编码的线性组合仍然是一个合法编码。循环码编码向量可以表示为一个多项式在某个次数上的循环移位。卷积码编码依赖于当前和过去几个时刻的输入符号。Turbo码一种高效的编码方式通过并行连接多个卷积码编码器来提高性能。低密度奇偶校验LDPC码一种具有接近香农极限性能的编码方式由稀疏奇偶校验矩阵定义。
概率论
概率论是数学的一个分支它研究随机现象的规律性为不确定性的量化提供了数学工具。
1. 概率空间
样本空间Sample Space所有可能结果的集合通常用 $ S $ 或 $ \Omega $ 表示。事件Event样本空间的一个子集表示实验结果的一个集合。概率测度Probability Measure将每个事件赋予一个概率值满足非负性、归一性和可数可加性。
2. 概率的基本性质
非负性任何事件的概率值都是非负的。归一性整个样本空间的概率为1。可数可加性对于一系列互斥事件它们并的概率等于各自概率的和。
3. 条件概率 条件概率Conditional Probability在某个事件已经发生的条件下另一个事件发生的概率。 $ P(A|B) \frac{P(A \cap B)}{P(B)} $ 其中$ P(A|B) $ 是在事件 $ B $ 发生的条件下事件 $ A $ 发生的条件概率。
4. 独立性
独立事件Independent Events两个事件的发生互不影响即一个事件的发生不会改变另一个事件的概率。两个事件 $ A $ 和 $ B $ 独立当且仅当 $ P(A \cap B) P(A) \cdot P(B) $
5. 随机变量
随机变量Random Variable将样本空间中的事件映射到实数可以是离散的或连续的。离散随机变量取值在可数集合中如整数。连续随机变量取值在实数线上的某个区间。
6. 概率分布
概率质量函数Probability Mass Function, PMF对于离散随机变量描述每个可能取值的概率。概率密度函数Probability Density Function, PDF对于连续随机变量描述概率密度。累积分布函数Cumulative Distribution Function, CDF描述随机变量取值小于或等于某个值的概率。
7. 期望值 期望值Expected Value随机变量的平均值是其概率分布的加权平均。 对于离散随机变量 $ X $ $ E(X) \sum_{x} x \cdot P(X x) $ 对于连续随机变量 $ X $ $ E(X) \int_{-\infty}^{\infty} x \cdot f(x) , dx $ 其中$ f(x) $ 是 $ X $ 的概率密度函数。
8. 方差和标准差 方差Variance衡量随机变量取值的分散程度。 对于离散随机变量 $ X $ $ \text{Var}(X) E[(X - E(X))^2] \sum_{x} (x - E(X))^2 \cdot P(X x) $ 对于连续随机变量 $ X $ $ \text{Var}(X) E[(X - E(X))^2] \int_{-\infty}^{\infty} (x - E(X))^2 \cdot f(x) , dx $ 标准差Standard Deviation方差的平方根同样衡量分散程度但与随机变量具有相同的量纲。 $ \sigma \sqrt{\text{Var}(X)} $
9. 大数定律
大数定律Law of Large Numbers随着试验次数的增加样本均值会趋近于期望值。$ \bar{X} $ 趋近于期望值 $ E(X) $ $ \lim_{n \to \infty} \frac{1}{n} \sum_{i1}^{n} X_i E(X) $
10. 中心极限定理
中心极限定理Central Limit Theorem在一定条件下大量独立同分布的随机变量之和将近似服从正态分布无论原始分布如何。如果 $ X_1, X_2, \ldots, X_n $ 是一系列独立同分布的随机变量且具有有限的均值 $ \mu $ 和方差 $ \sigma^2 $则标准化的和 $ Z \frac{\sum_{i1}^{n} X_i - n\mu}{\sigma \sqrt{n}} $ 当 $ n $ 足够大时$ Z $ 的分布近似为标准正态分布。
11. 协方差和相关性 协方差Covariance衡量两个随机变量之间的线性关系。 对于两个随机变量 $ X $ 和 $ Y \text{Cov}(X, Y) E[(X - E(X))(Y - E(Y))] $ 相关系数Correlation Coefficient标准化的协方差衡量两个随机变量之间的线性关系强度。 $ \rho_{X,Y} \frac{\text{Cov}(X, Y)}{\sigma_X \sigma_Y} $ 其中$ \sigma_X $ 和 $ \sigma_Y $ 分别是 $ X $ 和 $ Y $ 的标准差。
数理统计
数理统计是统计学的一个分支它使用概率论的概念来分析和处理数据。数理统计提供了一套工具和方法用于从样本数据中推断总体特征。
1. 基本概念
总体Population包含所有研究对象的集合。个体Individual总体中的每一个成员。样本Sample从总体中选取的一部分个体。样本容量Sample Size样本中包含的个体数量通常用 $ n $ 表示。参数Parameter描述总体特征的数值如总体均值 $ \mu $ 和总体方差 $ \sigma^2 $。统计量Statistic描述样本特征的数值如样本均值 $ \bar{x} $ 和样本方差 $ s^2 $。
2. 数据描述
集中趋势度量 均值Mean数据的平均值计算公式为 $ \bar{x} \frac{1}{n} \sum_{i1}^{n} x_i $。中位数Median将数据排序后位于中间位置的值。众数Mode数据中出现次数最多的值。 离散程度度量 方差Variance衡量数据分布的离散程度计算公式为 $ s^2 \frac{1}{n-1} \sum_{i1}^{n} (x_i - \bar{x})^2 $。标准差Standard Deviation方差的平方根。极差Range数据的最大值与最小值之差。 分布形状度量 偏度Skewness衡量数据分布的对称性。峰度Kurtosis衡量数据分布的尖峭程度。
3. 概率分布
离散型随机变量的概率分布 二项分布Binomial Distribution在固定次数的独立实验中成功次数的分布。泊松分布Poisson Distribution在固定时间或空间间隔内发生次数的分布。 连续型随机变量的概率分布 正态分布Normal Distribution一种对称的钟形分布由均值和标准差确定。均匀分布Uniform Distribution在一定区间内等概率取值的分布。
4. 抽样分布
中心极限定理Central Limit Theorem指出样本均值的分布随着样本容量的增加而趋近于正态分布无论总体分布如何。t分布t-Distribution当样本容量较小时样本均值的分布。卡方分布Chi-square Distribution卡方检验中使用的分布。F分布F-Distribution方差分析中使用的分布。
5. 参数估计
点估计Point Estimation用样本统计量来估计总体参数的单个值。区间估计Interval Estimation构建一个区间使得总体参数以一定的概率落在这个区间内。置信区间Confidence Interval区间估计的一种给出估计的可靠性如95%置信区间。
6. 假设检验
零假设Null Hypothesis $ H_0 $通常表示没有效应或没有差异的假设。备择假设Alternative Hypothesis $ H_1 $与零假设相对的假设。检验统计量Test Statistic用于决定是否拒绝零假设的统计量如t统计量或卡方统计量。P值P-value在零假设为真的前提下观察到的统计量或更极端情况出现的概率。显著性水平Significance Level $ \alpha $拒绝零假设的阈值通常取0.05或0.01。
7. 回归分析
简单线性回归Simple Linear Regression分析一个自变量和一个因变量之间的线性关系。多元线性回归Multiple Linear Regression分析多个自变量和一个因变量之间的线性关系。回归方程Regression Equation描述自变量和因变量之间关系的方程。
8. 卡方检验
拟合优度检验Goodness of Fit Test检验样本数据是否符合某种分布。独立性检验Test of Independence检验两个分类变量是否独立。
