1
$\begingroup$

In Professor Boneh's online Cryptography course at Coursera, I am a little puzzled by his definition of a statistical test where he writes:

A(x) = iff |#0(x) - #1(x)| <= 10.√n

Now, if – as an example – we were to perform this test on a string of $100$ bits, then $10$ multiplied by the square root of $100$ is… $100$. But if we had a hundred $0$s in this string and no $1$s then A would output $1$, i.e. would judge the string as random.

Am I perhaps misunderstanding something?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Your understanding of what the formula means seems right to me. This test is designed with much more than 100 bits in mind, and I would say aims at having an extremely low false-positive rate. $\endgroup$
    – fgrieu ♦
    Commented Apr 5, 2014 at 13:30
  • 2
    $\begingroup$ An extremely low false positive rate; when I attempt to estimate the probability of a false positive of a truly random long string, I get something on the order of $10^{-88}$ $\endgroup$
    – poncho
    Commented Apr 5, 2014 at 13:42

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.