Graph & Number theory & RSA

前半部分跟fds的Graph似乎是一样的，后半部分的数论也不是很深入.

Graph¶

Path, walk, tour之间的区别：
1. path是指无向图\(G =(V,E)\)中从\(v_1\)到\(v_n\)的一条通路，不能有重复顶点或者重复的边，但起点和终点可以不同.
2. walk比path更加宽泛，允许有重复顶点/重复边，只需要从\(v_1\)到\(v_n\).
3. tour则要求起点必须与终点一致.
Eulerian Walk&Tour / Euler's Theorem:

Eulerian Walk: 指的是恰好经过\(G\)的所有边一次的walk

Eulerian Tour: 指的是起点与终点相同的Eulerian Walk

（经常记混，这里辅助理解的方法是，tour是有目的性的旅行，常有“回到出发点”的意思）

添加到上面的表格中就是：

no repeated vertices no repeated edges start = end

Eulerian Walk \(\checkmark\)

Eulerian Tour \(\checkmark\) \(\checkmark\)

Euler's Theorem: 无向图\(G = (V,E)\)有Euler tour的充分必要条件是\(G\)的度数为偶数且\(G\)连通.

这是判别graph是否存在Euler Tour的方法，证明如下：
Tips
1. 必要性（Only if）
  
  假设图 \(G\) 存在欧拉回路.
  
  连通性：欧拉回路经过图中每条边恰好一次，因此所有有边的顶点都在这个回路上，它们彼此连通. 孤立顶点（度数为0）不影响欧拉回路的存在性. 所以 \(G\) 是连通的（忽略孤立顶点）.
  
  度数为偶数：考虑欧拉回路中的任意顶点 \(v\). 每当回路进入顶点 \(v\) 时，必定会从 \(v\) 离开（包括起点/终点，因为是回路）. 因此，与 \(v\) 关联的边可以配对成"进入-离开"的形式. 这意味着 \(v\) 的度数必定是偶数.
2. 充分性（If）
  
  假设图 \(G\) 连通（忽略孤立顶点）且所有顶点度数均为偶数，证明存在欧拉回路.
  
  构造性证明（算法）：
  1. 基础情况：从任意顶点 \(v\) 开始，由于所有顶点度数为偶数，我们可以构造一个回路：
    - 从 \(v\) 出发，每次经过一条未使用的边
    - 由于每个顶点度数为偶数，每次"进入"一个顶点时，总有未使用的边可以"离开"
    - 最终必定回到起点 \(v\)（因为度数为偶数保证了配对性）
    设这个回路为 \(C\).
  2. 递归构造：如果回路 \(C\) 已经覆盖了所有边，则 \(C\) 就是欧拉回路，证明完成.
  3. 否则，存在未被 \(C\) 覆盖的边. 由于 \(G\) 连通，必存在某个顶点 \(u\) 在 \(C\) 上，且 \(u\) 关联着未被 \(C\) 使用的边.
  4. 构造新回路：考虑删除 \(C\) 中的边后得到的图 \(G'\)：
    - \(G'\) 中每个顶点的度数仍为偶数（因为 \(C\) 在每个顶点"进入"和"离开"的次数相同，减少了偶数条边）
    - 从顶点 \(u\) 开始，在 \(G'\) 中构造一个新回路 \(C'\)（使用步骤1的方法）
  5. 合并回路：将回路 \(C\) 和 \(C'\) 在顶点 \(u\) 处合并：
    - 沿着 \(C\) 走，当到达 \(u\) 时，走完整个 \(C'\)，然后继续沿 \(C\) 走
    - 得到一个更大的回路，覆盖了更多的边
  6. 迭代：重复步骤2-5，直到所有边都被覆盖. 由于每次迭代至少增加一条边，且边的数量有限，算法必定终止，得到欧拉回路.
判定是否存在Euler Walk的条件更为宽泛：

"An undirected graph has an Eulerian walk if and only if it is connected (except for isolated vertices) and has at most two odd degree vertices. Note that there is no graph with only one odd degree vertex (you can prove this using the degree-sum formula)."

翻译过来就是，无向图在连通的前提下，节点的度数放宽到了最多允许2个节点度数为奇数. 证明如下：
Tips

证明：
1. 必要性
  
  假设存在一条Euler Walk从\(u\)开始，到\(v\)结束（\(u\neq v\)），那么所有在这条路径上的顶点彼此相连，而所有不在这条路径上的顶点（如果有的话）必定是孤立的.
  
  因此，该图是连通的（除了孤立顶点）. 此外，在这条路径中每次中间访问一个顶点时，都会与两条边配对，因此，除了\(u\)和\(v\)之外，所有其他顶点的度数必定是偶数.
2. 充分性
  
  首先，一个没有奇度顶点的连通图存在Euler Tour就意味着存在Euler Walk. 因此只需要考虑恰有两个奇度顶点的情况.
  1. 解法1：取两个奇度顶点\(u\)和\(v\)，添加一个顶点\(w\)以及两条边\((u,w)\)和\((w,v)\)，得到的图\(G'\)只有偶度顶点（我们给\(u\)和\(v\)的度数各加了1，并引入了一个度数为2的顶点），并且仍然是连通的.
    
    所以，我们可以在\(G'\)上找到一条Euler Tour. 现在，删除回路中使用边\((u,w)\)和\((w,v)\)的部分，剩余的回路部分就是原图上从\(u\)到\(v\)的Euler Walk，因为它遍历了原图上的每条边.
  2. 解法2：构造一个与图论笔记中描述的带拼接的FindTour算法非常相似的算法.
    
    假设\(G\)是连通的（除了孤立顶点）并且恰有两个奇度顶点\(u,v\). 首先删除所有孤立顶点（如果有的话）. 由于\(u\)和\(v\)属于一个连通分量，所以可以找到一条从\(u\)到\(v\)的路径\(P\)，接下来考虑从图中删除路径\(P\)的边后得到的图\(G'\).
    
    在\(G'\)中，所有顶点都有偶数度，因此对于剩余图的每个连通分量，可以找到一条Euler Tour（注意，删除路径的边后得到的图可能是不连通的）.
    
    观察到Euler Walk就是一条覆盖所有边的边不相交路径，而刚才做的是将所有边分解为\(P\)和一组边不相交的Euler Tour，其中\(P\)显然是边不相交的. 然后，给定一条边不相交的路径和一条边不相交的回路，如果它们至少共享一个公共顶点，就可以简单地在公共顶点处用回路扩充路径，将它们组合成一条边不相交的路径. 因此，我们可以将所有边不相交的Euler Tour组合到从\(u\)到\(v\)的路径中，构成一条从\(u\)到\(v\)的Euler Walk. ~~（Claude机翻+我微调的，表述上比较奇怪）~~

Number theory¶

Extended gcd：考虑方程\(ax+by = \operatorname{gcd}(a,b)\)，我们希望在已知\(a,b\)的条件下得知\(x,y\)的值.

这个问题的处理的理论基石之一是辗转相除法的原理，即\(\operatorname{gcd}(a,b) = \operatorname{gcd}(b,a\%b) = \cdots etc.\)

我们先考虑\(b = 0\)的情形，此时\(\operatorname{gcd}(a,0) = a\)，于是容易得出\(\begin{cases} x = 1 \\ y = 0\end{cases}.\)

接着不妨设\(a>b>0\)，于是\(a = bq_1+r\).

考虑递归的数量关系，倒退一步到\(bx_1 + ry_1 = \operatorname{gcd}(b,r) = \operatorname{gcd}(a,b)\)

代入\(r = a-bq\)，得到

\[bx_1+ (a-bq)y_1 = \operatorname{gcd}(b,r) \Longrightarrow ay_1 + b(x_1-qy_1) = \operatorname{gcd}(b,r)\Longrightarrow \begin{cases} x = y_1 \\ y = x_1-(a//b) y_1 \end{cases}\]

以此类推可知，当\((a,b) \rightarrow (b,r_1) \rightarrow (r_1,r_2) \rightarrow \cdots \rightarrow(r_k,0)\)终止时，

\[(x,y) \rightarrow (x_1,y_1) \rightarrow \cdots\rightarrow(x_{k+1}= 1,y_{k+1} = 0)\]

就是最终结果. 所以我们只需要每次迭代完成：

\[\textcolor{red}{\begin{cases} x_{i} = y_{i+1} \\ y_i = x_{i+1}-(r_{i-1} // r_i) y_{i+1} \end{cases}}\]

的计算即可，Python代码如下：
```
def extendgcd(a, b):       # a > b >= 0 
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extendgcd(b, a % b)
        return (g, y, x - (a//b)*y)
```
Wilson Theorem：对于素数\(p\)，有 \((p-1)! \equiv -1 \pmod{p}\)；反之若\((p-1)! \equiv -1 \pmod{p}\)，则\(p\)是素数.

证明：
1. \(p\)为素数时，首先考虑在\(\{2,3,\cdots,p-2\}\)集合中任意选取一个
2. 若\((p-1)! \equiv -1 \pmod{p}\)，则\(p\)一定是素数，否则设\(p = q*M\)，其中\(q\)是素数；

RSA¶

直接参考CTF-crypto下的笔记即可.

	no repeated vertices	no repeated edges	start = end
Eulerian Walk		\(\checkmark\)
Eulerian Tour		\(\checkmark\)	\(\checkmark\)