# Tagged Questions

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

33 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 ...
6k 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 ...
24 views

### Feedback polynomial of 7-bit Linear Feedback Shift Register [duplicate]

My friend gave me a question to solve. The question he asked me was: the foll. Sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I ...
7 views

### Feedback polynomial of 7-bit Linear Feedback Shift Register [duplicate]

My friend gave me a sequence that has been generated by a 7-bit linear feedback shift register. ...
288 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 ...
38 views

### How broken is LCG in the case of partial output?

Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can ...
80 views

### Generate integer from 0 to 1 with equal probability

I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0_4()) which generates random number from 0 to 4. I am wondering if I can approach this way: ...
33 views

### Probability with an unusual pseudo-random generator

I will preface this with the actual question taken from lecture: An unusual pseudo-random generator outputs integers between 1 and 4, inclusive, in such a way that each value, v, occurs with a ...
39 views

### Random sampling of tuples

When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may ...
44 views

### Could PRNGs make use of more internal state?

In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing): Pseudo-random number generators (PRNGs) must have a period since they ...
20 views

### Is there a way to incrementally degrade the quality of a PRNG?

I have an application that depends on a random number generator to perform. The application might be sensitive to the quality of the random numbers, but I don't know for sure. I'd like to test this, ...
427 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 ...
77 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?
37 views

### how to prove the periodity of an LFSR

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 ...
64 views

599 views

### Seeding the Mersenne Twister Random Number Generator

I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I ...
146 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. ...
117 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 ...
37 views

### Mersenne twister middle word

In some literature, as well as in Wikipedia, the middle term parameter m of Mersenne twister is called "number of parallel sequences". Why? What is meant here by "parallel sequences"?
105 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 ∈ {...