Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1327

Re: Pseudorandom Permutation Algorithm for Arbitrary Size?

Cross-posted to 3 groups.

Show all headers | View raw

On Thu, 16 Feb 2012 04:47:25 -0800 (PST), Andrew Tomazos
<andrew@tomazos.com> wrote:

>Given a positive integer N, I would like a function f(N,i) where i is
>in [0,N) such that:
>
>    f(N,0) = x0
>    f(N,1) = x1
>    f(N,2) = x2
>    .
>    .
>    f(N,N-1) = x[N-1]
>
>where (x0, x1, x2, ..., x[N-1]) is a pseudo-random permutation of (0, 1,
>2, .., N-1).
>
>For example the output for N = 5 may be:
>
>   f(5,0) = 3
>   f(5,1) = 0
>   f(5,2) = 2
>   f(5,3) = 4
>   f(5,4) = 1
>
>Here (3,0,2,4,1) is a "pseudo-random" shuffle of (0,1,2,3,4)
>
>What is a closed form or algorithm for f?
>
>- N may be very large, so allocating an identity permutation array and
>randomly shuffling it is out. Ideally calculating f(N,i) for some N
>and i should take constant size and space.
>
>- If this is not possible than perhaps an easing constraint can be
>added that a stateful solution that guarantees f(N,i) will be called
>in ascending order of i values (ie f(N,0), f(N,1), f(N,2) and so on)
>would be useful to.
>
>- f doesn't need to be "cryptographic strength", just sufficiently
>random for statistical purposes.)
>
>- I note that maybe mutliplying by and moding by prime numbers (or
>pure powers of primes) is somehow a useful tool as P^n where P is
>prime forms a valid finite field. ?
>
>Thanks,
>Andrew.
You need an encryption function.  Given a key, every allowed bit
patttern is reversibly mapped to another bit pattern.  The
reversibility ensures that all output bit patterns are the result of
one, and only one, input bit pattern.

For 8, 16 and 32 bit numbers, I would suggest that you build yourself
a simple 4-round Feistel cypher
(http://en.wikipedia.org/wiki/Feistel_cipher).  It won't be
cryptographically secure, but it will probably be random enough for
your purpose.  For 64 bit numbers, use DES.  For 128 bit numbers use
AES.

For other number ranges, use Hasty Pudding cypher,
(http://en.wikipedia.org/wiki/Hasty_Pudding_Cipher), which is defined
for all possible number ranges.

rossum

Back to comp.programming | Previous | Next — Previous in thread | Find similar

Thread

Pseudorandom Permutation Algorithm for Arbitrary Size? Andrew Tomazos <andrew@tomazos.com> - 2012-02-16 04:47 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? Patricia Shanahan <pats@acm.org> - 2012-02-16 06:22 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? James Dow Allen <jdallen2000@yahoo.com> - 2012-02-16 06:57 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? root <NoEMail@home.org> - 2012-02-16 15:10 +0000
    Re: Pseudorandom Permutation Algorithm for Arbitrary Size? Patricia Shanahan <pats@acm.org> - 2012-02-16 08:39 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? rossum <rossum48@coldmail.com> - 2012-02-16 15:24 +0000

csiph-web