I calculated the linear complexity of some Mersenne Twister PRNG using two
implementations of the Berlekamp-Massey algorithm.
The sequence to test is generated by taking only the bits in one position
(not the whole 32-bit number). In C, for example, we can do:
bit= (PRNG() >> 16) & 1
to take the bit 16.
I obtained a strange linear complexity for SFMT19937:
http://www.math.sci.hiro****ma-u.ac.jp/~m-mat/MT/SFMT/
(I checked the correctness of the implementation).
While for MT19937 and WELL19937c I get L=19937 (as expected), for
SFMT19937
I get values from 79860 and 79872 (which is good, but strange).
In the paper
http://www.math.sci.hiro****ma-u.ac.jp/~m-mat/MT/SFMT/M062821.pdf
I saw nothing about that.
Please, could someone explain?
Thanks
Cristiano