Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python implementation of the runs cryptographic test for randomness
def independent_runs(self, bin_data: str):
"""
Note that this description is taken from the NIST documentation [1]
[1] http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf
The focus of this tests if the total number of runs in the sequences, where a run is an uninterrupted sequence
of identical bits. A run of length k consists of k identical bits and is bounded before and after with a bit of
the opposite value. The purpose of the runs tests 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 tests determines whether the
oscillation between zeros and ones is either too fast or too slow.
:param bin_data: a binary string
:return: the p-value from the test
"""
ones_count, n = 0, len(bin_data)
for char in bin_data:
if char == '1':
ones_count += 1
p, vobs = float(ones_count / n), 1
tau = 2 / math.sqrt(len(bin_data))
if abs(p - 0.5) > tau:
return 0.0
else:
for i in range(1, n):
if bin_data[i] != bin_data[i - 1]:
vobs += 1
# expected_runs = 1 + 2 * (n - 1) * 0.5 * 0.5
# print("\t", Colours.Italics + "Observed runs =", vobs, "Expected runs", expected_runs, Colours.End)
num = abs(vobs - 2.0 * n * p * (1.0 - p))
den = 2.0 * math.sqrt(2.0 * n) * p * (1.0 - p)
p_val = spc.erfc(float(num / den))
return p_val
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment