1

I have a counter with a known maximum (called max). max can be big (actually it will be either 36^40 - 1 or 62^40 - 1).

I want a bijection b from [0..max] to [0..max] with the following property: b(n+1) not easily guessable from b(n).

I am NOT searching for a cryptographically secure function, I just want as much entropy as possible to obfuscate a little the output of a counter.

The function must be doable in PHP. This allows all the functions PHP does.

PengOne
  • 48,188
  • 17
  • 130
  • 149
Frizlab
  • 846
  • 9
  • 30
  • What ideas do you have for how to do this? At what point did you get stuck? – PengOne Jan 18 '12 at 16:20
  • Why do you need b^2 = 1? That sounds like a very strong restriction. – Kerrek SB Jan 18 '12 at 16:20
  • You'll probably have to use the GMP library in PHP if you want to deal with numbers that large. Just an FYI. – Mr. Llama Jan 18 '12 at 16:21
  • Sorry, my bad. I do not _need_ `b(b(n)) = n`. I **do** want a bijection though. – Frizlab Jan 18 '12 at 16:25
  • @PengOne: I do not know what bijection I could use to get the entropy I'm searching for. – Frizlab Jan 18 '12 at 16:31
  • @Frizlab Possibly because you have no described clearly what you are searching for. Define "easily guessable" more clearly, and the question might become answerable. – PengOne Jan 18 '12 at 16:39
  • @PengOne: I do not truly care that anyone find the function. Also, one would not actually have the ability to call b(N) with N fixed, either, which is required for the method proposed in the link you give. Finally, are polynomial functions bijections? – Frizlab Jan 18 '12 at 16:39
  • @Frizlab Not all polynomials are bijections. Any linear polynomial taken modulo `max` gives you a bijection. However, if you don't care about anyone finding the function, then why not make `b(n) = n`. That's certainly a bijection. – PengOne Jan 18 '12 at 16:44
  • Since this is a counter, how easily must *you* compute n from b(n)? i.e. is this is a database id that you only compare for equality vs something you need to reverse? How simple should it be to compute b(n+1) from b(n) if you know the secret sauce? Can a psuedorandom number generator suffice (one way, easy to compute next) if it has a cycle time equal to your range? – ccoakley Jan 18 '12 at 16:48
  • @ccoakley: I do not need to know `n` from `b(n)`. The solution you would propose (a pseudorandom generator with a cycle time equal to my range) would do it I suppose. – Frizlab Jan 18 '12 at 16:51
  • I just realized that your known max is not a clean power of 2. That makes your implementation with a random number generator much less fun. Also, I posted/deleted a very incorrect answer (many, many repeated counts). You should look for a shuffle algorithm that can be lazily computed (look for haskell questions on shuffle algorithms, haskell programmers love that stuff). – ccoakley Jan 18 '12 at 17:10

1 Answers1

3

I do not think this question is answerable in it's current form. The criterion

b(n+1) is not easily guessable from b(n)

is not well-defined. You have given no metric or quantifiable constraint. Since you go on to write that you are "NOT searching for a cryptographically secure function" and mention in the comments that you "do not truly care that anyone find the function", it is unclear why you need the bijection at all.

However, here are some ideas that may help you either find a bijection you're happy with or clarify your question so others can help.

Any linear polynomial invertible modulo max will work. That is, a polynomial of the form 

b(n) = a*n + b mod max

gives a bijection if and only if 

gcd(a,max) = 1

The easiest case is a=1 and b=0, so that b(n) = n, which seems to satisfy your vague constraints.

If you want to get fancy with it, you could change a and b often, say be generating a random number (but be sure to check that gcd(a,max) = 1 or you will not get a bijection).

PengOne
  • 48,188
  • 17
  • 130
  • 149
  • Thank you, you gave me what I was searching for. Out of curiosity, is there a way to have a polynomial with a different degree which would be guaranteed to be a bijection? What would be the constraints on the other degrees? – Frizlab Jan 18 '12 at 17:08
  • 2
    @Frizlab For higher degrees, whether the function is invertible depends on the number theoretic properties of max. It's an interesting question, but the answer will take you farther into number theory and away from your application. – PengOne Jan 18 '12 at 17:37
  • The simplest way to be sure that `gcd(a,max) = 1` might be to always pick a prime number for `a`. – caf Feb 07 '12 at 05:58