Frequency Monobits Test

Kevin Perez

3/12/24, 8:32 PM

As detailed in the paper Statistical test suite for random and pseudorandom number generators for cryptographic applications by NIST, the first test is given as a basic significance test, it uses a bit sum and calculates the p-value and test statistic. But I do not have the clearest understanding of why $S_{obs}$ is defined as the sum of the sequence divided by the square root of the length of the sequence. What is the statistical rationale behind why this is done two times in order to find a z value?

1 + 0

statistical-test

randomness

Score:3

Crypto

kodlu

3/12/24, 10:31 PM

Since the test uses $X_k=\pm 1$ as its symbols, it is statistically based on the idea of a simple random walk with unknown bias (if $p=1/2$ then the bias is zero).

By the Central Limit Theorem, for an independent identically distributed sequence $X_k$ we have convergence in distribution, i.e., $$ \frac{(X_1+X_2+\cdots+X_n)-n\mathbb{E}(X)}{\sqrt{ n\sigma^2}} \stackrel{\cal D}{\longrightarrow} \cal{N}\mathrm{(0,1)}. $$ If you do some algebraic manipulation, you can see that the test statistic is exactly the left hand side and the $Z$ value is of course based on a gaussian distribution.

+ 5

Kevin Perez

3/12/24, 11:21 PM

Your answer is very good. And I believe it is helpful, but do you mind elaborating on why in the paper they divided by $\sqrt{2}$ from the test statistics in the erfc equation?

kodlu

3/12/24, 11:29 PM

Since they use absolute value, I think, going between one sided vs two sided?

Kevin Perez

3/12/24, 11:35 PM

I thought it had something to do with the positive values defined only as well, but what does it mean to be half normal? In particular, why can't they just change the significance level why does dividing by the square root of two and not 2 solve the issue?

Kevin Perez

3/13/24, 1:00 AM

I figured it out, you are right about the two-tailed. It is just that there are different gaussian distributions in the text and it was hard to make them relate when I was looking at them.

kodlu

3/13/24, 2:10 AM

great that you figured it out. you can upvote the answer if it was helpful.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Frequency Monobits Test

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.