日常学习笔记

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),它要么是一个数,要么是。假设PG的顶点的集合,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), 可以证明从SU的最短通路中除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

发表评论

邮箱地址不会被公开。 必填项已用*标注