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.Thu, 16 Dec 2021 11:43:18 +0100Computing element norm from its conjugates in towered extension fieldshttps://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/Hi!
I'm trying to compute the norm of an element by using the product of its conjugates.
This works fine for extensions of prime fields, but seems to give me results different than expected for extension towers.
Example from BLS12-381 curve:
field_modulus = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
Fp = GF(field_modulus)
R.<x> = Fp[]
Fp2.<u> = Fp.extension(x^2 + 1)
R2.<y> = Fp2[]
Fp6.<v> = Fp2.extension(y^3 - (u+1))
# This works for Fp2, which is an extension of a prime field
elem_fp2 = Fp2([1, 1])
fp2_norm_from_conjugates = elem_fp2 * elem_fp2 ^ field_modulus
elem_fp2.norm() == fp2_norm_from_conjugates
# But not for the towered extension Fp6
elem_fp6 = Fp6([1, 1, Fp2([2, 3])])
fp6_norm_from_conjugates = elem_fp6 * (elem_fp6 ^ field_modulus) * (elem_fp6 ^ (field_modulus^2))
elem_fp6.norm() == fp6_norm_from_conjugates
# False
What I am expecting from the above is that `norm()` maps an element from the extension field to an element in the base field, i.e. `elem_fp2.norm()` to return an element of `Fp` and ` elem_fp6.norm()` an element of `Fp2`.
This is indeed true when I use the `norm()` method (which, under the hood uses `matrix().determinant()`), but fails when using the element's conjugates in the towered field.
(I'm using pages 57-58 of the [Finite Fields] (https ://archive.org/details/finitefields0000lidl_a8r3/) book as reference, which states that I should just be able to multiply the elements and all its conjugates to get the norm):
`\alpha * \alpha^q * ... * \alpha^(q^m-1)`
Am I doing something wrong?Wed, 15 Dec 2021 16:23:38 +0100https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/Comment by slelievre for <p>Hi!</p>
<p>I'm trying to compute the norm of an element by using the product of its conjugates.
This works fine for extensions of prime fields, but seems to give me results different than expected for extension towers.</p>
<p>Example from BLS12-381 curve:</p>
<pre><code>field_modulus = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
Fp = GF(field_modulus)
R.<x> = Fp[]
Fp2.<u> = Fp.extension(x^2 + 1)
R2.<y> = Fp2[]
Fp6.<v> = Fp2.extension(y^3 - (u+1))
# This works for Fp2, which is an extension of a prime field
elem_fp2 = Fp2([1, 1])
fp2_norm_from_conjugates = elem_fp2 * elem_fp2 ^ field_modulus
elem_fp2.norm() == fp2_norm_from_conjugates
# But not for the towered extension Fp6
elem_fp6 = Fp6([1, 1, Fp2([2, 3])])
fp6_norm_from_conjugates = elem_fp6 * (elem_fp6 ^ field_modulus) * (elem_fp6 ^ (field_modulus^2))
elem_fp6.norm() == fp6_norm_from_conjugates
# False
</code></pre>
<p>What I am expecting from the above is that <code>norm()</code> maps an element from the extension field to an element in the base field, i.e. <code>elem_fp2.norm()</code> to return an element of <code>Fp</code> and <code>elem_fp6.norm()</code> an element of <code>Fp2</code>.
This is indeed true when I use the <code>norm()</code> method (which, under the hood uses <code>matrix().determinant()</code>), but fails when using the element's conjugates in the towered field.</p>
<p>(I'm using pages 57-58 of the [Finite Fields] (https ://archive.org/details/finitefields0000lidl_a8r3/) book as reference, which states that I should just be able to multiply the elements and all its conjugates to get the norm):
<code>\alpha * \alpha^q * ... * \alpha^(q^m-1)</code></p>
<p>Am I doing something wrong?</p>
https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/?comment=60282#post-id-60282Welcome to Ask Sage! Thank you for your question.Wed, 15 Dec 2021 16:33:19 +0100https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/?comment=60282#post-id-60282Answer by Max Alekseyev for <p>Hi!</p>
<p>I'm trying to compute the norm of an element by using the product of its conjugates.
This works fine for extensions of prime fields, but seems to give me results different than expected for extension towers.</p>
<p>Example from BLS12-381 curve:</p>
<pre><code>field_modulus = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
Fp = GF(field_modulus)
R.<x> = Fp[]
Fp2.<u> = Fp.extension(x^2 + 1)
R2.<y> = Fp2[]
Fp6.<v> = Fp2.extension(y^3 - (u+1))
# This works for Fp2, which is an extension of a prime field
elem_fp2 = Fp2([1, 1])
fp2_norm_from_conjugates = elem_fp2 * elem_fp2 ^ field_modulus
elem_fp2.norm() == fp2_norm_from_conjugates
# But not for the towered extension Fp6
elem_fp6 = Fp6([1, 1, Fp2([2, 3])])
fp6_norm_from_conjugates = elem_fp6 * (elem_fp6 ^ field_modulus) * (elem_fp6 ^ (field_modulus^2))
elem_fp6.norm() == fp6_norm_from_conjugates
# False
</code></pre>
<p>What I am expecting from the above is that <code>norm()</code> maps an element from the extension field to an element in the base field, i.e. <code>elem_fp2.norm()</code> to return an element of <code>Fp</code> and <code>elem_fp6.norm()</code> an element of <code>Fp2</code>.
This is indeed true when I use the <code>norm()</code> method (which, under the hood uses <code>matrix().determinant()</code>), but fails when using the element's conjugates in the towered field.</p>
<p>(I'm using pages 57-58 of the [Finite Fields] (https ://archive.org/details/finitefields0000lidl_a8r3/) book as reference, which states that I should just be able to multiply the elements and all its conjugates to get the norm):
<code>\alpha * \alpha^q * ... * \alpha^(q^m-1)</code></p>
<p>Am I doing something wrong?</p>
https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/?answer=60287#post-id-60287If you check the parent of `elem_fp6`, you'll see:
Univariate Quotient Polynomial Ring in v over Finite Field in u of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787^2 with modulus ...
Correspondingly, rather than using `field_modulus` in computing `fp6_norm_from_conjugates`, you need to use its square:
field_modulus2 = field_modulus^2
fp6_norm_from_conjugates = elem_fp6 * (elem_fp6 ^ field_modulus2) * (elem_fp6 ^ (field_modulus2^2))Wed, 15 Dec 2021 16:49:27 +0100https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/?answer=60287#post-id-60287Comment by mmagician for <p>If you check the parent of <code>elem_fp6</code>, you'll see:</p>
<pre><code>Univariate Quotient Polynomial Ring in v over Finite Field in u of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787^2 with modulus ...
</code></pre>
<p>Correspondingly, rather than using <code>field_modulus</code> in computing <code>fp6_norm_from_conjugates</code>, you need to use its square:</p>
<pre><code>field_modulus2 = field_modulus^2
fp6_norm_from_conjugates = elem_fp6 * (elem_fp6 ^ field_modulus2) * (elem_fp6 ^ (field_modulus2^2))
</code></pre>
https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/?comment=60310#post-id-60310That's great, works like a charm.Thu, 16 Dec 2021 11:43:18 +0100https://ask.sagemath.org/question/60275/computing-element-norm-from-its-conjugates-in-towered-extension-fields/?comment=60310#post-id-60310