python - Characteristic polynomial of binary matrix over the field F2 or GF(2)

Question

How can the characteristic polynomial of a binary matrix (one with only zeros and ones) be found programmatically, where the process operates in the finite field F₂ (also known as GF(2)) and the coefficients are zeros and ones?

Here's what I have tried:

1. SymPy's charpoly() method doesn't give the answer I want, since it doesn't operate on the field F₂ and gives a polynomial with coefficients well beyond 0 and 1. However, is it possible to adapt the output of charpoly() to return the characteristic polynomial over F₂, or to have the charpoly() method operate on that field?
2. This repository is about the most convenient thing I could find that could solve this question. As of this writing I am trying it out now. However, it is very slow (is on track to take many hours) for the sizes of matrices I am interested in (128x128 to 256x256). Moreover, I had to modify the source code to fit my needs since the code, as is, doesn't take arbitrary matrices.

I am asking this question because finding the characteristic polynomial in F₂ is part of the process of calculating the appropriate jump parameter for certain random number generators (see my note on this).

标签： pythonmatrixsympy

Answer 1

事实证明，返回的特征多项式的系数charpoly()可以适应 GF(2) 有限域，而且很容易做到：奇数系数变为 1，偶数系数变为 0。这对我的目的来说已经足够了。因此，我的问题解决了。