# Questions tagged [pseudo-random-generators]

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

93 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
12k 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 ...
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 ...
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... ...
2k views

829 views

86 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 ...
754 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 ...
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 ...
163 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 ∈ {...
55 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 ...
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?
233 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 ...
36 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, ...
245 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 ...
84 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 ...
116 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?
46 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. ...
26 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 ...
47 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 ...
149 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 ...
everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's ...