较长的专题文章

从0证明RSA RSA 算法（即一个非对称加密算法）除了应用非常广泛外，其特性也非常吸引人（起码非常吸引我）。我在网上找了很多关于RSA的证明，要么不够详细（例如缺失对前置定理的证明），要么需要引出较多复杂的数论概念。作者本身水平不高，试图绕过这些复杂的概念，从初等数学的开始，完备地证明RSA。 关于RSA的背景知识可能很多，可以慢慢阅读，我在此尝试从初等数学开始证明。这些背景知识的证明有一定的顺序，如果读者发现某个证明看不懂，可以向前翻阅。 参考的文章如下：（因为参考的文章太多，大概率不全） 费马小定理 中国剩余定理 阮一峰的博客——RSA算法原理（一） 阮一峰的博客——RSA算法原理（二） 初等数论笔记Part 1： 欧拉定理 算法学习笔记(9)：逆元 费马小定理 简介 如果 $p$ 是质数且 $\mathrm{gcd}(a,p)=1$ , 那么 $a^{p-1}\equiv 1\ (\mathrm{mod}\ p)$ 在证明该定理前，先证明一个简单的引理 引理1 如果 $p$ 是质数，且 $\mathrm{gcd}(a,p)=1$ , 那么 $$ \lbrace ka \ \mathrm{mod}\ p | k = \lbrace 1,2,…,p -1 \rbrace \rbrace= \lbrace 1,2,3,…,p-1 \rbrace $$ 即二者存在一对一的关系。由于这两个集合的元素个数相同，所以只要证明左侧集合没有重复元素即可 证明：假设存在 $k_1$ 和 $k_2$ 满足 $1 \leq k_1 < k_2 \leq p-1$ ，且 $k_1a\ \mathrm{mod}\ p = k_2a\ \mathrm{mod}\ p$ ....

概述 本文介绍 PostgreSQL 中 Heap Only Tuple(HOT) 技术以及创建索引相关的知识，主要包含以下内容： HOT 的基本原理 普通的创建索引 (Create Index) 流程 同时创建索引 (Create Index Concurrently CIC) 的原理 本文不包括： btree 等索引的具体实现方式 PostgreSQL 对索引访问方式 (Access Method) 的抽象 HOT 基础 简单而言, HOT(Heap Only Tuple) 指没有索引指向的元组，用于消除元组更新引起的索引膨胀，原理如下图： 索引指向 line_ptr_1 ，line_ptr_1 指向 tuple_1 ，tuple_1 被更新后成为 tuple_2，此时 tuple_1 指向 tuple_2 索引指向 line_ptr_3 , line_ptr_3 指向 line_ptr_4 ，line_ptr_4 指向 tuple3 显然，HOT 技术具有如下优点 对于被更新的元组，无需创建新的索引指针指向新元组 旧元组可以被“普通操作”删除掉，并不一定需要 vacuum HOT 链的构建 （一）：表 tbl(x int, y int) 在 x 上有索引，先插入一行 tuple_1=(x=1, y=1) ，结果如下...