Skip to main content

Questions tagged [pseudo-random-generators]

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

Filter by
Sorted by
Tagged with
-1 votes
1 answer
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 ...
108_mk's user avatar
  • 101
4 votes
0 answers
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 ...
innocuous-squid's user avatar
2 votes
4 answers
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 ...
simd's user avatar
  • 121
1 vote
0 answers
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 ...
Stevie's user avatar
  • 141
0 votes
1 answer
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: ...
Vishal's user avatar
  • 1
0 votes
0 answers
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 ...
RT.'s user avatar
  • 101
2 votes
2 answers
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 ...
DannyNiu's user avatar
  • 352
1 vote
1 answer
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 ...
Craig Feinstein's user avatar
0 votes
3 answers
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: ...
Tom's user avatar
  • 133
0 votes
0 answers
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. ...
MUSTANGBOSS8055's user avatar
0 votes
0 answers
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 ...
MUSTANGBOSS8055's user avatar
1 vote
1 answer
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"-...
Rexcirus's user avatar
  • 171
1 vote
1 answer
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 ...
Jake's user avatar
  • 378
0 votes
0 answers
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 ...
shewag's user avatar
  • 1
0 votes
1 answer
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 ...
ColorStatistics's user avatar
18 votes
4 answers
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 ...
Rusty Fieldstone's user avatar
0 votes
1 answer
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 ...
Sas2450's user avatar
0 votes
1 answer
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 ...
JP.'s user avatar
  • 103
4 votes
0 answers
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 ...
Matthieu Latapy's user avatar
0 votes
1 answer
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 ...
user918212's user avatar
2 votes
1 answer
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$ ...
Emad's user avatar
  • 411
1 vote
0 answers
122 views

Nisan-Wigderson generator and $\mathbf P=\mathbf{BPP}$

In this set of notes it is claimed that: If there exists a polynomial-time pseudorandom generator $G:\{0,1\}^{O(\log n)}\to\{0,1\}^{O(n)}$ that $1/10$-fools all $n^2$-size circuits, then $\mathbf P=\...
asdf's user avatar
  • 33
2 votes
1 answer
191 views

Proof that pseudorandom generators implies one-way function

I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions. My understanding is that pseudorandom generators are defined as A function $...
asdf's user avatar
  • 33
0 votes
2 answers
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 ...
Monther's user avatar
  • 118
2 votes
3 answers
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 ...
Monther's user avatar
  • 118
1 vote
1 answer
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. ...
Sid Meier's user avatar
  • 249
1 vote
0 answers
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 ...
Liam White's user avatar
2 votes
0 answers
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 ...
Tom's user avatar
  • 133
2 votes
1 answer
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]$. ...
Blanco's user avatar
  • 623
1 vote
1 answer
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 ...
roydiptajit's user avatar
1 vote
1 answer
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 ...
Gabi G's user avatar
  • 325
0 votes
1 answer
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 ...
Codevalley's user avatar
1 vote
1 answer
148 views

Connection between Pseudo random generators and hardness

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
roydiptajit's user avatar
0 votes
1 answer
61 views

Existence of Pseudorandom Generator

How to show that for $\epsilon>0$, there exists a function $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. ...
roydiptajit's user avatar
0 votes
1 answer
294 views

If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?

Just like the title states. If I have a pseudo-random generator $g\colon \Sigma^n \rightarrow \Sigma^{2n}$ and a one-way function $f$, is $g'(x)=f(g(x))$ a pseudo-random generator? And why? My ...
Pedro Costa's user avatar
1 vote
1 answer
71 views

What is and amplification factor in pseudo-random generators?

I can't seem to find an answer to this. For instance, I have this question: Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$). My gut tells me this ...
Pedro Costa's user avatar
0 votes
0 answers
41 views

Asking for your help with LFSR, linear automaton

I am a software developer new to the site. I am currently learning about LFSR (linear feedback shift register). Every day I solve a question which is given to me, but today I am lost. I can not solve ...
endoftheworld's user avatar
1 vote
1 answer
27 views

Printing values of psuedo random numbers in a range

I wanted to write a program to print the values of pseudo random numbers in a range. So, i wrote the following: ...
Ruthvik's user avatar
  • 11
2 votes
3 answers
1k views

How likely is for a pseudorandom number generator to generate a long sequence of similar numbers?

How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? "Similar numbers" could be same numbers, or numbers from a given range. For example, if we consider ...
Maciej Łoziński's user avatar
2 votes
1 answer
61 views

Set which is easy to sample, but difficult to sample from its complement

Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
Ron Y's user avatar
  • 23
3 votes
0 answers
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 ...
Mark Pedley's user avatar
4 votes
1 answer
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 ...
Vincent's user avatar
  • 723
3 votes
2 answers
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 ...
stackzebra's user avatar
1 vote
1 answer
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 ...
maciek's user avatar
  • 125
4 votes
2 answers
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 ...
chendoy's user avatar
  • 307
2 votes
2 answers
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, ...
Anthony's user avatar
  • 21
3 votes
1 answer
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?
FunkyBaby's user avatar
  • 133
0 votes
1 answer
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 ...
Varun Negandhi's user avatar
4 votes
2 answers
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$ ...
Root's user avatar
  • 313
1 vote
0 answers
114 views

Pseudo random generator that is non injective

I was reading answer to https://crypto.stackexchange.com/questions/24941/prove-there-is-prg-that-is-not-necessarily-one-to-one Here assuming existence of G: from n bit to l(n) bits non injective G' ...
Root's user avatar
  • 313