哈希运算时 为什么m用质数时可以使哈希值更加随机发生更少的碰撞
时间: 2023-02-09 21:26:03 浏览: 75
当m为质数时,哈希值更加随机是因为质数更好地避免了数值之间的相关性。使用质数作为哈希表的大小可以减少数值之间的相关性,从而减少碰撞的可能性。因为质数不能被整除,所以在计算哈希值时不会存在整除的情况,从而使哈希值的分布更加均匀。
相关问题
在数字签名中经过哈希运算之后的哈希值是怎么转换为可以与多项式计算的
在数字签名中,经过哈希运算之后的哈希值需要被转换为可以进行多项式计算的形式,这个过程称为哈希值编码。在NTRUSign签名算法中,哈希值编码采用的是多项式环上的编码方式。
具体地,将哈希值分成若干个长度为$\log_2 q$比特的块,每个块作为多项式$F$的系数,组成一个$\log_2 q$比特的多项式。这里,$q$是NTRUSign算法中的模数,通常为一个较大的质数。
接下来,需要将这个多项式$F$编码为一个新的多项式$G$,使得$G$可以在多项式环上进行计算。NTRUSign算法中采用的是切比雪夫多项式变换(Chebyshev polynomial transform)进行编码。具体地,对于$F$中的每个系数$a_i$,都可以使用切比雪夫多项式变换将其转换为一个多项式$g_i$,满足:
$$g_i(x) = a_i T_i(x) \bmod q$$
其中,$T_i(x)$为切比雪夫多项式,满足$T_i(\cos(\frac{k\pi}{n}))=\cos(\frac{ik\pi}{n})$,$k=0,1,\ldots,n-1$。这里,$n$是多项式的次数,通常为$2^k$的形式。
最后,将所有的多项式$g_i$按照系数顺序组合成一个新的多项式$G$,作为最终的哈希值编码。这样,就可以将哈希值转换为可以在多项式环上进行计算的形式,以便进行数字签名的计算。
哈希值计算31怎么来的
哈希值计算31通常被用作哈希表中的哈希函数,该函数被设计为将任意长度的输入(如字符串或数字)映射到固定大小的哈希值上。基于大量实验,31被发现是一个较好的质数作为哈希函数的乘数。
31的选择有几个原因:
1. 31是一个质数。使用质数可以减少哈希冲突的可能性。
2. 31可以被计算机高效地处理。在使用哈希函数时,乘法比取模运算的速度要快,因此31被选择作为哈希函数的乘数。
3. 对于长度不超过10的字符串,31的效果被证明是很好的。因此,它被广泛地使用。
因此,在使用哈希函数时,31可以很好地平衡质数的选择与高效的计算。