日常学习笔记

SHA256

哈希是一种能将不同的输入映射为独一无二的定长字符串的算法，如果对于不同的输入，映射为同一字符串，则称之为哈希碰撞(collision).
对于哈希碰撞，我们可以记住这样一个公式

50%概率发生哈希碰撞的计算次数

$m =\sqrt{(\frac{\pi }{2}N)}$

N为哈希值的二进制位数，对于 SHA256 来说，它会生成32字节，64长度的16进制字符串，256位（每个字符取值范围为[0-9a-z]）

对于生日来说可以计算出它50%概率发生碰撞所需要的计算次数为23.9
同时也要记住另一个公式

哈希碰撞概率公式

$p(n,d)\approx 1 - e^{\frac{-n(n-1)}{2d}}$

n为计算次数，d为取值空间，该公式推导过程中用到了泰勒公式 $e^x \approx 1+x$

我们假设G中的每个顶点V都被赋予了一个标记L(V),它要么是一个数，要么是∞。假设P是G的顶点的集合，P包含S，满足：

1）如果V属于P，则L（V）是从S到V的最短通路的长度，并且存在这样的从S到V的最短通路：通路上的顶点都在P中

2）如果V不属于P，则L(V)是从S到V的满足下面限制的最短通路的长度：V是通路中唯一一个不属于P的顶点。

先找出不在P中且带有最小标记的顶点U，标记为L(U), 可以证明从S到U的最短通路中除U外不包含不属于P的元素。

因为若存在除U外其他顶点，先假如果最短通路U前最后一个点为Q且不属于P ，则最短通路为SP1P2...PnQU(P1,P2..Pn属于P,Q不属于P),则由性质2）最短通路长度为L(Q)+PATH(Q,U)>L(U)

从而大于SP1P2..PnU的通路长度L(U)，不是最短通路，所以从S到U的最短通路中除U外不包含不属于P的元素，从而从S到U的最短通路长度由L(U)给出.

以上证明了最短路终点的前一个顶点一定属于P