nist_sp_800_22_tests.py 文件源码

def runs(generator, n_bits, misc=None):
    """Runs Test.

    Test purpose as described in [NIST10, section 2.3]:
    "The focus of this test is the total number of runs in the sequence, where a run is an
    uninterrupted sequence of identical bits. A run of length k consists of exactly k identical bits
    and is bounded before and after with a bit of the opposite value. The purpose of the runs test
    is to determine whether the number of runs of ones and zeros of various lengths is as expected
    for a random sequence. In particular, this test determines whether the oscillation between such
    zeros and ones is too fast or too slow."
    """
    pi = 0
    v_obs = 0
    b0 = None
    for _ in range(n_bits):
        b1 = generator.random_bit()
        pi += b1
        v_obs += b0 != b1
        b0 = b1
    pi /= n_bits

    if type(misc) is dict:
        misc.update(pi=pi, v_obs=v_obs)

    if abs(pi - 1 / 2) >= 2 / sqrt(n_bits):
        return 0

    p_value = erfc(abs(v_obs - 2 * n_bits * pi * (1 - pi)) / (2 * sqrt(2 * n_bits) * pi * (1 - pi)))

    return p_value