Skip to content

Instantly share code, notes, and snippets.

# StuartGordonReid/Runs.py Created Aug 25, 2015

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   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
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.