Tausworthe Generators

Tausworthe Generator (TG) [17] is a kind of multiplicative recursive generator (see Section 3.1) which produces random bits. It has the following form:

$$x_{n+1} = (A_1x_n + A_2x_{n-1} + \ldots + A_kx_{n-k+1}) \mbox{ mod } 2$$

where $x_i, A_i \in \{0,1\}$ for all $i$.

The theory behind TG is related to irreducible primitive polynomials over GF(2). A polynomial over Galois field of order 2 (GF(2)) is a polynomial whose coefficients are either 0 and 1. Such a polynomial is irreducible primitive if it does not have nontrivial factors like 1 and has order of $2^n-1$ for some $n$. The order of a polynomial $f(x)$ over GF(2) is the smallest integer $e$ for which $f(x)$ divides $x^e+1$. For example $x^2+x+1$ is irreducible primitive with order $3 = 2^2-1$, while $x^2+1 = (x+1)^2$ is not even irreducible.

When the characteristic polynomial of the above form $P(z) = z^k-A_1z^{k-1}- \ldots -A_k$ is an irreducible primitive and the $k$ initial seeds are not all zero, the corresponding TG will have a period of $2^k-1$. To obtain random numbers instead of bits, we can output the decimal values of every $k$-consecutive bits.

Since TG only produces bits, it is too slow to be useful. A technique to speed up is to use a special form called trinomial-based TG. A trinomial is a polynomial with only three coefficients being nonzero, so a trinomial-based TG has only two of the $A_i$ coefficients of the characteristic polynomial being nonzero. This results in a very fast, hardware-based implementation technique called Feedback Shift Register (FSR) which involves shift, AND, and XOR operations on a small set of $k$-bit registers. However, TGs based on this special form are known to have statistical defects, so in practice the outputs of two or more trinomial-based TGs are combined using bitwise XOR operations to provide the final output. As with LCGs, arbitrarily chosen parameters will yield poor TGs, and not all combinations of any three good TGs necessarily create a better TG, therefore, in this project we implemented a 3-combined TG based on parameters from [11] with period $2^{88}$

The main attraction of TGs lies in its independence of word size of target hardware and some of the variants have strong cryptographic safety (see Section 3.5)