ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 23 Apr 2018 17:37:41 -0500Square root of polynomial modulo another irreducible polynomialhttp://ask.sagemath.org/question/42042/square-root-of-polynomial-modulo-another-irreducible-polynomial/Hello,
If I'm not wrong, it is always possible to compute the square root of a polynomial $P$ modulo an irreducible polynomial $g$ when the base field is in $GF(2^m)$, i.e. find $Q \in GF(2^m)$ such that $Q^2 \equiv P \mod g$. Indeed, the operation $Q \rightarrow Q^2 \pmod g$ should be linear (because we are in $GF(2^m)$) so an idea would be to compute the matrix $T$ that perform this operation, and then invert it, but I'd like to find an embedded operation in sage. I tried the sagemath $P.sqrt()$ method, but the problem is that because it does not take into account the modulo, it fails most of the time when the polynomial has some terms with odd power of $X$.
Any idea?
Thanks!Mon, 16 Apr 2018 02:57:45 -0500http://ask.sagemath.org/question/42042/square-root-of-polynomial-modulo-another-irreducible-polynomial/Answer by dan_fulea for <p>Hello,</p>
<p>If I'm not wrong, it is always possible to compute the square root of a polynomial $P$ modulo an irreducible polynomial $g$ when the base field is in $GF(2^m)$, i.e. find $Q \in GF(2^m)$ such that $Q^2 \equiv P \mod g$. Indeed, the operation $Q \rightarrow Q^2 \pmod g$ should be linear (because we are in $GF(2^m)$) so an idea would be to compute the matrix $T$ that perform this operation, and then invert it, but I'd like to find an embedded operation in sage. I tried the sagemath $P.sqrt()$ method, but the problem is that because it does not take into account the modulo, it fails most of the time when the polynomial has some terms with odd power of $X$.</p>
<p>Any idea?</p>
<p>Thanks!</p>
http://ask.sagemath.org/question/42042/square-root-of-polynomial-modulo-another-irreducible-polynomial/?answer=42144#post-id-42144Let us start with some finite field $F$ of characteristic $2$ with $q = 2^r$ elements,
and some irreducible polynomial $g$ of (small) degree $s$ over this field.
Then $L=F[Y]/g(Y)$ is a field with $q^s=2^{rs}$ elements, so the corresponding Frobenius
morphism is the identity isomorphism of $L$.
Now let us fix $P=P(y)=P(Y)\mod g(Y)$. Let
$$ Q=P^{\displaystyle 2^{rs-1}}\ . $$
Then
$$ Q^2=\left(P^{\displaystyle 2^{rs-1}}\right)^2
=P^{\displaystyle 2^{rs}}=P\ . $$
Example:
F.<a> = GF(2^5)
R.<Y> = PolynomialRing(F)
g = Y^3 + Y + 1
print "Is g = %s irreducible? %s" % ( g, g.is_irreducible() )
S.<y> = R.quotient(g)
P = a*y
Q = P^(2^(3*5-1))
print "P = %s" % P
print "Q = %s" % Q
print "Is Q^2 == P? %s" % bool( Q^2 == P )
This gives:
Is g = Y^3 + Y + 1 irreducible? True
Q = (a^4 + a^3 + a + 1)*y^2 + (a^4 + a^3 + a + 1)*y
Is Q^2 == P? TrueMon, 23 Apr 2018 17:37:41 -0500http://ask.sagemath.org/question/42042/square-root-of-polynomial-modulo-another-irreducible-polynomial/?answer=42144#post-id-42144