Random number generation

Thread View: sci.crypt

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by David Goodenough Wed, 04 May 1988 15:35

#4214

Author: David Goodenough
Date: Wed, 04 May 1988 15:35

38 lines
1760 bytes

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	+-+-+ |
						  	  +---+

Re: Random number generation

#4217

Author: Andreas Nowatzyk
Date: Thu, 05 May 1988 08:42

13 lines
974 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads