ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 24 Oct 2022 15:49:07 +0200generating powers of g, an irreducible polynomial in an extension fieldhttps://ask.sagemath.org/question/64555/generating-powers-of-g-an-irreducible-polynomial-in-an-extension-field/In an extension field, how do you to iteratively multiply an irreducible polynomial to obtain its powers, simplifying and printing the results in sagemath?
For example:
1) Within `GF(59^2)['x']`, the polynomial `x^2 + 2x + 13` is irreducible.
2) Say we use the label `'g'`, we can use this irreducible polynomial to express g squared.
`g^2 = -2g - 13
= 57g + 46
3) Subsequent powers of g can be obtained by iteratively multiplying the previous expression by g.
for example:
g^2 = 57g+46
g^3 = g(g^2) = g(57g+46) = 57g^2 + 46g = 57 (57g + 46) + 46g (mod 59)
= 50g + 26,
g^4 = g(g^3) = g(50g + 26) = 50g^2 + 26g = 50(57g+46) + 26g = (50*57)g + (50 * 46) + 26 g (mod 59)
= 44g + 58,
g^5 = g(g^4) = g(44g + 58) = 44g^2 + 58g = 44(57g+46) + 58g = (44*57)g + (44 * 46) + 58g = 30g + 18+ 58g
=29g + 18
(...)
and so on, up to cycle, or g^59.
The question is:
What would the sagemath code look like to do the following a) initialize g squared, subsequently multiply by g, and simplify mod 59 to print the following output?
Sample output:
g^2 = 57*g + 46
g^3 = 50*g + 26
g^4 = 46*g + 58
g^5 = 25*g + 51
(....)
g^59 = ....
Possible pseudocode:
#initialize the ring
F = GF(59^2)['x']
#initialize the starting point to our g^2
g_current = F('57g + 46')
#loop over an appropriate range
for i in range (1,57):
#accumulate the current power, multiplying the previous by g, and then simplifying
g_current = (g * g_current).simplify()
#print an appropriate line summary
print("g^" + str(i+2) + "=" + str(g_current))
Your help is appreciated.Sat, 22 Oct 2022 06:55:17 +0200https://ask.sagemath.org/question/64555/generating-powers-of-g-an-irreducible-polynomial-in-an-extension-field/Answer by Max Alekseyev for <p>In an extension field, how do you to iteratively multiply an irreducible polynomial to obtain its powers, simplifying and printing the results in sagemath?</p>
<p>For example: </p>
<p>1) Within <code>GF(59^2)['x']</code>, the polynomial <code>x^2 + 2x + 13</code> is irreducible.</p>
<p>2) Say we use the label <code>'g'</code>, we can use this irreducible polynomial to express g squared. </p>
<pre><code>`g^2 = -2g - 13
= 57g + 46
</code></pre>
<p>3) Subsequent powers of g can be obtained by iteratively multiplying the previous expression by g. </p>
<p>for example:</p>
<pre><code> g^2 = 57g+46
g^3 = g(g^2) = g(57g+46) = 57g^2 + 46g = 57 (57g + 46) + 46g (mod 59)
= 50g + 26,
g^4 = g(g^3) = g(50g + 26) = 50g^2 + 26g = 50(57g+46) + 26g = (50*57)g + (50 * 46) + 26 g (mod 59)
= 44g + 58,
g^5 = g(g^4) = g(44g + 58) = 44g^2 + 58g = 44(57g+46) + 58g = (44*57)g + (44 * 46) + 58g = 30g + 18+ 58g
=29g + 18
(...)
and so on, up to cycle, or g^59.
</code></pre>
<p>The question is:</p>
<pre><code>What would the sagemath code look like to do the following a) initialize g squared, subsequently multiply by g, and simplify mod 59 to print the following output?
</code></pre>
<p>Sample output:</p>
<pre><code>g^2 = 57*g + 46
g^3 = 50*g + 26
g^4 = 46*g + 58
g^5 = 25*g + 51
(....)
g^59 = ....
</code></pre>
<p>Possible pseudocode:</p>
<pre><code>#initialize the ring
F = GF(59^2)['x']
#initialize the starting point to our g^2
g_current = F('57g + 46')
#loop over an appropriate range
for i in range (1,57):
#accumulate the current power, multiplying the previous by g, and then simplifying
g_current = (g * g_current).simplify()
#print an appropriate line summary
print("g^" + str(i+2) + "=" + str(g_current))
</code></pre>
<p>Your help is appreciated.</p>
https://ask.sagemath.org/question/64555/generating-powers-of-g-an-irreducible-polynomial-in-an-extension-field/?answer=64591#post-id-64591First, 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](https://en.wikipedia.org/wiki/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}')
Mon, 24 Oct 2022 15:49:07 +0200https://ask.sagemath.org/question/64555/generating-powers-of-g-an-irreducible-polynomial-in-an-extension-field/?answer=64591#post-id-64591