基于原生五项式的乱数产生器

摘要

原生三项式(primitive trinomial)ｘp＋ｘq＋１广泛应用在乱数产生器的设计上，其特点是以简单的线性递回公式ｘi＝ｘi-p⊕ｘi-q产生乱数。研究发现此类乱数产生器无法通过重量分布(weight distribution)统计的检测。一般而言，采用更多项次的多项式(如原生五项式)，将大幅降低乱数产生的速度。本发明选取原生五项式ｘp＋ｘp-1＋ｘq＋ｘq-1＋１，利用ｘi-p与ｘi-(p-1)、ｘi-q与ｘi-(q-1)两两紧邻的关系，以简化计算。此一形式的速度约与三项式ｘp＋ｘq＋１相若，且产生的乱数通过重量分布的检测。

主权项

1.一种基于线性回馈移位暂存器(linear feedback shiftregisters)产生乱数的方法,其特征多项式(characteristic polynomial)采用原生五项式(primitivepentanomial)xp+xp-1+xq+xq-1+1,递回公式为Xi=(Xi-p⊕Xi-q)⊕(Xi+1-p⊕Xi+1-q)。2.如申请专利范围第1项的方法,产生乱数Xi时,由先前计算(产生乱数Xi-1时)援用Xi-p⊕Xi-q的値,并计算Xi+1-p⊕Xi+1-q的値,将二者作互斥或(exclusive or)运算即得,同时保留Xi+1-p⊕Xi+1-q的数値,以供产生乱数Xi+1时援用。