本文需要一点抽象代数基础, 需要了解群环域, 同态与同构相关概念和相关定理 抽象代数的应用举例 椭圆加密 前置 考虑椭圆曲线方程: $$ y^2 \equiv x^3+ax+b \pmod p (a,b \in F_p, 4a^3+27b^2 \not\equiv 0 \pmod p )$$将加法如下定义: 如果点$ P(x_1,y_1), Q(x_2,y_2) $在曲线上, 经过两点的直线能唯一交于曲线上的第三个点$ R(x_3,y_3) $, 再对这个点做关于x轴的对称点即可得到$-R(x_3,-y_3)$(即定义取逆为做关于x轴的对称点), 即: $$ P+Q=-R $$我们稍微需要一点射影几何的知识, 考虑椭圆曲线在射影坐标$ [X:Y:Z] $, 在射影坐标中$ [X:Y:Z] $与$ [\lambda X:\lambda Y:\lambda Z] $等价, 或者说它们属于同一个等价类 当$Z \neq 0 $时, 此时射影坐标下的$ [X:Y:Z] $可以对应到坐标$ (\frac{X}{Z},\frac{Y}{Z}) $(此时对应的射影坐标为$ [\frac{X}{Z}:\frac{Y}{Z}:1] $) 下面我们将给出这种加法构成一个群的证明 其中封闭性, 交换律如下: 两点确定的直线与椭圆曲线的交点依旧在椭圆曲线上, 而曲线明显关于x轴对称, 所以对称操作也不会影响封闭性 交换两个点等价于一个求$P$和$Q$确定的直线, 另外一个求$Q$和$P$确定的直线, 这显然不会改变所确定的直线, 因而不会改变第三个点 单位元与逆元 对于单位元, 我们定义射影平面的无穷远点$\mathcal{O} $为单位元 ...
[Kolmogorov Complexity]0 序言
本系列参考的内容主要来自教材《An Introduction to Kolmogorov Complexity and Its Applications》, 外加ai的辅助阅读, 旨在介绍柯尔莫哥洛夫复杂度(Kolmogorov Complexity)的含义, 数学细节, 以及相关应用. 感谢Gemini, 以及其它ai还有我某些不愿意透露姓名的朋友帮助. 什么是Kolmogorov Complexity(KC)？ 在给出概念的定义, 我们先来看几个例子. 考虑二进制字符串: $$ 00000000000000000000000000,\\ 01000110110000010100111001,\\ 10010011011000111011010000 $$从概率上来看, 这三个字符串产生的概率是相同的, 均为 $2^{-26}$ , 但从人类直观出发, 会觉得第一个字符串更规律. 如果你的注意力不那么涣散的话, 还能留意到第二个序列由$0,1,00,01,10,11,000,...$生成, 而第三个序列是真实的抛一枚硬币所产生的. 从传统概率论的角度来看, 这三者生成的概率是一样的, 但从直觉出发, 前两个序列更加的简单. 而实际上这种直觉也并不是错觉, 在python语言中, 对于第一个式子, 我们有: print("0"*26) 但对于剩下两个式子, 我们大概率很难将其缩减为像上面这个式子这么简短的形式. 因此, 我们可以粗略用生成一个字符串程序长度来衡量这个字符串的随机性. 显然, 一个字符串存在着很多种生成办法, 为便于比较, 我们不严谨地定义: 在给定描述方法U下, 生成一段字符串x的最短描述长度称为这个字符串的柯尔莫哥洛夫复杂度(Kolmogorov Complexity), 记为$K_U(x)$ 描述方法严格定义实际上需要是一个通用图灵机, 而且必须是无前缀的(设 $P$ 是图灵机 $M$ 所有能使其停机的输入字符串（程序）的集合。如果对于 $P$ 中的任意两个不同的字符串 $p_1$ 和 $p_2$，$p_1$ 都不是 $p_2$ 的前缀，那么图灵机 $M$ 就被称为无前缀图灵机。). ...