Will a Random Number Generator Eventually Repeat Its Numbers?

[kuahji]

I am just curious. If I have a random number generator, eventually, if I wait long enough all possible numbers should began to repeat. Or would the numbers not repeat? For example, if say the first hundred numbers were totally random 455688132547... etc. would the machine eventually repeat the numbers? If so, how would I go about calculating an approximation of when they'd repeat?
Anyway, hope that all made sense.

 

[robert Ihnot]

Sure the numbers will repeat, but the question is just how many digits are you talking about? Now at dice numbers run from 2 to 12, 7 is the most frequent number. It is not uncommon, not that uncommon for 7 to repeat 3 or even 4 times in a row. Sure, not like everytime, but you keep playing and YOU WILL SEE SUCH REPEATS!

To make a rough estimate, I guess a throw of dice may take only 15 seconds. So that would give 4 throws in a minute. The 7 comes up 1/6 of the time, and four of them every 1296 throws. So that amounts to 5.4 hours of actual play! Now, of course, at the table there is time spent changing dealers, so slower period exists, and probably faster ones too. Of course, your play could be over days or weeks, but certainly if what we are talking about is an average of 5.4 hours of actual play, you don't have to play that game for very long before it may happen!

The trouble with these repeating 7s is they are the bane of the wrong better, who bets against the house. On the pass line, when you first start, the right player will automatically win if a 7 is thrown. (Rather than lose as is usual with a 7.) If the wrong better can get his number, (4,5,6, 8,9,10) he is likely to win because the shooter will probably throw a 7 before hitting the wrong better's number again. Since wrong betters have this advantage once they have their number, they may begin by betting heavy, because otherwise they will have to give odds if they want to add to their bet since with their number the game is now in their favor.) The true bane of being a wrong better is that a series of 7s might occur before he can get his number, then instead of rejoicing over immediate wins, he has immediate losses. (If this happens three times in a row, he may be cured of betting wrong.)

The matter in general is discussed by the mathemtician and philosopher Nassin Nicholas, writer of "Fooled by Randomness." He asks what happens, "When the black swan alights"? (While some have compared them to unicorns, it's not true, black swans do exist.) http://www.fooledbyrandomness.com/ I quote: NNT is the Dean’s Professor in the Sciences of Uncertainty at the University of Massachusetts at Amherst. He is also an essayist, belletrist, literary-philosophical-mathematical flâneur, and practitioner of uncertainty (“mathematical trader”) focusing on the attributes of unexpected events, with a focus on extreme deviations, the “Black Swans” (i.e. outliers), their unpredictability, and our general inability to forecast.

Again, what is involved in the problem of kuahji is the range, R, of the numbers involved. Take Pick 3 there are 1000 numbers involved, 000 to 999. So that a reapeat of a GIVEN NUMBER would be 1/million, but normally what is being sought is the repeat of ANY NUMBER, and that is just 1/1000 or the range of the numbers in question. So if we suppose that Pick 3 is played twice a day for 6 days a week, we should expect that after about 83 weeks we would see the same number come up twice in two successive drawings. If one has the time or inclination, he could check this out!

 

[MeJennifer]

Sure the numbers will repeat, but the question is just how many digits are you talking about?

Sure?
Well in principle one could make a random number generator that does not repeat.

 

[mathman]

Random number generators, as normally thought of, are programs on digital computers, where numbers have a finite number of bits. Therefore there are only a finite number of possibilities for numbers out of the generator. As a result, the generator must eventually repeat numbers it had turned out previously.

 

[MeJennifer]

Random number generators, as normally thought of, are programs on digital computers, where numbers have a finite number of bits. Therefore there are only a finite number of possibilities for numbers out of the generator. As a result, the generator must eventually repeat numbers it had turned out previously.

Then I suppose I do not think normally

Furthermore a true random number generator, assuming such a device would exist, that would never give any duplicate numbers would most certainly not be a true random generator.

 

[selfAdjoint]

Then I suppose I do not think normally

Furthermore a true random number generator, assuming such a device would exist, that would never give any duplicate numbers would most certainly not be a true random generator.

Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.

 

[MeJennifer]

Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.

Well not quite.
For instance it is not true that if a random generator is not periodic it must be true random.
Being periodic is just one of the criteria that disqualifies a generator as random.

 

[Intuitive]

I am an advanced Programmer in Vbscript and in order to have what's called a true random number generator you'd have to deal with infinity.

You can not deal with infinty on a system that requires a time limit therefore you can not have a true random number generator but you can give it very large odds.

I can build you a true random number generator but it would never stop functioning and freeze your system.

 

[chroot]

You cannot implement a true random number generator entirely on a digital computer. The best you can do is a "pseudo-random number generator," which, as has been said, will eventually repeat. This is because computer programs are deterministic, and can do no better than shuffling bits in a complex (yet not random) way.

There are, however, many sources of true randomness available in the physical world. The voltage across a temperature-sensing diode in the processor, the time between successive user keystrokes, the receipt of random broadcast packets on a network interface, etc. are all random enough, at least in aggregate, for most cryptographic purposes. A random-number generator based on such sources of true randomness will never repeat.

- Warren

 

[BoTemp]

A random-number generator based on such sources of true randomness will never repeat.

- Warren

It depends on what you mean by "repeat". Any random number generator must pick over a finite set, so let's say you want to generate random integers from 1-100. A pseudorandom number generator would repeat it's sequence infinitely many times. A truly random number generator could never be guaranteed to repeat, but it must. Any sequence it generated once would be generated again later, but only given infinite time. Given finite time, the probability of repeating a sequence of length n starting from a given point would be (1/100)^n, same as it was for being generated the first time.

 

[chroot]

Any sequence it generated once would be generated again later, but only given infinite time.

Who cares? Why don't we keep the discussion to things that are physically realistic?

- Warren

 

[MeJennifer]

Who cares? Why don't we keep the discussion to things that are physically realistic?

Hmmm, this is the Mathematics / Number theory section right?

 

[chroot]

Hmmm, this is the Mathematics / Number theory section right?

Random number generators, including those implemented on computers, are rather physical things. The qualities being discussed -- repitition, for example -- depend on the actual physical nature of their implementation.

- Warren

 

[matt grime]

Hmmm, this is the Mathematics / Number theory section right?

You want to do it mathematically? Define random then. What is the sample set, and what is the probability distribution on that sample set, i.e. what are the measurable subsets, the sigma algebra, whatever you choose to call it.

Integer values? That doesn't have a uniform distribution. The interval [0,1] with the uniform measure? Then you're into all kinds of issues as to what it means to actually sample a single element from a continuous distribution. Remember, such things are purely mathematical constructs, and only model of what we find in the real world.

 

[MeJennifer]

You want to do it mathematically? Define random then. What is the sample set, and what is the probability distribution on that sample set.

Hmmm, well the digits of PI and e are quite random aren't they.

 

[matt grime]

That isn't a good enough definition. There are many interpretations of that sentence.

What is true is that pi is believed to be normal (no proof exists) and that means something very specific, so its *digits* are believed to be 'random' in the sense of 'normal' (see e.g. wolfram for an explanation). If you wanted to generate a 3 digit string at random then sure picking some 3 digit string from pi would create a random (conjecturally) 3 digit string, but it is not producing a random number (how many digits in the string should you pick? And that doesn't even then begin to address what it means to pick a string at random).

 

[Crosstalk]

With random number generators, a quickly built one will often generate a series like 174891029174891029174891029174891029, where it repeats forever. Often, though, it is a long time before a repitition occurs. A good random number generator is designed to not have repitition as obvious as that, in fact a very good random number generator has no repitition that goes on forever. So, yes, if you took the output of some random number generators, they would repeat forever, and for some they wouldn't ever start repeating forever.

 

[0rthodontist]

Any pseudo-random number generator that is written on a computer with a finite amount of memory must output a sequence that a repeating tail. This is because the computer only has a finite number of states it can take, so it must repeat some state eventually, and once it does that it gets locked into a loop of states which repeatedly outputs the same finite string of numbers.

 

[HallsofIvy]

Hmmm, well the digits of PI and e are quite random aren't they.

Okay, now you need to define "random" and "quite random"! I don't see how that responds to

Define random then. What is the sample set, and what is the probability distribution on that sample set.

 

[-Job-]

Computers can be made to output an arbitrarily large randomish number, since it's not really required that the whole number be kept in memory. For example, an algorithm that outputs the digits of a random number in batches of k random digits only keeps at most k digits in memory. The difficulty is in deciding when to stop outputting the number. After how many digits will the computer stop? It should be a random number of digits. To be a perfect random generator the probability of stopping at the nth digit should be the same as that of stopping at the (n+1)th digit, approximately 0, which is not really feasible.
Unless perhaps we start the computer and let it naturally come to a stop (i.e. due to destruction, insufficient resources, etc). If the universe is truly random, then the system will be a true random number generator.

 

[0rthodontist]

It is necessary to have at least as many states in the computer as the length of the repeating tail of the sequence. I am using the following kind of model:
1. Computer outputs a number based deterministically on its state, of which there are a finite number
2. Computer moves to a new state, which is based deterministically on its previous state. Goto 1
With finite memory eventually the path of states, and therefore the string of numbers that are output, will fall into a cycle. If the computer's states at any time become xaya, where a is a single state and x and y are strings of states, then they must repeat xayayaya... and the output numbers will also repeat since there can be only one number per state.

 

[Crosstalk]

Actually, about the fact that once it passes a state twice it will get locked in a cycle, that is false. If you think about any irrational number, and figure out a way to calculate the next digit quickly, where it doesn't slow down based on number of numbers already computed, it will never give a repeating sequence. That would be an easy way to make a random number generator. In that case it would not repeat. It may hit a similar state where it puts out the same number, but it would be possible to make a random number generator that never gets locked in a cycle.
I thought up a quick random number generator that would never get locked in a cycle. You would start with the first digit of tan(1), rounded, and the second number would be the rounded second digit of tan(1), making a list of random values like:
round(tan(1))
round(tan(1)*10)-round(tan(1))
round(tan(1)*100)-round(tan(1)*10)-round(tan(1))
and so on...
This would never get locked in a repeating state, since tan(1) is irrational. I am also trying to make one that runs fast and doesn't repeat.
Also, to stress the point that a random number generator that doesn't repeat doesn't have to slow down with each digit, you could make one that takes the square root of 2.1428304820483 using a algorithm that doesn't slow down during each digit. If you research, there are a lot of methods to take a square root that don't slow down with each digit, and some don't need knowledge of the rest of the digits already calculated, just the last few.
The only problem with ones that don't repeat is they probably run slowly.

 

[CRGreathouse]

Actually, about the fact that once it passes a state twice it will get locked in a cycle, that is false. If you think about any irrational number, and figure out a way to calculate the next digit quickly, where it doesn't slow down based on number of numbers already computed, it will never give a repeating sequence.

To calculate an arbitrary number of digits would take an unbounded amount of memory. Of course it may be possible to calculate with a finite amount of internal memory plus the Turing machine tape output, but that's still an unbounded number of internal states (tape + memory).

 

[moving finger]

Excellent point, but the failure of pseudo-random generators would be to repeat whole cycles of previously generated numbers, since they're just periodic with very long periods.

I don't see that a pseudo-random number generator need necessarily be periodic in principle - that depends on the seed and the algorithm for each random number generated.

Any pseudo-random number generator that is written on a computer with a finite amount of memory must output a sequence that a repeating tail. This is because the computer only has a finite number of states it can take, so it must repeat some state eventually, and once it does that it gets locked into a loop of states which repeatedly outputs the same finite string of numbers.

This applies if the computer algorithm is completely digitally self-contained with a finite number of internal states and takes no outputs from the external world. Add an interface to the computer so that it can utilise information from the outside world in its random number generation algorithm, and your potential number of states is as large as you like.

Best Regards

 

[0rthodontist]

This applies if the computer algorithm is completely digitally self-contained with a finite number of internal states and takes no outputs from the external world. Add an interface to the computer so that it can utilise information from the outside world in its random number generation algorithm, and your potential number of states is as large as you like.

True--or do something drastic like increase the memory by a gigabyte or two every million years.

 

[moving finger]

True--or do something drastic like increase the memory by a gigabyte or two every million years.

or make part of the computer analogue instead of digital? could this create a potentially infinite number of internal states?

 

[chroot]

If you want true randomness, you need to sample an analog source. Commonly, the noise in a diode is used as a source of randomness in commercially available true-random number generators. You could also use other phenomena, like the decay events of a small radioactive sample.

You cannot, even in principle, achieve true randomness from any algorithmic process with finite states.

- Warren

 

[0rthodontist]

You cannot, even in principle, achieve true randomness from any algorithmic process with finite states.

Sure you could--you could, for example, prepare an algorithm by sampling an analog source, transforming the data to randomize it, and recording it in a large database. Then your algorithm might be just to read off the database.

 

[moving finger]

If you want true randomness, you need to sample an analog source. Commonly, the noise in a diode is used as a source of randomness in commercially available true-random number generators. You could also use other phenomena, like the decay events of a small radioactive sample.

You cannot, even in principle, achieve true randomness from any algorithmic process with finite states.

- Warren

How do we know that an analogue source has (in practice) an infinite number of internal states? If space and time are quantised at the Planck scale, then it is possible that even analogue sources have finite numbers of states.

Best Regards

 

[chroot]

Sure you could--you could, for example, prepare an algorithm by sampling an analog source, transforming the data to randomize it, and recording it in a large database. Then your algorithm might be just to read off the database.

...Except your "algorithm" still has finite states, and thus eventually repeats. Unless of course you've pioneered infinite-capacity hard drives?

- Warren

 

[chroot]

How do we know that an analogue source has (in practice) an infinite number of internal states? If space and time are quantised at the Planck scale, then it is possible that even analogue sources have finite numbers of states.

Best Regards

Even if analog sources really do have a finite number of states at the Planck level, there would be so many states (the Planck scale is extremely small) that the system would not necessarily repeat for many, many times the age of the universe.

There's currently no way to "prove" that analog randomness is truly random -- although it is an axiom of quantum mechanics, the most successful scientific theory in existence -- but there are many means to prove that no pseudorandom number generator can ever be truly random.

- Warren

 

[moving finger]

Even if analog sources really do have a finite number of states at the Planck level, there would be so many states (the Planck scale is extremely small) that the system would not necessarily repeat for many, many times the age of the universe.

Agreed - but the important issue here is that it would in fact repeat in principle, thus would only be pseudo-random.

There's currently no way to "prove" that analog randomness is truly random -- although it is an axiom of quantum mechanics, the most successful scientific theory in existence -- but there are many means to prove that no pseudorandom number generator can ever be truly random.

- Warren

Sorry, chroot, but randomness is NOT an axiom in all interpretations of QM.

The Heisenberg Uncertainty Principle says the world is epistemically indeterminable, but this is not the same thing as being ontically indeterminate. The difference explained here :

http://philsci-archive.pitt.edu/archive/00000939/

The wave equation evolves completely deterministically, and in practice we can prepare certain quantum states with determined properties. And I have yet to see a coherent and complete ontological interpretation of the Delayed Choice Quantum Eraser experiment which assumes quantum randomness (paper here http://www.citebase.org/fulltext?format=application%2Fpdf&identifier=oai%3AarXiv.org%3Aquant-ph%2F9903047) .

Depending upon which "interpretation" of QM one assumes to be correct, the world may or may not be fundamentally (ontically) random. The Copenhagen interpretation is silent on the issue (it simply says that what we cannot measure, we have no right to ask about - the shut up and calculate approach), whereas Bohmian mechanics assumes non-local hidden variables.

Best Regards

 

[chroot]

It's pretty damned irrelevant to go into interpretations of quantum mechanics in this thread. The topic is deterministic pseudo-random number generators. As I said, regardless of which interpretation of QM you prefer, there is no such thing as a perfect deterministic PRNG. There need not be any appeals to quantum mechanics to show this is correct.

Neither of us could prove that analog sources of randomness like diode thermal noise are or are not truly random, because we certainly can't wait long enough. It's a moot point.

- Warren

 

[0rthodontist]

Let's say we had a hypothetical truly random source that outputs 1000000 numbers randomly and then stops. There's an unlimited number of programs that output the same 1000000 numbers. The only way to distinguish between the output of "random" objects and "deterministic" objects is in the actually infinite case--which is out of the reach of experiments. For practical purposes there is no hard line between random and nonrandom.

I think that the true issue is practical predictability. With a hard coded self contained algorithm, someone could know the algorithm ahead of time and predict all of the numbers it outputs. Whereas with a physical source it is much harder to predict its output since you can't get total knowledge of its start conditions. It's a practical barrier, not a philosophical one.

However, with some arrangements, it is possible to allow a self contained program to generate numbers that it are in practice impossible to predict even if you know the code for the program. What you need:
1. Some pseudo random system
2. The fastest computer in the world, dedicated to the task
If no other computer is as fast as your random number generator, the generator will produce every number before any other computer can predict it, even with complete knowledge of start conditions.

 

[moving finger]

It's pretty damned irrelevant to go into interpretations of quantum mechanics in this thread.

Well I'm sorry, chroot - but YOU were the one who claimed that randomness is an axiom of quantum mechanics (and what is that if not "an interpretation of QM"?) - I was simply responding to your claim, that's all.

Neither of us could prove that analog sources of randomness like diode thermal noise are or are not truly random, because we certainly can't wait long enough.

I agree completely - but I'm not the one claiming that randomness is an axiom of QM, am I?

Best Regards

 

[Playdo]

A random sequence has no discernable pattern because it has no pattern, each digit (say we are talking about {0, ..., 9}) happens randomly. In that setting there is really no chance at all, as the number of trials goes to infinity, of getting a repeating decimal.

An interesting little experiment is to try generating sequences using recurrence relations like x_{[i+1]}=x_{<i>}^2+c</i>. Apparently there also exist real numbers between zero and one which do not allow any shorter version than to write out all the digits, you can discover they exist but never write them down. Would that be a truly random number?

 

[Alkatran]

I am an advanced Programmer in Vbscript and in order to have what's called a true random number generator you'd have to deal with infinity.

You can not deal with infinty on a system that requires a time limit therefore you can not have a true random number generator but you can give it very large odds.

I can build you a true random number generator but it would never stop functioning and freeze your system.

If I hadn't just looked at the thread with all the joke math articles, this would be the funniest thing I read all night.

 

[Playdo]

I'm trying to think of natural phenomenon that will give you a flat continuous distribution. Dice are not too bad, roulette wheel but those are discrete. What about just using a ten sided die and rolling it repeatedly, that ought to be a random rational number. Each trial is independent and about as random as you can get. You could map the ratio of two parametric chaotic sequences and see if you can't adjust the parameters so you get an equal density on the range. You might investigate a ratio of sequences from this family x_{i+1}=|a log x_{i}|.

 

[Crosstalk]

Going back to the question of whether a random sequence will ever repeat, there are random number generators that do not work with seeds and never repeat. They often use what is called an entropy pool, which is just a big file filled with data that is supposedly random like where you move your mouse. Between when you call these random number generators, the pool is updated. As computers get faster and faster, the time it takes for you to reach a point where it repeats grows smaller and smaller, but at an equal rate the time it takes before the pool gets more data decreases. Therefore, the random number generators never let the program that calls the random number generator call it fast enough it gets a repeat.
Also, some of the algorithms for getting data into an entropy pool are sensitive enough they can sometimes grab results from events caused by quantum physics, which are often truly random. Then, a truly random number is put into a pool used to calculate other random numbers, making those numbers truly random. Truly random numbers never repeat, so the sequence never would either.
One such random number generator is included in the linux kernel. Look it up if you want, for programmers who know where it is the source code is free.
Now, onto pseudorandom number generators that work using a seed. Because a computer has limited memory, they will always repeat.

 

[HallsofIvy]

That is believed to be true but has never been proven.

 

[itsjustme]

OK, if you want a randon integer number in the set {-inf < x < inf} or {0 < x < inf} you would get a number infinete in lenght. And i think QM would be pretty appropriate here. forget decimal, think binary. the only truly random event is nuclear decay (or so we think as observing it makes it change its properties). if you did the schrodinger's cat experiment an infinete amount of times and recorded your results in binary 1 for alive and 0 for dead or vise versa, you would get a truly random number.

 

[NateTG]

Discussing what 'truly random' is, is a topic for philosophers. You might as well be talking about how many angels can dance on the head of a pin.

This argument:

the only truly random event is nuclear decay (or so we think as observing it makes it change its properties). if you did the schrodinger's cat experiment an infinete amount of times and recorded your results in binary 1 for alive and 0 for dead or vise versa, you would get a truly random number

Is obviously circular, and uninformed to boot. Nuclear decay is not 'truly random' there are many examples of it being affected by external factors.

 

[•H3TTING3R]

wow, wouldn't it be possible to make a random number generator, with like som bug or something inside, so when it randomly steps on things, every place it steps on has a digit, and then it keeps adding the last digits it made to the new digits, and then it sometimes multiplies, sometimes divides or subtracts, so it always makes random stuff [if the screen tht the numbers were displayed on was massive, so it could go forever, and just keep making the numbers smaller? o even without a screen, just a data base thingy. but then you'd have to replace the bug. but would tht be classified as random?

 

[matt grime]

Everyone seems to want an infinite amount of time to generate a single random number. Why does that not make them pause for thought for just one second?

 

[itsjustme]

wow, wouldn't it be possible to make a random number generator, with like som bug or something inside, so when it randomly steps on things, every place it steps on has a digit, and then it keeps adding the last digits it made to the new digits, and then it sometimes multiplies, sometimes divides or subtracts, so it always makes random stuff [if the screen tht the numbers were displayed on was massive, so it could go forever, and just keep making the numbers smaller? o even without a screen, just a data base thingy. but then you'd have to replace the bug. but would tht be classified as random?

That would be quite random i imagine, however it would still be predictable and you will not be able to get it in the domain of {0 =< x < inf} as it will only give you a very long number.

Everyone seems to want an infinite amount of time to generate a single random number. Why does that not make them pause for thought for just one second?

lets take a look at probability from the basics. let x= possible outcomes and u= favorable outcomes. The probability of getting u will be:
P=\frac{u}{x}
Now let's bring it into context. Regardless of what number u is as long as it is a countable number:
\stackrel{lim}{x\rightarrow\infty}\frac{u}{x}=0
This means that it would take infinite time to get a truly random number in domain {0 =< x < inf} as the number would be infinite in lenght.

 

[chroot]

itsjustme:

This is the second time in this thread that you've asserted that "truly random" numbers are "infinite in length." That's ridiculous, of course. Zero is a perfectly valid random number, given that it was generated in a "truly random" way.

In fact, most pseudo- and true-random number generators just emit streams of bits -- ones and zeros -- each of which is a random number in its own right, just one in the set {0, 1}.

- Warren

 

[itsjustme]

yes, zero and one and two would be perfectly valid. but what would the probability of geting it be? \frac{1}{\infty}

Try thinking of the biggest number you can think of. then visualise its place in the number line and zoom out, the number line never ends. eventually that number along with every other number before it will be less than what you define to be a division on the number line, the probability of getting it as a result will be practically zero.

 

[matt grime]

Please can someone lock this before it degenerates into anymore nonsense?

1a. There is no discrete uniform distribution on an infinite set.
1b. There isn't a uniform continuous distribution on the real numbers.
2. There is no such thing as a 'number drawn uniformly at random from the real line' in real life (see 1b).
3. Real "random number" generators only choose from a large but finite state space.
4. Ants walking across paper, killing of infinitely many cats, all this is just nonsense.

 

[robert Ihnot]

MeJennifer: Hmmm, well the digits of PI and e are quite random aren't they.

If so, why are these numbers constant?

I am reminded of the Clinton impeachment, "What is the meaning of "is"?"

 

[ramsey2879]

Hmmm, well the digits of PI and e are quite random aren't they.

Because it is common in this thread for statements to be misinterperted and then poked fun of, I will try to explain how I interpret MeJennifer's quote. As the last post I read stated Pi and e are constants. However, I agree the the "distribution" of the digits is such that a presudo random number genetator that gives a result in base 10 having a fixed number of digits, could presumably include the Pi sequence to generate such numbers since I believe (and no one has asserted otherwise) that every possible base ten number less than some fixed number can be found somewhere in the Pi sequence.

Of course no number generater that always generates numbers that are always from some fixed number set {0,1,2,...n} with a relatively smooth distribution within the set is truly a random number generator but in the real world that is most people in fact demand of a "random number" generator.

I interpret MeJennifer's quote in that light, but believe that there are better "random number" generators, such as those where a seed number for a first random number generator is use to generate the seed of a second random number generator.

If one pays attention to the requirement that the distribution within the set of numbers generated by a "random number" generator be uniform then some sort of cyclic number generator such as those based upon raising a number to a given power mod z will best fulfill that requirement.