Questions about algorithms that deterministically generate sequences of numbers that have stochastic properties of random sequences.
3
votes
2answers
44 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. ...
3
votes
0answers
69 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
28 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"?
1
vote
2answers
58 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
65 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 ...
8
votes
1answer
127 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, ...
9
votes
1answer
171 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 ...
