These are very good info, thanks!
On Friday, 21 October 2016 11:49:42 UTC+1, Fredrik Johansson wrote: > > On Thursday, October 20, 2016 at 9:52:26 PM UTC+2, CrocoDuck O'Ducks wrote: >> >> Hi there cool people! >> >> I have implemented a simple MLS generator using linear feedback shift >> registers. I used as taps the ones provided in: >> >> Vanderkooy, J. (1994). Aspects of MLS Measuring Systems. Journal of the >>> Audio Engineering Society, 42 (4), 219-231. >>> >> >> However, now that the theory is a little bit clearer to me, I would like >> to make it more general. The feedback taps are supplied by the coefficients >> of the primitive factors of the polynomial x^N + 1, where N is the length >> of the sequence (related to the number of registers). I would like to know >> from you guys if you think there is some Julia package I can use to >> calculate primitive factors of polynomials. As mentioned in the title, I >> need to perform this in modulo-2. Here >> <http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm> >> >> there are more info and the Berlekamp algorithm is mentioned. Has that >> algorithm already been implemented somewhere (couldn't really quite find >> out at the moment)? If not, do you know any good source that could assist >> me in the implementation? >> > > You can factor polynomials with Nemo: > > julia> using Nemo > > julia> R = ResidueRing(ZZ, 2) > Residue ring of Integer Ring modulo 2 > > julia> S, x = PolynomialRing(R, "x") > (Univariate Polynomial Ring in x over Residue ring of Integer Ring modulo > 2,x) > > julia> factor(x^23+1) > Dict{Nemo.nmod_poly,Int64} with 3 entries: > x+1 => 1 > x^11+x^9+x^7+x^6+x^5+x+1 => 1 > x^11+x^10+x^6+x^5+x^4+x^2+1 => 1 > > julia> length(factor(x^12345+1)) > 15 > > Regarding implementation, the book Modern Computer Algebra by von zur > Gathen and Gerhard has a chapter on factoring polynomials over finite > fields, which might be helpful. Knuth also covers this topic. > > From memory, for Berlekamp's algorithm you need functions to compute the > modular product and GCD of polynomials, and a function to find the > nullspace of a matrix. Once you have those, Berlekamp's algorithm is > simple: you construct the matrix whose rows are the coefficients of a > sequence of polynomial powers modulo f, minus the identity matrix, then > compute the nullspace. Next, you pick a random linear combination of > nullspace basis vectors. There is a GCD test that tells you if the random > vector is a factor (or if the factorisation is complete). Continue picking > random vectors until done. > > The Cantor-Zassenhaus algorithm is an alternative to Berlekamp, but it is > slightly more complicated to code. If you need to factor polynomials of > very high degree, both algorithms can be sped up asymptotically using > various tricks. > > Nemo calls FLINT for polynomial factorisation, in which some of those > tricks are implemented. It should be fast enough for most purposes, but > it's not really optimised for GF(2). Victor Shoup's C++ library NTL has a > faster implementation. I'm not aware of a Julia wrapper for NTL, but it > should be possible to call it with Cxx. > > Fredrik >
