1

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.

OldCurmudgeon
  • 585

1 Answers1

2

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

Ross Millikan
  • 374,822
  • 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 05 '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 05 '13 at 22:02
  • I am limited to 100 bits of output so hashing would almost certainly introduce duplicates would it not? – OldCurmudgeon May 05 '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 05 '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 05 '13 at 22:08
  • @AlfonsoFernandez - that is exactly what I am looking for. I may end up with thousands of generators each starting at their own spot but none must ever produce the same number that one of the others has or will. – OldCurmudgeon May 05 '13 at 22:10
  • @RossMillikan - There must never be any collisions, and with this wide a field I am not going to be able to record all previous numbers to detect a duplicate. Thus my need for a non-repeating algorithm. – OldCurmudgeon May 05 '13 at 22:12
  • @RossMillikan - If you could post a separate answer for the LFSR idea I will up-vote. I could choose a number of different ones and interleave the bits. There is more discussion required however because I need to be able to generate the nth number in the sequence. – OldCurmudgeon May 05 '13 at 22:17
  • @OldCurmudgeon: Then I would just find my favorite encryption algorithm. The Advanced Encryption Standard has a version that outputs $128$ bits. Is that too many more than $100$? – Ross Millikan May 05 '13 at 22:17
  • @RossMillikan - I would happily discard 28 bits so long as the result never repeats. – OldCurmudgeon May 05 '13 at 22:18
  • @OldCurmudgeon: But you can't guarantee the result will not repeat. See my edit, suggesting you can use RSA to get output the size you want. – Ross Millikan May 05 '13 at 22:28