Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1713237

Re: random.c: LFSR polynomials are not irreducible/primitive

Show all headers | View raw

Hi,

Sorry to answer this late, but i was pretty busy, and i assume Olivier
Vivolo is on vacation.

For a polynomial, being primitive implies being irreducible, and the
polynomial which must be primitive is Q(x), as you described it
earlier, on GF(2^32).
When the polynomials will be primitive,the TGFSR (LFSR on 32 bit word)
will have his maximal period.
If i remember well, we gived inthe paper, the magma code, and the
patch for random.c.
We did several tests for the propsal, and we chose those polynomials
because they avoid a lot of changes on the source code, and they
preserve the quality of the statistic distribution.


Regards,
David.


2017-08-16 14:51 GMT+02:00 Stephan Mueller <smueller@chronox.de>:
> Am Dienstag, 15. August 2017, 17:12:24 CEST schrieb Theodore Ts'o:
>
> Hi Theodore,
>
>>
>> Stephan, if you have any comments on the proposal made by David
>> Fontaine and Olivier Vivolo, I'd appreciate hearing them!
>
> I think I have some news: The magma code I used for GF(2^32) testing was not
> correct.
>
> The corrected magma code is attached (thanks to Dr. Peter Birkner, BSI, who
> helped me here).
>
> That magma code shows:
>
> - the current polynomials for Q(X) = α**3 (P(X) − 1) + 1 are irreducible but
> not primitive over GF(2^32)
>
> - the polynomials suggested in https://eprint.iacr.org/2017/726.pdf Q(X) =
> α**4 (P(X) − 1) + 1 are both, irreducible and primitive over GF(2^32)
>
> The use of GF(2^32) is important, because we apply the LFSR to a 32 bit word.
> Hence, we have 2^32 permutations the LFSR should evenly cover.
>
>
> Bottom line, I would recommend that random.c is patched to take the
> polynomials suggested in https://eprint.iacr.org/2017/726.pdf.
>
>
> If it is of any help, the attached magma code could be preserved somewhere
> useful (in random.c?)
>
> Ciao
> Stephan

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

random.c: LFSR polynomials are not irreducible/primitive Stephan Mueller <smueller@chronox.de> - 2017-08-14 10:30 +0200
  Re: random.c: LFSR polynomials are not irreducible/primitive Theodore Ts'o <tytso@mit.edu> - 2017-08-15 00:30 +0200
    Re: random.c: LFSR polynomials are not irreducible/primitive Stephan Mueller <smueller@chronox.de> - 2017-08-15 10:50 +0200
      Re: random.c: LFSR polynomials are not irreducible/primitive Theodore Ts'o <tytso@mit.edu> - 2017-08-15 17:20 +0200
        Re: random.c: LFSR polynomials are not irreducible/primitive Stephan Mueller <smueller@chronox.de> - 2017-08-16 15:00 +0200
          Re: random.c: LFSR polynomials are not irreducible/primitive Fontaine david <fontained35@gmail.com> - 2017-08-16 21:10 +0200
        Re: random.c: LFSR polynomials are not irreducible/primitive Stephan Mueller <smueller@chronox.de> - 2017-08-17 08:10 +0200

csiph-web