# Generating a sequence of $n$-bit random-like numbers that will never repeat.

I am actually aiming for n $\approx 100$ but obviously I could interleave the bits of two never-repeating $50$-bit sequences etc.

I need to be able to generate the $n^{th}$ number quickly enough to seem instantaneous to a human. After that, finding the $(n+1)^{th}$ should be trivial.

Given a large number of the already generated numbers I need it to be difficult to reproduce the algorithm I am using.

-

## 1 Answer

You can't generate a list of $n$ bit numbers that never repeats because there are only $2^n$ of them. It must repeat within that time.

Probably the easiest way to generate them is to use some very simple random number generator like a linear congruential one, and hash the result.

Added: A Linear Feedback Shift Register seems to do what you want. You could build one in software of length $100$ bits. It will avoid all collisions. It looks like predicting the output from a number of successive outputs is quite easy, but you could run it through your favorite encryption algorithm. The Advanced Encryption Standard has a version that outputs 128 bits. If that is too many, you could find a pair of 49/50 bit primes and do RSA encryption

-
I plan to stop well before the last number, probably around 1/2 way through, certainly well before my algorithm becomes obvious. - What do you mean by and hash the result? – OldCurmudgeon May 5 '13 at 22:00
@OldCurmudgeon: to take the output of your random number generator (which will be easy to guess if you give somebody lots of values) and run it through a cryptographic hash function You could also run it through your favorite encryption algorithm. – Ross Millikan May 5 '13 at 22:02
I am limited to 100 bits of output so hashing would almost certainly introduce duplicates would it not? – OldCurmudgeon May 5 '13 at 22:07
@OldCurmudgeon If you have a cycle of $2^{100}$ and you stop half way through, you'll have gone through $2^{99}$ numbers. If you can do one billion ($1000000000$) every second, that will take a little over twenty trillion years :-) – Alfonso Fernandez May 5 '13 at 22:07
@OldCurmudgeon: You would expect a collision at about $2^{100/2}=2^{50}\approx 10^{15}$ outputs. You could use a Linear Feedback Shift Register to make sure of no duplicates, but I don't know how easy they are to crack. – Ross Millikan May 5 '13 at 22:08