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
60
votes
6answers
8k views

Why do we not combine random number generators?

There are many applications where a pseudo random number generator is used. So people implement one that they think is great only to find later that it's flawed. Something like this happened with ...
39
votes
3answers
14k views

Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
38
votes
7answers
4k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
31
votes
2answers
2k views

Simulating a probability of 1 of 2^N with less than N random bits

Say I need to simulate the following discrete distribution: $$ P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} $$ The most ...
24
votes
3answers
3k views

Are all pseudo-random number generators ultimately periodic?

Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end? By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence... ...
13
votes
1answer
2k views

Choosing taps for Linear Feedback Shift Register

I am confused about how taps are chosen for Linear Feedback Shift Registers. I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, ...
13
votes
1answer
305 views

Proving the security of Nisan-Wigderson pseudo-random number generator

Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as ...
12
votes
3answers
1k views

PRNG for generating numbers with n set bits exactly

I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
9
votes
4answers
901 views

What is a good algorithm for generating random DFAs?

I am generating random DFAs to test a DFA reduction algorithm on them. The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)...
8
votes
2answers
231 views

What makes a pseudorandom generator, a high quality one?

Reading this answer to this SO question: Why do we not combine random number generators?, it talks about very high-quality PRNG (Pseudo Random Number Generator) so it makes me wonder what ...
7
votes
1answer
264 views

Recover PRNG description from consecutive outputs

Given the outputs of the pseudorandom numbers generator how can one determine the type (e.g. Linear Feedback Shift Register), Multiply-With-Carry, Linear Congruential Generator etc.) and recover the ...
7
votes
1answer
489 views

What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed?

Whilst reading up on Xorshift I came across the following (emphases added): The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush: ...
6
votes
1answer
134 views

Find missing value in period of LCG

It's well known that linear congruential generators have a full period only if a few properties are fulfilled. Now I need a LCG that does not generate a full period in 2^32 (easy to find, just ...
6
votes
1answer
323 views

Generating uniform random connected graphs: doubt about Wilson's algorithm

I want to generate a random connected simple labeled graph with $n$ vertices and $m$ edges, selected uniformly over all connected graphs with such $n$ and $m$. I found this approach. It says: build a ...
6
votes
1answer
3k views

Period of a pseudo-random sequence generated using an LFSR

I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated ...
5
votes
3answers
98 views

One way recurrence O(N)->O(1)

Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence). I'm trying to find a system where it's fast to find many steps in the future ...
5
votes
1answer
279 views

What's relation between Kolmogorov complexity and pseudorandomness?

In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the ...
5
votes
2answers
792 views

Introductory Book on Pseudo-Random Number Generation

I'm a rank amateur in the area of pseudo-random number generation. I've recently found out that certain generators are better than others (e.g. mt19337 vs rand in C++) and learned what modulo bias is. ...
5
votes
2answers
184 views

Random generator considerations in the design of randomized algorithms

It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. ...
5
votes
1answer
66 views

Distribution of Ones in a Psuedorandom Sequence

Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table ...
5
votes
0answers
136 views

Will the Mersenne Twister PRNG eventually produce all integer sequences of a certain length?

I'm attempting to use the MT19937 variant of the Mersenne Twister PRNG to accomplish something. Whether or not this something is feasible depends upon the answers to these two questions: What is the ...
4
votes
2answers
132 views

Recover NLFSR description from given output

Given Fibonacci's Nonlinear Feedback Shift Register output, how can I recover the description (nonlinear feedback function and current seed)? The clean output of consecutive and unmodified is large ...
4
votes
1answer
41 views

Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

Let f and g be two functions with integer range 0..m-1. They may keep state and interact ...
4
votes
1answer
219 views

Hardcore Bit proof for discrete log

I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that $B(x)=(x<p/2)$ is a hardcore bit for ...
4
votes
1answer
166 views

Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
4
votes
1answer
93 views

Bias of first values produced by a family of RNGs

Suppose I'm doing a large number of pseudo-random but deterministic experiments, where each experiment requires generating several random numbers. I'm approaching this by having each experiment use a ...
4
votes
1answer
454 views

LFSR sequence computation

I need to calculate the output of the sequence generated by this shift register but I cannot find anywhere how to do it. Everywhere the results are just given but there is no explanation how to do ...
4
votes
1answer
40 views

Logarithmic guarantees for randomized search trees

In this paper [1], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being ...
3
votes
2answers
47 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$ ...
3
votes
1answer
38 views

How good (or bad) is my makeshift PRNG?

Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I ...
3
votes
1answer
255 views

Perfect random number generation using normal numbers

This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the ...
3
votes
2answers
73 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 ...
3
votes
1answer
185 views

PRNG bad seeding and von Neumann unbiasing

Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is ...
3
votes
1answer
65 views

How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

I'm considering the following definition of one-way functions: Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is ...
3
votes
0answers
60 views

creating new PRF from existing one

I have encountered a problem in class, tried solving it and faced a problem, I will include my ideas, and the problems i faced. Assume F is a PRF, 1.denote $P_k(x) = F_k(x) ⊕ F_k(1^n)$ for any $n ∈ ...
3
votes
0answers
103 views

Origin of Mersenne Twister tempering parameter 'd'?

Short version: common MT (and MT64) implementations have a tempering parameter 'd' (a bit mask). The papers I've looked at describing MT don't include it. Where is it from? When was it added? Long ...
3
votes
0answers
809 views

NFA random generator

I'm working on a NFA to DFA conversion tool that is different from the Subset Construction and I need to test this tool. In order to be sure that the immplementation has no bug I'd like to generate a ...
2
votes
3answers
1k views

Feedback polynomial of 7-bit Linear Feedback Shift Register

My friend gave me a question to solve. The question he asked me was: the following sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I ...
2
votes
2answers
168 views

Rigorous proof against pseudorandom generator

I am trying to teach myself the principles of cryptograhpy, and want to solve the following question: Let G be the algorithm that takes an input x = (x1, . . . , xn) from {0, 1} n (so each xi ∈ {...
2
votes
2answers
56 views

Why does the distribution of pseudorandom numbers change when operating like this?

We were introduced to the standard C rand() function, and how to use it. At some point during the class we were asked how to roll a die. The simple answer was to ...
2
votes
1answer
81 views

What does it mean to fool a function?

In computer science papers, I see about the term 'fooling' a function. What does it mean to fool a function against a particular complexity class? Why is it important?
2
votes
2answers
47 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 ...
2
votes
2answers
290 views

How can I prove that a cryptography algorithm is a pseudo-random number generator?

I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not? Is there some principles I have ...
2
votes
2answers
95 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, ...
2
votes
1answer
86 views

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring ...
2
votes
1answer
63 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 ...
2
votes
1answer
170 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?
2
votes
1answer
50 views

Why do many developers continue to rely on pseudo-random number generators?

Although hardware based “true” random number generators are available, software-based pseudo-random number generators still remain the predominant method for generating random numbers in use today. ...
2
votes
1answer
29 views

Pseudo-number generation compared to Blum-Micali

A few years ago I made a pseudo-random number generator to use in a monte carlo simulation for a lecture in my University. My instructor ask me why I did that generator instead of using C equivalent ...
2
votes
1answer
48 views

A question about the definition of PRFs

Let $\mathcal{F} = \{ f_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$. We define a family of ...