Conference rusure::math

I think there's a way based on Mersenne primes; I'd have to check
a textbook I have on spread spectrum communications which lists
some very long shift register sequences, some with a single tap.

- Jim

Also, I assume you're aware that maximal length linear recurring
sequences are always based on prime polynomials over GF(n), n=2
in your case...

Also, it would be easy to cascade two relatively prime sequences
to generate a longer sequence.  This is how its normally done
(say, for space probe applications), since the individual, shorter
sequences can be thoroughly tested.  The longer sequences that
are known can never be exhaustivly tested in the life of the universe...

One idea I thought of once but never analyzed, was to have two
sequence generaters, say A and B, along with a third generator, C,
which could be relatively short.  Clock a bit out of C.  If it's a
1 then clock a bit out of A and use it, else clock a bit out of B.
A, B, and C could all be relatively prime... this might be much
better than simply XORing two relatively prime sequences in terms
of immunity to decoding (its known that simple max length sequences
can be detected using a relatively short piece of them so they're
not good for really secure communications).

- Jim

Perhaps I don't understand.  Shift registers yield notoriously bad random
number sequences for a wide range of applications.

If he's unconcered with how random the sequences appear, but simply wants
a long cycle, why not use the sequence X(i) = A*i+B mod 2^n, where A is some
even number?  If he *is* concerned with how random the sequences appear, why
is he using shift registers?

Linear congruential methods (and their variants) are typically *much* better
sources of psuedo-random numbers.  Also, *no* random number generator should
be put into production without extensive testing.  If this is security-related,
you should be able to apply a trap-door function to a sequence of psuedo-random
numbers to get an even better sequence of random numbers.  If either the
psuedo-random number sequence or the trap-door function can depend on some
'key' that can be specified when the sequence begins (for example, XOR the
key into the number before computing the trap-door function), you'll decrease
the likelyhood that someone else can duplicate part of your sequence.

[Edited from a MAIL message received from Richard (MARIAH::) Lary.

Yeah, but I only have half the answer.

What the guy wants to do is find a polynomial with coefficients in G(2) of
order N+1 (highest coefficient=X**N) such that:

1)	it is irreducible
2)	it does not divide X**K - 1, where 1<=K<=2**N

The term I've seen for these polynomials is "primitive polynomials". The half
of the answer I don't have is a good source for a list of primitive
polynomials of large order, although I believe the book "Error Correcting
Codes" by Pedersen(?) and Weldon has such a list.

I will get around to putting something in MATH.NOT eventually...

Once you find such a polynomial, the pseudo-random generator is:

	TEMP = TEMP * 2
	IF TEMP >= 2**N THEN TEMP = TEMP .XOR. POLYNOMIAL

where POLYNOMIAL is the polynomial you found.

The previous reply is correct... Peterson does have an extensive
list of primitive polynomials.  You could basiclly find then with
a sort of sieve procedure.  From what I understand, very long sequences
are normally build from two or more relatively prime sequences
to make testing feasable and to allow coarse/fine synchronization.

The literature in this area is really extensive.   The routine below is
a concrete example of one I've used for coin flipping in the past (BLISS16).

- Jim

ROUTINE PRBS(SEED) : JSR1 =

!++
! Generate the next bit of a maximal length pseudo random bit stream based
! on the prime polynomial X^16 + X^12 + X^3 + X + 1 over GF(2).
!
! Input:
!	SEED -> A 16 bit nonzero seed register
!
! Output:
!	Shift register is updated
!	Routine returns TRUE or FALSE based on next bit in stream
!--
BEGIN

BIND
    SHIFT_REGISTER = .SEED;

LOCAL
    BIT_0;

BIT_0 = .SHIFT_REGISTER AND 1;
SHIFT_REGISTER = .SHIFT_REGISTER ^ -1;
IF .BIT_0 THEN SHIFT_REGISTER = .SHIFT_REGISTER XOR %O'150010';
RETURN(.BIT_0);

END;

END
ELUDOM

Oops.  I've checked Volume 2 of "The Art of Computer Programming".
Shift registers yield a good source of random bits, but not a good
source of random fractions.  The index contains three items under
"Shift register recurrence".  One discusses it as a technique for
generating random bit-sequences, one discusses deternining the
period length, and the third is on factoring polynomials mod p.

I also have a paper that shows how to find a *random* primitive
polynomial of degree n, given any particular primitive polynomial
of degree n.

Random number generators based on feedback registers are often called Tausworth
generators.  One article on them is "Quasi-Random Number Sequences from a Long-
Period TLP Generator", by Bright and Enison (ACM Computing Surveys, V11#4 -
Decmeber 1979).

As Peter mentioned, such generators are good sources of random BITS, but not of
random NUMBERS - if you try and use the whole register as the "next random num-
ber", you get a poor generator.

Note that the generator with the longest period may not be the generator with
the best statistical properties.

Also, good random number generators do NOT necessarily make good bases for
encryption.  Linear congruential random number generators, if carefully chosen,
have about the excellent statistics, but it is straightforward to determine
all the parameters of the generator from a few (3 or 4) successive outputs.
(Knuth has an article on this somewhere.)

If you have no faith in any particular random number generator, you can use
a scheme due to MacLaren and Marsaglia:  Use one generator to scramble the
output of another.  That is:  Set aside a table of, say, 100 entries.  Fill
the table with values given by generator A.  To generate a number, use generator
B to pick a "random" spot in the table.  Return the value there, re-filling the
slot with the next value from generator A.  The result can be shown to be at
least as strong as the stronger of A and B.  (Actually, I'm not sure where I saw
that claim.  The original paper, which I've never read, is in JACM 12:1, pg 83
(Uniform Random Number Generators).  One would certainly need some assumptions -
if A returns a truelly random number on every other trial, and 0 on the remain-
ing trials, and B shows a bias toward even numbers, you could get 0 more often
than you should.)
							-- Jerry

Question: Is there any DEC device, based on A/D that generates a REALLY (not
pseudo) random sequence? If so - is the sequence reproducible?

Sure - tap onto the Ethernet and note the interarrival times for all messages.
Random? Yes. Uniformly distributed? No. Reproducible? If it's truly random
how can it possibly be? The two concepts are contradictory. - Lynn

One technnique for generating random numbers (discussed in the S{}Y notesfile)
is to set a timer request, then bump a counter in a tight loop.  When the
timer 'goes off', the low order bit of the counter is polled.  This continues
until sufficient bits have been collected.

This seems to be pretty random.  On a VAX-11/780, using the smallest
expressible delta time, the counter got bumped about 240 times, with
what appeared to be a reasonable distribution.  Some people think this
technique produces pretty random numbers (and have tested the numbers),
while some think it doesn't (without justification).   In fairness, I
didn't do any sophisticated analysis of the generated bits in my small
experiment, and there were other processes on the machine (but the test
was run at priority 24).
    
BTW - It is possible for a truly random sequence to be reproducible;
consider consulting (and re-consulting) the same numbers in the RAND
Corporations well-known table of a million random digits.
             
					- Gilbert