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, 16 Apr 2018 09:57:45 +0200Square root of polynomial modulo another irreducible polynomialhttps://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!tobiasBoraMon, 16 Apr 2018 09:57:45 +0200https://ask.sagemath.org/question/42042/irreducible polynomial defining the finite fieldhttps://ask.sagemath.org/question/41473/irreducible-polynomial-defining-the-finite-field/X = GF(2).polynomial_ring().gen()
F = GF(2^8, name="a", modulus=X^8 + X^6 + X^5 + X + 1)
As example above, the polynomial X^8 + X^6 + X^5 + X + 1 is one of irreducible polynomial defining the finite field GF(2^8).
How can I get all the irreducible polynomial which can define the finite field GF(2^8)?omggggggSat, 10 Mar 2018 18:22:06 +0100https://ask.sagemath.org/question/41473/What is the effect of declaring a polynomial `sparse'?https://ask.sagemath.org/question/34095/what-is-the-effect-of-declaring-a-polynomial-sparse/I do some work on polynomials over finite fields. Generated polynomials of larger degree are sparse in the sense that only a few coefficients are not zero. I tried to utilize this property by defining PR=PolynomialRing(GF(7),name='x',sparse=True). Then type(PR) is
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category'>
what is not very informative. It is not clear which library is involved (FLINT, NTL, Sage's own implementation, or something else), and libraries FLINT, NTL seem not to support sparse polynomials (sparse in the sense of storing only the non-zero coefficients similar to sparse matrices).
So what does "sparse=True" mean? Is there a reduction of occupied memory? Anyway, time consumption for multiplication increases tremendously (I expected a major reduction).
Thanks in advance.
Function "make_pol" defined below generates for any target degree "deg" a polynomial over a finite field. Only about "deg^ex" coefficients are not zero where "ex" depends on the field's order and is in interval (1/2, 1), in particular "ex" is about 3/4 for field order 7. The reason for the sparsity is not yet understood. Multiplication of polynomials over GF(7) of degrees 100043 and 100361 (and 6144 coefficients each) generated this way takes 36 milliseconds for dense implementation but 29 seconds (without "milli"!) for sparse implementation (similarly for the function call, the function uses multiplications). If you are curious about the chosen degrees: these are Sophie Germain primes, they are of special interest since the generated polynomials are irreducible.
Platform info: 64 bit, 3.3GHz, Linux, Sage 7.1 (Release Date: 2016-03-20)
from sage.all import ZZ, GF, PolynomialRing
def make_pol(deg, char, sparse):
"""
Generate a sparse polynomial over a finite field.
INPUT:
"deg" target degree (natural number)
"ch" field characteristic (prime number)
"sparse" whether a sparse implementation to use (boolean)
OUTPUT:
Polynomial in 'x' of degree "deg" over field "GF(ch)".
Only about "deg^ex" (where "ex"<1) coefficients are not zero,
value of "ex" depends on "ch", e.g. "ex==3/4" for "ch==7".
"""
if not deg in ZZ or deg<0:
raise ValueError("First arg must be a non-negative integer.")
if not char in ZZ or not is_prime(ch):
raise ValueError("Second arg must be a prime number.")
R = PolynomialRing(GF(ch),'x',sparse=sparse)
i0 = 0
r0 = R(1)
s = R.gen()
if deg == 0:
return r0
i1 = 1
r1 = s+R(1)
if deg == 1:
return r1
i2 = 2
r2 = s*r1 - r0
if deg == 2:
return r2
k = 1
while i2 < deg:
if deg & k != 0:
i3 = 2*i2-i1
r3 = s*r2 - r1
i0 = i1
r0 = r1
i1 = i3
r1 = r3
else:
i1 = i2
r1 = r2
k = 2*k
s = s**2 - 2
i2 = 2*i1 - i0
r2 = s*r1 - r0
if deg == i2:
return r2
return r3
wjansenFri, 15 Jul 2016 17:20:06 +0200https://ask.sagemath.org/question/34095/Get coefficients of a polynomial in quotient ringhttps://ask.sagemath.org/question/24902/get-coefficients-of-a-polynomial-in-quotient-ring/Let say I have the following quotient ring:
F.<t> = PolynomialRing(GF(2), 'x').quotient(x^128 + x^7 + x^2 + x + 1);
Then I create a polynomial, for example t^128 which yields:
t^7 + t^2 + t + 1
Now how do I obtain the array of coefficients of this polynomial?
Or, similarly, how do I actually substitute 2 for t and evaluate this polynomial? The `subs` method doesn't work. (Probably the polynomial needs to be coerced to other ring with base field where 2 != 0).
NumberFourTue, 18 Nov 2014 13:04:35 +0100https://ask.sagemath.org/question/24902/Defining Polynomial Basis and Generic Polynomialshttps://ask.sagemath.org/question/8885/defining-polynomial-basis-and-generic-polynomials/Given a Extension Field , say GF(2**4) with modulus polynomial f(x), I would like to a) Define a polynomial basis [1,x,x^2,x^3] for its elements. b) Define a general polynomial as a0 + a1*x + a2*x^2 +a^3. Currently for part (a) I am defining the basis as a tuple, but I have an inkling that it is the worst possible fix. Kindly suggest a better alternative and a solution for part (b).Prateek_123Fri, 20 Apr 2012 08:17:30 +0200https://ask.sagemath.org/question/8885/Define function in GF(q)https://ask.sagemath.org/question/8862/define-function-in-gfq/Hi,
First of all I say that these are my first steps in SAGE.
I want to define a function f(x,y), where x,y in GF(q), q=2^3 and next check all possible values of this function (for all x,y in GF(q)). If it will be necessary I'll write more details about function f.
Could you give me some advices how can I do it in SAGE?
Any help will be highly appreciated.
I wish you a very happy Easter!
Best regards,
ArturArczi84Fri, 06 Apr 2012 11:08:12 +0200https://ask.sagemath.org/question/8862/