[lkml]   [2017]   [Aug]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: random.c: LFSR polynomials are not irreducible/primitive
On Mon, Aug 14, 2017 at 10:20:18AM +0200, Stephan Mueller wrote:
> Hi Ted,
> drivers/char/random.c contains the following comment:
> """
> * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
> * Videau in their paper, "The Linux Pseudorandom Number Generator
> * Revisited" (see: In their
> * paper, they point out that we are not using a true Twisted GFSR,
> * since Matsumoto & Kurita used a trinomial feedback polynomial (that
> * is, with only three taps, instead of the six that we are using).
> * As a result, the resulting polynomial is neither primitive nor
> * irreducible, and hence does not have a maximal period over
> * GF(2**32). They suggest a slight change to the generator
> * polynomial which improves the resulting TGFSR polynomial to be
> * irreducible, which we have made here.
> """
> This comment leads me to belief that the current polynomial is primitive (and
> irreducible).
> Strangely, this is not the case as seen with the following code that can be
> used with the mathematical tool called magma. There is a free online version
> of magma available to recheck it:
> Note, the polynomials used up till 3.12 were primitive and irreducible.
> Could you please help me understanding why the current polynomials are better
> than the old ones?

Have you looked at section 3.1.1 of the above cited paper?

- Ted

 \ /
  Last update: 2017-08-15 00:21    [W:0.061 / U:3.516 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site