Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pseudo-random-generators]

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

0
votes
0answers
17 views

arithmetic coding for generating random number with desired distribution

Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding ...
0
votes
0answers
18 views

What is a minimal, pseudo-random hash function?

I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient. I'm not at all concerned about security. The output should be evenly distributed and appear ...
0
votes
1answer
52 views

Can the pseudo-random-sequence generator be described as a finite state automaton?

I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot ...
1
vote
1answer
34 views

PRNG for a gaussian distribution?

I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data. I know that PRNG produce ...
2
votes
1answer
45 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. ...
1
vote
0answers
29 views

Is it possible to build a secure PRG from two functions one of them being a PRG?

Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG. Being $\alpha$ a constant, is it possible ...
1
vote
2answers
126 views

How to determine seed collision probability in a PRNG?

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...
0
votes
0answers
43 views

What is known about the equidistribution properties of Philox pseudo random number generator?

I want to evaluate the usefulness of Philox pseudo random number generator for drawing multidimensional random vectors. What is known about the equidistribution properties of Philox? I read the ...
1
vote
0answers
16 views

Pseudo-random regex-searchable function

Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties: $f$ is efficiently ...
1
vote
1answer
44 views

Generate numeric or string ID for a sequence of elements

How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter. Example: [41,1001,32] should generate the ...
2
votes
2answers
53 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 ...
1
vote
1answer
45 views

Can pseudo random number generator generate all possible sequences?

Suppose I have a random number generator G that takes in a seed s from the set of integers. Suppose we have a sequence of numbers Q where |Q| = k. Does there exist a seed s such that G(s) produces the ...
2
votes
1answer
24 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 ...
-1
votes
2answers
56 views

How do these alternative definitions of one-way functions compare?

I've seen competing requirements in the definitions for one-way functions. Namely $$ \underset{x,r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big) = o(n^{-c}) $$ and $$ \underset{x}{\mathbb{E}}\left[\...
3
votes
1answer
62 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 ...
-2
votes
5answers
147 views

Algorithm to generate non-repeating random numbers of O(1) memory?

Is it possible to create $O(1)$ memory consuming algorithm, which is generating non-repeating pseudo random numbers? I can remember numbers in the hash set and it will be $O(1)$ time, but the set ...
1
vote
1answer
25 views

Which definition of PRFs is correct?

Assume the $\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|}$. Let $F_{n}$ be a ...
2
votes
1answer
46 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 ...
0
votes
1answer
36 views

Looping through random integers - will it halt with probability 1?

Say I have a simple program that has the pseudocode like this: ...
1
vote
1answer
1k views

Monte Carlo: what is a seed?

I have reached a chapter in the notes I am following where a program written in C++ is using a Monte Carlo method to estimate $\pi$. It mentions a 'seed', but does not say what this is. I have tried ...
1
vote
1answer
200 views

Is $x^2+x+1 (mod 2)$ a one-way function?

Given that $x^2+x+1 (mod 2) = 1$ and $x^2+x (mod 2) = 0$ for ${|x\rangle}_{x=0,1} \xrightarrow{F} \frac{1}{\sqrt{2}}[(-1)^{x}|x \rangle + |1-x \rangle]$ (Fourier transform). So, the 1-1 correspondence ...
1
vote
2answers
158 views

Pseudo random, unqiue integer numbers in a given range

I need an algorithm that gives me integer numbers with the following features: Numbers must be in a given range $[n..m]$; Numbers must be returned in pseudo-random order (random at visual inspection ...
7
votes
2answers
167 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 ...
1
vote
1answer
40 views

Generating numbers to be averaged efficiently

During my research, I had encountered the following issue. Consider the equation $$\sum_{k=1}^K\alpha_k P_k = P$$ where $\sum_{k=1}^K\alpha_k=1$, $\alpha_k > 0$, $P_k > 0, P>0$. So you are ...
1
vote
2answers
80 views

Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?

I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here: ...
0
votes
0answers
19 views

Generating symmetric keys

Let's assume that we have to generate huge number of 256-bit symmetric keys. How to do it and how to be sure that it is safe. Perhaps it requires a strong mathematical backend. Don't hesitate to ...
0
votes
0answers
474 views

Non repeating pseudo random number generator for a dynamic range

Algorithms like Knuth's algorithm or this one, works for a range that is known in advance(like shuffling numbers 1 to 11), in this case the range will never change. You'll always get a random no. ...
1
vote
0answers
29 views

Generation of 11 bit random number

I need camera to sign one random line(there are something like 2000 lines) from the frame each second. At the beginning I have some 64 bits seed with high entropy from physical RNG and a secure ...
3
votes
1answer
141 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 ...
6
votes
1answer
252 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 ...
4
votes
0answers
55 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 ∈ ...
2
votes
1answer
54 views

Fitting a feedback loop to data points

If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation. However, thinking in more ...
5
votes
1answer
173 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 ...
1
vote
2answers
614 views

Given a random number generator rand5() generate gen7()

Given a pseudo random number generator rand5() that generates a random integer in the set [0,1,2,3,4], how would someone use this to generate a function rand7() that outputs [0,1,2,3,4,5,6] with equal ...
3
votes
2answers
189 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 ...
4
votes
2answers
120 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 ...
7
votes
1answer
260 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 ...
0
votes
1answer
54 views

What is the period of N xored identical random number generators, with differing seeds?

This question is a kinda spin off from Why do we not combine random number generators? If for example we had N identical type random number generators, with N different seeds, what would the period ...
3
votes
0answers
75 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 ...
11
votes
3answers
910 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 < ...
5
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 ...
6
votes
0answers
601 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. ...
1
vote
1answer
82 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 ...
1
vote
1answer
28 views

Hardness amplification of PRFs by increasing key length

I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF ...
4
votes
1answer
40 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 ...
61
votes
6answers
7k 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 ...
2
votes
0answers
32 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
13 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. ...
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 ...
1
vote
1answer
101 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 ...