LaFarr's 80-bit pseudo Random Number Generator Description

Last Up date: 2015 October 19 Changed multiply symbol to * instead of x
2014 September 4 Added note about 65537 also being prime.
Recent changes: Now it allows a decimal integer parameter up to 65,535
This Page started on: 2012 March 17 16:47:15

Most random number generators generate a sequence of integers by the following recurrence: R(n+1) = p1 * R(n) + p2 (mod N) R(0) is the seed.

The parameters p1, p2, and N determine the characteristics of the random number generator, and the choice of R(0) (the seed ) determines the particular sequence of random numbers that is generated. If the generator is run with the same values of the parameters, and seed, it will re-generate the sequence. In that sense the numbers generated certainly are not random. They are therefore sometimes referred to as pseudo random numbers.

Above, explained in a University of Utah Math department web page

If p1, p2, and N are relatively prime (no common divisors>1) every value of N will be generated, before it repeats.

257 is prime, and simply using a one byte higher address multiplies by 256 and an add makes it 257!
65537 is prime, and using a 2 byte higher address and add would also work, and be as fast.
It might be a little more secure?

I have an encoding program using no multiply where: p1=257 p2=1 N=2^80

It is written in Assembly Language and is a 376 byte .COM file. It allows a numeric parameter from 1 to 65,535. Effectively there are that many different versions. For better or worse, it has to be run under DOS, or at the command prompt on a 32-bit Windows system. On a Mac it might work under something called DOSbox; but I haven't verified it.

To help debug the Pseudo Random Number generator, here is a description with some computed values. I needed correct values to verify the logic as I stepped through the execution.

My encoding program generates a new random value for each byte of data.

It uses the high order byte of each 80-bit pseudo random number and Exclusive OR's it with each byte of data. Because XORing with the same value twice brings back the original: The same program does the decoding. It can encode and decode any type of file, including: images, programs, and compressed files, as well as simple text.

2^80 is over 1.2 * 10^24 which is so large all the computers in the world could not determine the seed or break it. It is hard to appreciate the size of 2^80 until one calculates the number of micro seconds in a year, which is: about 1.8 * 10^14 .

Unfortunately, this type Pseudo Random Generator is criticized in the Wiki articles I found. They are looking at the entire number; but the low order bits of all this type Generator are anything but uniformly distributed. The low order byte of the one described here simply counts!

Often, people using languages like BASIC and C, who want a small Random number use the low order bits. It is easy to just use the Remainder to get a "random" number in a limited range. This is very bad for applications like: shuffling a deck or cards, slot machines, KENO or Bingo. Only the high order bits should be used for every application I know of; but few High Level Language programmers do that, because these languages don't use the high order bits of a good random number generator.

I have a short description of other Random Number Generators I know of here.

E-mail me or Click the phone block to call or get link to my BIO page.

Go to: My Home Page My phone #'s Go to: This page TOP