3

Is there any good invertible 1-1 function that maps an integer to another integer? for eg, given the range 0-5, I want to find one that maps:

0->3
1->2
2->4
3->5
4->1
5->0

Also, the mapping should look random.

Eric J.
  • 147,927
  • 63
  • 340
  • 553
boh
  • 1,477
  • 2
  • 16
  • 35

4 Answers4

4

You can fill an array in ascending order and shuffle it. This will usually perform reasonably well, if not being the most efficient memorywise.

You can also rely on a closed discrete transformation, such as multiplication. If you have 2 numbers, P and K, then (I think) as long as P and K are coprime, P^n mod K will produce a nonrepeating, pseudorandom sequence of values of length (K - 1), ranging from 1 to K. This particular manifestation of discrete math is one of the premises of cryptography. Going backwards from sequence to exponent is known as the discrete logarithm problem and is the reason traditional RSA is secure.

You asked for a reversible algorithm. If you keep track of the exponent, you can go from P^n mod K to P^(n-1) mod K without much difficulty. You can take a few shortcuts to go backwards from power to exponent that don't work in cryptography because certain parameters of the algorithm are intentionally discarded to make it harder.

That said, if you happen to break RSA by solving the discrete log problem while you're working on this, be sure to let me know.

Wug
  • 12,956
  • 4
  • 34
  • 54
  • 1
    You can only get a sequence of length `K - 1` by `P^n` if `K` is prime. In general the limit is `φ(K)`, and that's reached if and only if `P` is a primitive root modulo `K` (of which there are `φ(K-1)`). – Daniel Fischer Jul 18 '12 at 04:49
  • The maths behind this suggestion are fairly arcane, I won't pretend to understand all of them completely. – Wug Jul 18 '12 at 04:59
  • thanx, let me try the mod one tonight :) – boh Jul 18 '12 at 05:43
0

How about permutation polynomials? See section 3 in this article: http://webstaff.itn.liu.se/~stegu/jgt2012/article.pdf It is used for noise there, but it looks exactly like what you want.

It suggest to construct functions of the form (Ax^2 + Bx) mod M. Only a small subset of those functions are invertible/produce permutations, but it shouldn't be hard to find the actual inverse if it exists.

ltjax
  • 15,837
  • 3
  • 39
  • 62
0

Something similar to this was discussed in Non-repetitive random seek in a range Algorithm. I was intrigued enough to put some ideas down at http://www.mcdowella.demon.co.uk/PermutationFromHash.html

Community
  • 1
  • 1
mcdowella
  • 19,301
  • 2
  • 19
  • 25
0

You can generate such a permutation using a block cipher, without having to hold the entire thing in memory (as you would if you were to shuffle the list). I wrote a blog post about it some time ago, which you can find here.

Nick Johnson
  • 100,655
  • 16
  • 128
  • 198