nist_sp_800_22_tests.py 文件源码

def discrete_fourier_transform(generator, n_bits, misc=None):
    """Discrete Fourier Transform (Spectral) Test.

    Test purpose as described in [NIST10, section 2.6]:
    "The focus of this test is the peak heights in the Discrete Fourier Transform of the sequence.
    The purpose of this test is to detect periodic features (i.e., repetitive patterns that are near
    each other) in the tested sequence that would indicate a deviation from the assumption of
    randomness. The intention is to detect whether the number of peaks exceeding the 95 % threshold
    is significantly different than 5 %."
    """
    if n_bits < 1000:
        print("Warning: Sequence should be at least 1000 bits long", file=stderr)

    x = [1 if generator.random_bit() else -1 for _ in range(n_bits)]
    s = fft(x)  # S = DFT(X)
    # print(s)
    m = abs(s)[0:n_bits // 2]  # modulus(S')
    # print("m =", m)
    t = sqrt(log(1 / 0.05) * n_bits)  # the 95% peak height threshold value
    n_0 = 0.95 * n_bits / 2  # expected theoretical number of peaks under t
    n_1 = len([1 for p in m if p < t])
    d = (n_1 - n_0) / sqrt(n_bits * 0.95 * 0.05 / 4)
    p_value = erfc(abs(d) / sqrt(2))

    if type(misc) == dict:
        misc.update(m=m, t=t, n_0=n_0, n_1=n_1, d=d)

    return p_value