Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
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
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.