dg@lakart.UUCP (David Goodenough) (05/04/88)
I post this here because having looked at sci.crypt, I see a lot of
references to "random" number generators in the context of their
usage as one time pads.
Long time ago I saw an article that explained how to generate "random"
numbers by shifting a pattern of bits, looking at two of the bits,
exclusive-or'ing the two bits, and using the result as the new bit
at the bottom:
bits := seed and 10010000
seed := seed + seed
if (bits = 10000000 or bits = 00010000)
seed := seed + 1
Now my problem is as follows: Ignoring the "demon" state (all zeros)
for a given bit pattern length, it may be possible to generate a
maximal sequence (i.e. 2**n - 1). Whether this happens depends on
the two bits you look at.
Does anyone have a list of the bit pairs for various pattern lengths that
will generate maximal lists. To do it by exhaustive search is feasible
up to about 24 bits, but after that it starts getting rediculous. (I only
have a 68020 here, and not a CRAY :-)
Alternatively, if anyone else knows a different method for generating
"random" numbers, preferably 32/48/64 bit I'd like to hear it. I'd try the
seed = seed * const + other_const
technique, except that I have been lead to believe that the bottom bits
of this have a tendancy to exhibit a cyclic pattern.
Thanks in advance,
--
dg@lakart.UUCP - David Goodenough +---+
| +-+-+
....... !harvard!adelie!cfisun!lakart!dg +-+-+ |
+---+agn@unh.cs.cmu.edu (Andreas Nowatzyk) (05/05/88)
The shift & xor - way of generating not-very-random numbers requires more that 2 taps for certain numbers of bits in order to get the max. period lengh (=2^n - 1). A table of polynomials that require only 2 terms can be found in Knuth's "The Art of Computer Programming", Vol.2. There is no 2-term solution for either 16, 32, 48 or 64 bit. (3, 17), (7, 31), (5, 47), (1, 63) are some nearby generators. -- -- Andreas Nowatzyk (DC5ZV) Carnegie-Mellon University Arpa-net: agn@unh.cs.cmu.edu Computer Science Department Usenet: ...!seismo!unh.cs.cmu.edu!agn