Am Dienstag, 15. August 2017, 17:12:24 CEST schrieb Theodore Ts'o: Hi Theodore, Jeffrey, > > Stephan, if you have any comments on the proposal made by David > Fontaine and Olivier Vivolo, I'd appreciate hearing them! (from Jefferey): > This may be helpful, too. I use it to look up minimal weight > irreducibles when I need them. > http://www.hpl.hp.com/techreports/98/HPL-98-135.pdf Thanks for the list of polynomials. There is even another list that I used for my LRNG: http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf. The problem with all of these polynomials is that their taps are very close together and are mostly in the high parts. As there is a chance that adjacent event values that shall be processed with the LFSR have some form of correlation, having taps close together is not good, especially when they are in the high parts of the polynomial. To counter that effect, either polynomials with spaced-out taps are good (as sought by Ted). There is another solution that I found which was confirmed by mathematicians to be of no effect regarding the polynomial behavior: instead of updating adjacent words in the entropy pool, update words that are more spaced apart. The key is that the spacing must ensure that still all words are evenly updated. Updating more spaced-apart words will effectively counter potential correlations in adjacent input data when these adjacent values are XORed due to polynomials with close taps. In my LRNG I use the value 67 (a prime number), since I have taps that are close together in the high parts. The value 67 is somewhat in the middle of the smallest pool size (having 128 words) and thus should have the largest spacing possible for the smallest pool. The spacing does not need to be a prime number, it is sufficient that this value is odd to ensure that all words are evenly accessed by the spacing. Translating that consideration into the code found in random.c, the following line is affected: i = (i - 1) & wordmask; This line could be changed to something like: i = (i - 13) & wordmask; Why 13? Well, it is a prime number (I like primes :-) ) and it is somewhat in the middle of the smallest pool size of 32 words. Though, as we have polynomials that are spread out more evenly, we do not need that change. Yet, if the impact on having such large polynomials (and thus doing that many XORs for each byte in the event value) is considered to great speed-wise, we could use much smaller polynomials, even when their taps are not spaced apart. Ciao Stephan
