# Questions tagged [pseudo-random-generators]

Questions about algorithms that deterministically generate sequences of numbers that have stochastic properties of random sequences.

137 questions
Filter by
Sorted by
Tagged with
47 views

### Does P=BPP implies we can construct a Boolean circuit for a fair coin flip?

I would precisely like to know if the conjecture BPP=P implies the following: Is it possible to build a classical Boolean circuit whose outputs are statistically indistinguishable from a fair coin ...
• 101
61 views

### Generate random points such that no 4 lie on a circle

In $\tilde{O}(n)$ time, can I generate $n$ random lattice points so that no four lie on the same circle? You can assume we pick points from a grid of side length $k \gg n$ (say, take $k=n^2$). I have ...
82 views

### Are float pseudo-random number generators always implemented using integer generators underneath

In C it's well known to use simple routine for turning integer rng into float rng. Something like that ...
• 121
1 vote
29 views

### Inefficient double lengthening PRG [closed]

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
• 141
16 views

### Why are seeds connected in Linear Congruential Generators?

I looked through Java's Random class and saw that the initial seed is created using: ...
16 views

### Randomized function with a communication size restriction

I need to create a randomized function between two participants, 1 and 2. The two participants have both n bit sized strings, and they want to determine whatever they have the same strings. 1 and 2 ...
• 101
123 views

### The awkward status of Mersenne Twister

Random number generators generally fit into 3 categories IMO: ad-hoc designs serving as stub to be replaced by something else if this ever happens, considerate designs aiming at achieving statistical ...
• 352
1 vote
61 views

### Chaitin’s version of Gödel’s theorem and pseudorandomness

Chaitin’s version of Gödel’s theorem roughly states that there exists a constant c such that for each string of one’s and zeroes x, the sentence “the algorithmic information complexity (Kolmogorov ...
227 views

### 64-bit Xorshift with 2^96 or 2^128 period

Can we create Xorshift generator, as Marsaglia in "Xorshift RNGs" does, using 64-bit numbers, but with period 2^96 or 2^128? He proposed PRNG with period 2^96: ...
• 133
43 views

### Creating a PRNG to replicate the LIbrary of Babel

I had asked a question here about this before but it had a lot of vagueness to it, so I'll rephrase the entire thing. I'm trying to create a PRNG that would replicate Borge's Library of Babel, i.e. ...
29 views

### PRNG with output of constant length

forgive me if my question is vaguely phrased. I’m fishing around for a PRNG algorithm which generates numbers of a constant length, regardless of the seed. I tried experimenting with a LCG but ...
1 vote
51 views

### Are there applications in which random number generation quality is the bottleneck?

Random number generators commonly found in default libraries are actually pseudo-random number generators. Nevertheless, more sophisticated options exist to gather entropy from "truly"-...
• 171
1 vote
80 views

### Why can't we just compose PRGs to get better PRGs?

I'm learning about (complexity-theoretic) pseudorandom number generators, and I have a pretty basic question about them that I couldn't find an answer to. Let's say we have a PRG for $P$ that can fool ...
• 378
32 views

### How to create random pseudo samples from a non-stationary time series containing NaNs using Monte-Carlo method?

I am looking for answers creating 500 samples of non-stationary Time series based on its probability distribution preferably using monte-carlo simulation. DATA LINK Secondly, the most example ...
130 views

### What is the connection between the Mersenne-Twister and Linear Congruential Generator?

This video claims that the Mersenne-Twister is based on the Linear Congruential Generator. The math in the Mersenne-Twister original paper is a bit too much for me. I have not seen that claim ...
5k views

### Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?

PRNGs (pseudorandom number generators) generally have a bit length for the binary numbers they generate (e.g. 32 bits, 64 bits). This is the universe of their possible numbers. It seems that they ...
66 views

### Algorithm for generating sorted lists of random floats

More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output ...
112 views

### Picking a pseudo random number generator

I'm looking for what I think is a random number generator, it should have the following properties, but I'm completely uncertain how to look for a suitable algorithm. I'd appreciate either pointers to ...
• 103
146 views

### Uniformly random decimal numbers

Due to finite precision of number representations, we face situations like: In: 0.1+0.1+0.1==0.3 Out: False (on my ...
38 views

### Examples of cryptographic methods using outside randomness

Most cryptographic protocols like pseudorandom number generators run only on "internal" information: that is you set a seed and the next state is a function of its previous state etc.. I am ...
• 291
347 views

### Some questions about RANDOM(a, b)

This is a question from CLRS: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of $a$ ...
• 411
1 vote
122 views

• 33
1k views

### What are the advantages of using PRNG over TRNG?

True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will ...
• 118
641 views

### How large is the seed in an encryption algorithm such as stream cipher?

The stream cipher is an encryption algorithm that was designed to approximate an idealized cipher, known as the One-Time Pad. It's crucial for a stream cipher to remain secure is to have a ...
• 118
1 vote
73 views

### Computational indistinguishability for any distribution using a Chernoff bound

I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
• 249
1 vote
38 views

### Generating a fast permutation function over an integer range

Is there a way to generate a bijection over integers $F : [0..n) \rightarrow [0..n)$ that satisfies the properties: $n$ is arbitrarily chosen and can be any positive integer $F$ generates a ...
87 views

### Simple way to extend period of LCG (expected cycle length)?

Let's consider 128-bit pseudorandom generator. From Harris 1960, if we model uniform random permutation, we know that every period length $l$ has equal probability $1/n$ (Eq. 5.2) for any particular ...
• 133
30 views

### Is there a way to measure the maximum random bits of the outputs of a generator?

I want to give examples to explain want I want to know first. Let $G \colon s \mapsto G(s)$ be a PRG. Let $F_{1} \colon s \mapsto G(s) \Vert b$, where $b = \bigoplus_{k = 1}^{|G(s)|} G(s)[k]$. ...
• 623
1 vote
73 views

### Hardness of boolean functions

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of ...
• 246
1 vote
85 views

### Check if a linear function or an affine function can be a pseudo random function

Let $G = \{0, \cdots , p-1 \}$ be a field. Let $K = G^{m \times n}$ and $F:K \times G^n \to G^m$ be a family of functions. For $A \in G^{m \times n}$ and $x \in G^n$ we have $F(A,x) = Ax$. I need to ...
• 325
97 views

### How does random number probabilities work in distributed systems?

Let's say I have a code which does coin toss at 25% win probability. If I run this code n number of times in the same system it will yield ~25% win. If I run this code on n devices (once each) will ...
• 101
1 vote
148 views

• 23
43 views

### Generation of pseudorandom floating point numbers on floating point vector DSP

I am working on a custom IEEE754 floating point vector signal processor with 64 cores and need to generate pseudo-random floating point numbers at high rate. The only numerical operation available to ...
441 views

### Oracle separation P and BPP

I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in ...
• 723
1k views

### If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?

I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear ...
• 133
1 vote
58 views

### Simple generator of pseudo-random permutations of variable length short sequence

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to ...
• 125
3k views

### How Fibonacci LFSR work

What is "Fibonacci" about the Fibonacci LFSR? If I read right, Fibonacci LFSR means that it depends on its two last states, but from the example in Wikipedia it doesn't look like two states are taken ...
• 307
4k views

### Predicting the next number output by a random number generator

Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence? For example, ...
• 21
594 views

### Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$?

For the Mersenne Twister prng, wikipedia, I feel the period exponent should be the size of the MT array, $32\cdot 624 = 19968$. How come the exponent is 19937 instead?
• 133
142 views

### Kolmogorov randomness for Pseudo random number generator

I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate ...
490 views

### Concatenated pseudorandom generators

I have two pseudorandom generators $G_1$ and $G_2$ from $k$ bit to $2k$ bit. I have another PRG $G_3$ from $k$ to $2k$ bits. Now I buildup a new function from $k$ to $4k$ as follows: Let $x$ be $k$ ...
• 313
1 vote