Berlekamp's algorithm

From: "narutocanada@xxxxxxxxx" <narutocanada@xxxxxxxxx>
Date: Mon, 16 Jul 2007 07:21:45 -0700

hi

I'm trying to implement Berlekamp's algorithm.
I've followed a few resources on the web.
I ran into exceptions with this claim:
"The number of the null space basis should equal to the number of
irreducible polynomials."
I found that the only reliable cases for this claim are polynomial
like x^q-x, with q=prime^power.
I've found quite a few exceptions, and here are one of them:

Irreduc( (2)+(2*x)+(2*x^2)+(2*x^3)+(2*x^4)+(2*x^5)+(x^6) ) mod 3;
# true
But the null space basis has dimension 3:
[[1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1], [1, -1, 1, 0, 1, 1]]

I don't know if it's my algorithm that's wrong or my misunderstanding
the theorem. Thanks for any insight.

.

Prev by Date: Re: Using affine schemes to prove two rings are equal
Next by Date: Re: looking for a set (three)
Previous by thread: simple group of order 720
Next by thread: Sir Isaac Newton, has originated, inter-conversion of mass and energy, (E=mc2 )
Index(es):
- Date
- Thread

Relevant Pages

MACIS 2007 - CALL FOR PARTICIPATION
... Sciences (MACIS) is a new series of conferences where foundational research on theoretical and practical problems of mathematics for computing and information processing may be presented and discussed. ... Computing Roots of Polynomials using Bivariate Quadratic Clipping ... An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection ...
(comp.specification.z)
Re: decomposition of polynomials
... but Googling "polynomial decomposition" will reveal ... problems for multivariate polynomials and for rational and algebraic ... O) algorithm for the decomposition of irreducible polynomials ... Technical Report TR87-826, Comput. ...
(sci.math)
Re: euclidean algorithm over Q[i]
... Are you using the Euclidean algorithm to compute ... GCD's of univariate polynomials over Q? ... I'm not sure what 'pseudo division' may mean, ... Let b be the leading coefficient of G ...
(sci.math.symbolic)
Re: Kroneckers method for polynomial factorization
... The algorithm as given is not really a good version. ... I hope this shows what you left out (factoring the integers). ... The polynomial interpolation step cannot always ... polynomials requiring rational coefficients cannot, however, be ...
(sci.math.symbolic)
Re: euclidean algorithm over Q[i]
... Z, the Gaussian integers, may be what you remember seeing. ... written a pretty simplistic algorithm in java that carries out polynomial ... GCD, just using polynomial long division and the euclidean algorithm. ... GCD's of univariate polynomials over Q? ...
(sci.math.symbolic)