Processing math: 100%
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 2 years ago

Max Alekseyev gravatar image

First, you define polynomial over GF(592) 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 59213=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)
    print(f'{n}:\t{c}')