第4期 杨先伟，等：随机序列的扑克检测优化研究 .515. 1),因此以下分析执行一组样本检测时1)所需的运 数据并更新频数，即 算量。在m=4和m=8时1)需分别执行n次 SHIFT、n次LOAD和2n次ADD,即合计总共需执行 C[E]=c[E]+1,0≤i≤g-1(5) 2n次SHIFT、2n次LOAD和4n次ADD。1)进行一 参数m=4时的频数统计方式为先加载字节数 组样本检测所需执行的操作数详情如表1。 据，接着获取高半字节和低半字节， 表1扑克检测算法的操作数量 Table 1 The calculation of poker test H=E≥4L=E,N0F,0≤i≤ -1(6) 步骤1 运算量 最后利用获取的高半字节和低半字节更新对应 m=4 nSHIFT nLOAD +2nADD 的频数，即 m=8 nSHIFT +nLOAD +2nADD C4[H]=C4[H]+1,C4[L]=C4[L]+1(7) 合计 2nSHIFT +2nLOAD +4nADD 参数m=4时和m=8时的统计过程分开实现 会使得待检数据序列重复加载，这也是扑克检测效 按我国随机性检测规范规定一组样本的大小n为 率不高的主要原因之一。如果能更进一步将参数在 10bit,因此由表1的统计结果可知，算法的运算量不 两种不同取值时的统计过程合并在一起，则可以减 小，执行效率不会太快。在实际检测中，需要加快扑克 少大量的数据重复加载。参数m取4和8合并实 检测的执行速度，以增强它的基础筛选作用。 现时的频数统计方式为先加载字节数据，然后获取 3 优化思想和优化算法 高半字节和低半字节，最后更新m=4的频数和m= 8的频数，合并式(5)~(7)，可得 根据上一节的分析可知，扑克检测的效率不高 的主要原因是计算统计量时出现了以下问题： H=E:≥4，L=E:∧0xF,0≤i≤n/8-1 1)采用了单比特统计方式，每次仅仅处理一个 C4[H]=C4[H]+1,C4[L]=C4[L]+1 比特，CPU的字长没有得到充分利用：如果一次处 Cs[E:]=Cs[E;]+1 (8) 理多个比特则处理速度将有明显的提升： 统计量的计算和判断过程还可以进行精简和优 2)对参数m=4和m=8,传统实现方式会各执 化：可根据余不完全伽马函数的性质预先求出 行一遍算法中的1)~4)的操作，存在相同数据反复 P.le≥a时统计量V的阈值，让统计值V直接和此 加载的情况： 阈值比较，如此可以减少余不完全伽马函数的计算 3)算法的统计量计算和判断过程没有精简和 次数。 优化，存在不必要的余不完全伽马函数的计算。 记m=4时的统计量为V,即 15 针对扑克检测原算法出现的效率不高问题，下 -642c,[)-4 (9) 面有针对性地提出几点优化想法。具体的优化想法 n 0 如下： 记m=8时的统计量为V,即 255 1)一次处理多个比特，比如一个字节或半个字 -2048 (10) 节，加快频数统计过程： n =0 2)对m=4和m=8整合在一起实现，减少不必 计算统计值所用的余不完全伽马函数满足性质 要的数据加载： igame(a,0)=1,igamc(a,o)=0。经简单计算可 3)精简并优化统计量的计算和判断过程，事先 知，当显著水平α=0.01，m=4时，统计量V,的阈值 计算P≥a时统计量V的阈值，让统计值直接和 为入4=30.577914：当显著水平a=0.01,m=8时， 此阈值比较，避免每个样本都计算两次余不完全伽 统计量V.的阈值为入g=310.457388。即如果V,< 马函数。 入，且'。<入g则认为待检序列通过检测。根据以上 记待检序列为n/8字节的字节数据E:,E:= 描述，优化实现的扑克检测算法如下。 E+:‖E数+2‖…‖eg:+8,0≤i≤n/8-1。为区分两 算法1优化实现的扑克检测算法 种不同参数取值时各种序列模式出现的频数，记 输入n/8字节的数据E:,0≤i≤n/8-1: C.[],0≤i≤15为m=4时各种序列模式出现的 输出检测结果。 频数，记Cg[i],0≤i≤255为m=8时各种序列模 1)初始化数据：i=0。 式出现的频数。 C4[j]=0,0≤j≤15， 参数m=8时的频数统计方式为直接加载字节 Cg[j]=0,0≤j≤255。１），因此以下分析执行一组样本检测时 １）所需的运 算量。 在 ｍ ＝ ４ 和 ｍ ＝ ８ 时 １） 需分别执行 ｎ 次 ＳＨＩＦＴ、ｎ 次 ＬＯＡＤ 和 ２ｎ 次 ＡＤＤ，即合计总共需执行 ２ｎ 次 ＳＨＩＦＴ、２ｎ 次 ＬＯＡＤ 和 ４ｎ 次 ＡＤＤ。 １）进行一 组样本检测所需执行的操作数详情如表 １。 表 １ 扑克检测算法的操作数量 Ｔａｂｌｅ １ Ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｐｏｋｅｒ ｔｅｓｔ 步骤 １ 运算量 ｍ ＝ ４ ｎＳＨＩＦＴ ＋ ｎＬＯＡＤ ＋２ｎＡＤＤ ｍ ＝ ８ ｎＳＨＩＦＴ ＋ｎＬＯＡＤ ＋２ｎＡＤＤ 合计 ２ｎＳＨＩＦＴ ＋２ｎＬＯＡＤ ＋４ｎＡＤＤ 按我国随机性检测规范规定一组样本的大小 ｎ 为 １０ ６ ｂｉｔ，因此由表 １ 的统计结果可知，算法的运算量不 小，执行效率不会太快。 在实际检测中，需要加快扑克 检测的执行速度，以增强它的基础筛选作用。 ３ 优化思想和优化算法 根据上一节的分析可知，扑克检测的效率不高 的主要原因是计算统计量时出现了以下问题： １）采用了单比特统计方式，每次仅仅处理一个 比特，ＣＰＵ 的字长没有得到充分利用；如果一次处 理多个比特则处理速度将有明显的提升； ２）对参数 ｍ ＝ ４ 和 ｍ ＝ ８，传统实现方式会各执 行一遍算法中的 １） ～４）的操作，存在相同数据反复 加载的情况； ３）算法的统计量计算和判断过程没有精简和 优化，存在不必要的余不完全伽马函数的计算。 针对扑克检测原算法出现的效率不高问题，下 面有针对性地提出几点优化想法。 具体的优化想法 如下： １）一次处理多个比特，比如一个字节或半个字 节，加快频数统计过程； ２）对 ｍ ＝ ４ 和 ｍ ＝ ８ 整合在一起实现，减少不必 要的数据加载； ３）精简并优化统计量的计算和判断过程，事先 计算 Ｐｖａｌｕｅ ≥ α 时统计量 Ｖ 的阈值，让统计值直接和 此阈值比较，避免每个样本都计算两次余不完全伽 马函数。 记待检序列为 ｎ ／ ８ 字节的字节数据 Εｉ ， Εｉ ＝ ε８ｉ＋１‖ε８ｉ＋２‖…‖ε８ｉ＋８ ， ０ ≤ ｉ ≤ ｎ ／ ８ － １。 为区分两 种不同参数取值时各种序列模式出现的频数，记 Ｃ４ ［ｉ］，０ ≤ ｉ ≤ １５ 为 ｍ ＝ ４ 时各种序列模式出现的 频数，记 Ｃ８ ［ｉ］，０ ≤ ｉ ≤ ２５５ 为 ｍ ＝ ８ 时各种序列模 式出现的频数。 参数 ｍ ＝ ８ 时的频数统计方式为直接加载字节 数据并更新频数，即 Ｃ８ ［Ｅｉ］ ＝ Ｃ８ ［Ｅｉ］ ＋ １，０ ≤ ｉ ≤ ｎ ８ － １ （５） 参数 ｍ ＝ ４ 时的频数统计方式为先加载字节数 据，接着获取高半字节和低半字节， Ｈ ＝ Ｅｉ ≫ ４，Ｌ ＝ Ｅｉ ∧ ０ｘＦ，０ ≤ ｉ ≤ ｎ ８ － １ （６） 最后利用获取的高半字节和低半字节更新对应 的频数，即 Ｃ４ ［Ｈ］ ＝ Ｃ４ ［Ｈ］ ＋ １，Ｃ４ ［Ｌ］ ＝ Ｃ４ ［Ｌ］ ＋ １ （７） 参数 ｍ ＝ ４ 时和 ｍ ＝ ８ 时的统计过程分开实现 会使得待检数据序列重复加载，这也是扑克检测效 率不高的主要原因之一。 如果能更进一步将参数在 两种不同取值时的统计过程合并在一起，则可以减 少大量的数据重复加载。 参数 ｍ 取 ４ 和 ８ 合并实 现时的频数统计方式为先加载字节数据，然后获取 高半字节和低半字节，最后更新 ｍ ＝ ４ 的频数和 ｍ ＝ ８ 的频数，合并式（５） ～ （７），可得 Ｈ ＝ Ｅｉ ≫ ４，Ｌ ＝ Ｅｉ ∧ ０ｘＦ，０ ≤ ｉ ≤ ｎ ／ ８ － １ Ｃ４ ［Ｈ］ ＝ Ｃ４ ［Ｈ］ ＋ １，Ｃ４ ［Ｌ］ ＝ Ｃ４ ［Ｌ］ ＋ １ Ｃ８ ［Ｅｉ］ ＝ Ｃ８ ［Ｅｉ］ ＋ １ （８） 统计量的计算和判断过程还可以进行精简和优 化：可根 据 余 不 完 全 伽 马 函 数 的 性 质 预 先 求 出 Ｐｖａｌｕｅ ≥α 时统计量 Ｖ 的阈值，让统计值 Ｖ 直接和此 阈值比较，如此可以减少余不完全伽马函数的计算 次数。 记 ｍ ＝ ４ 时的统计量为 Ｖ４ ，即 Ｖ４ ＝ ６４ ｎ ∑ １５ ｉ ＝ ０ Ｃ４ ［ｉ］ ２ ( ) － ｎ ４ （９） 记 ｍ ＝ ８ 时的统计量为 Ｖ８ ，即 Ｖ８ ＝ ２ ０４８ ｎ ∑ ２５５ ｉ ＝ ０ Ｃ８ ［ｉ］ ２ ( ) － ｎ ８ （１０） 计算统计值所用的余不完全伽马函数满足性质 ｉｇａｍｃ（α，０） ＝ １， ｉｇａｍｃ（α，¥） ＝ ０。 经简单计算可 知，当显著水平 α ＝ ０．０１， ｍ ＝ ４ 时，统计量 Ｖ４ 的阈值 为 λ４ ＝ ３０．５７７ ９１４；当显著水平 α ＝ ０．０１， ｍ ＝ ８ 时， 统计量 Ｖ８ 的阈值为 λ８ ＝ ３１０．４５７ ３８８。 即如果 Ｖ４ ＜ λ４ 且 Ｖ８ ＜ λ８ 则认为待检序列通过检测。 根据以上 描述，优化实现的扑克检测算法如下。 算法 １ 优化实现的扑克检测算法 输入 ｎ ／ ８ 字节的数据 Εｉ，０ ≤ ｉ ≤ ｎ ／ ８ － １； 输出 检测结果。 １）初始化数据： ｉ ＝ ０。 Ｃ４ ［ｊ］ ＝ ０， ０ ≤ ｊ ≤ １５， Ｃ８ ［ｊ］ ＝ ０， ０ ≤ ｊ ≤ ２５５。 第 ４ 期 杨先伟，等：随机序列的扑克检测优化研究 ·５１５·