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
