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

learn more… | top users | synonyms

2
votes
0answers
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 ...
0
votes
0answers
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. ...
1
vote
3answers
246 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 ...
1
vote
1answer
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 ...
1
vote
1answer
44 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: ...
1
vote
1answer
27 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 ...
1
vote
2answers
37 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 ...
3
votes
2answers
40 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 ...
0
votes
1answer
17 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, ...
15
votes
2answers
335 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 ...
2
votes
1answer
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?
2
votes
1answer
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 ...
1
vote
1answer
64 views

Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials

I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials. In particular, ...
2
votes
0answers
22 views

What are the recent research directions in the topic of circuit lower bounds from derandomization?

I am thinking of the classical paper, https://www.cs.sfu.ca/~kabanets/Research/poly.html Can someome link to some papers/reviews that give a sampling of what are the recent thoughts in this ...
5
votes
3answers
59 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 ...
4
votes
1answer
74 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
51 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 ...
6
votes
1answer
209 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 ...
2
votes
1answer
59 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 ...
5
votes
1answer
52 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 ...
3
votes
1answer
46 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 ...
2
votes
1answer
209 views

Linear congruential generator with uniform distribution [closed]

I am currently studying linear congruential generators, and there was an example in which I didn't get the code: ...
5
votes
1answer
75 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 ...
2
votes
1answer
205 views

A binomial random number generating algorithm that works when $Np$ is very small

I need to generate binomial random numbers: A binomial random number is the number of heads in $N$ tosses of a coin with probability $p$ of a heads on any single toss. If you generate $N$ uniform ...
20
votes
2answers
2k 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... ...
5
votes
1answer
205 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: ...
2
votes
1answer
111 views

Are there pseudorandom number generators (PRNG) with no finite period?

The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period? For this question it is not ...
-2
votes
1answer
71 views

proof of convergence in arbitrary precision PRNGs

consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow). ...
0
votes
0answers
245 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 ...
6
votes
4answers
404 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, ...
1
vote
1answer
533 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 ...
5
votes
2answers
145 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
0answers
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 ...
2
votes
0answers
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"?
2
votes
2answers
101 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 ∈ ...
4
votes
1answer
153 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 ...
11
votes
1answer
495 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, ...
12
votes
1answer
248 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 ...