Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

First, you define polynomial over $GF(59^2)$ but then reduce its coefficients modulo 59. It will be simpler to consider the polynomial over $GF(59)$ upfront. Next, the claim "up to cycle, or g^59" is incorrect. The cycle length in this case equals $\frac{59^2-1}3=1160 > 59$.

The coefficients you look for form the first column of the powers of the companion matrix of polynomial $g$. They can be computed as follows:

R.<x> = GF(59)[]
g = x^2 + 2*x + 13
M = companion_matrix(g)
for n in (1..10):
    c = (M^n).column(0)