Tag Info

47

For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator. Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating but it's a terrible generator of random digits, since the answer is "always" zero, occasionally one, and never anything else. We don't actually know if every ...

29

It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.

28

Wow, great question! Let me try to explain the resolution. It'll take three distinct steps. The first thing to note is that the entropy is focused more on the average number of bits needed per draw, not the maximum number of bits needed. With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of ...

17

The most obvious disadvantage is the unnecessary complexity of PRNG algorithms based on irrational numbers. They require much more computations per generated digit than, say, an LCG; and this complexity typically grows as you go further in the sequence. Calculating 256 bits of π at the two-quadrillionth bit took 23 days on 1000 computers (back in 2010) - a ...

7

(updated after many people pointed out that random number generator is not the same thing as a single normal sequence) If you ask whether you can get a normal sequence out of $\pi$ (i.e., all numbers appear uniformly), then there are several answers on mathoverflow. For example, the answer about Distribution of the digits of Pi says: ...it is believed ...

5

There is no such test. All automated tests for examining the randomness of a PRNG have limitations. If you read some papers in the literature that propose PRNGs, you might notice that they do more than just run an automated test against their scheme. Of course you can always write up anything at any time. For the research community to find it interesting,...

4

The key property that we want from (non-cryptographic) pseudorandom numbers is that they "look" independent. In particular, say you have some algorithm that requires a PRNG to perform well and you give it a current time function as a PRNG. Then, if the algorithm repeatedly queries what is supposed to be a PRNG, it will actually see that it gets the same ...

3

You already proved in First part that using random assignments to the values it solves $\frac{m}{2}$ equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability $\frac{1}{2}$ on every random assignment. So we can use the following algorithm to solve this problem: E = Unsolved equations (...

3

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.

3

If you want just some basic ideas what you might test. The simplest test just generates a million random numbers and puts them into say 100 buckets depending on their value. Each bucket should contain about 10,000 random numbers. If not, your random number generator is off. However, just generating 1, 2, 3, 4, 5, ... will pass this test, so it's not a very ...

3

it seems that you're asking why bother with reservoir sampling when you're capable of tricking the test that you wrote? Round robin doesn't return random numbers. It returns numbers deterministically. Well much more deterministic seeming than reservoir/other methods. Your tests should be better. If you need the result to seem random and not deterministic, ...

2

Purely randomness is not possible but in real-world the most randomness that a neural network can process is enough to discover an approximation pattern; the precision depends on the model of the context (exactitude of the Digital Twins) and processing power. To extract the exact pattern from the pure randomness (I think) is impossible even with a quantum ...

2

You can think this backwards: consider the problem of binary encoding instead of generation. Suppose that you have a source that emits symbols $X\in \{A,B\}$ with $p(A)=2^{-N}$, $p(B)=1-2^{-N}$. For example, if $N=3$, we get $H(X)\approx 0.54356$. So (Shannon tells us) there is an uniquely decodable binary encoding $X \to Y$, where $Y \in \{0,1\}$ (data ...

2

I can't argue with the second paragraph of D.W.'s answer, and D.W. is right that all tests have limitations: That's intrinsic to PRNG-testing. But TestU01 is still pretty much state of the art. You can use the NIST suite, too, which includes some tests not in TestU01, I believe. You might want to skim L'Ecuyer and Simard's paper on TestU01 and O'Neill's ...

2

It's not random. It increases by 1 every milliseconds. In computer terms, it stays unchanged for a loooooong time (millions of clock cycles). But current system time in milliseconds is most definitely not good enough anyway. If an attacker knows that you seeded a random number generator some time today, there are only 86 million possible seed values. ...

2

There's really no way to do this. First, the website generating the password would need to be open source, or at least publish what algorithm they use. Supposing they do that, then we would need to know the "inputs" to the algorithm. That would depend on their source of randomness: it might be the microsecond that your query was submitted, or it might be ...

1

Consider a graph with $n$ vertices and $m$ edges. Let $\mathcal{D}$ be a pairwise independent distribution over $\{0,1\}^n$, and suppose that $x = (x_1,\ldots,x_n) \sim \mathcal{D}$. For every edge $(i,j)$, the probability that it is cut in the cut corresponding to $x$ is $$\Pr[x_i \neq x_j] = \frac{1}{2},$$ due to pairwise independence. Therefore the ...

1

It provides a good random number right until you realize how it was produced, as with many pseudo random number. The irrational (non algebraic and non transcendental) numbers you have chosen are common and so easier guessed then others. I can see no issue with this method provided you choose less commonly seen generators.

1

In general, this approach does not work: "randomness" does not mean that you get a lot of different digits, but there are other aspects as well. For example, a classic test is to see if all two-digit, or three-digit etc. combinations occur with the same frequency. This would be a very simple test, which can rule out obvious non-random results, but is still ...

1

Let's first clarify the scenario. What you're basically asking is why it is more likely to randomly write a computer program that outputs the works of Shakespeare than writing the works of Shakespeare directly. The simple answer to this is that there are many ways to write a program that outputs a fixed string, but only one way to directly write this string....

Only top voted, non community-wiki answers of a minimum length are eligible