All Questions
13
questions
5
votes
2
answers
563
views
Singular Procedure: Vanishing polynomial function (A Singular Introduction to Commutative Algebra)
I have recently started studying the computer algebra system Singular with help of the book „A Singular Introduction to Commutative Algebra“ by Gert-Martin Greuel & Gerhard Pfister.
Since a few ...
user695468
0
votes
1
answer
121
views
Obtaining a primitive polyomial over $GF(p^b)$ from a primitive p0lynomial over $GF(p)$.
Let $f$ be a monic primitive polynomial of degree $ab$ over $\mathbb{F}_p$ and let $x$ be a root of $f$.
Let $k = x^{c\frac{p^{ab}-1}{p^b - 1}}$, where $\mathrm{gcd}(c, p^b -1)=1$. Then there is a ...
- 85
1
vote
0
answers
49
views
Primitive polynomials from GF(q) to GF(q^n)
Suppose that over some finite field $GF(q)$, we have two monic primitive polynomials of orders $n$ and $mn$.
-From these polynomials, is there always a 'natural' monic primitive polynomial over $GF(q^...
- 85
2
votes
2
answers
2k
views
Algorithm to find the irreducible polynomial
What algorithm can be used find an irreducible polynomial of degree $n$ over the field $GF(p)$ for prime $p$. The reason I ask is I want to make a program for finite field arithmetic, but creating a ...
- 10.5k
2
votes
1
answer
307
views
Pth Root of Polynomial Over Finite Fields for Yun's Algorithm
While I was implementing Yun's algorithm in java, I could not figure out an algorithm to find the $p$th root of a polynomial in $\mathbf{F}_p$ where the polynomial is a perfect power of $p$. How would ...
- 436
1
vote
1
answer
259
views
Is there any algorithm that produces irreducible polynomials over $\mathbb{F}_2$?
Is there any (fast) algorithm that produces irreducible polynomials over $\mathbb{F}_2$?
EDIT:
I look up for a irreducible polynomial generator, that is different from decider algorithm for ...
- 39
4
votes
1
answer
3k
views
Fast polynomial division algorithm over finite field
Recently, I am working on polynomial division. Suppose coefficients of all polynomials are elements in $GF(2^q)$. I want to calculate the remainder such that
$f(x) = g(x)q(x) + r(x)$ (1)
I searched ...
- 427
0
votes
1
answer
85
views
Which one is Faster: Factoring a polynomial of degree $c\cdot d$ or Factoring $c$ number of degree $d$ polynomials?
I consider polnomial $T(x)$ defined over a finite field $\mathbb{F}_p$ where $p$ is a large prime number (256-bit). I want to factorize the polynomials over the finit field. The dgree of $T(x)$ is $c\...
- 311
5
votes
2
answers
196
views
Differentiate polynomials in $\mathbb{Z}_2[x]$
It seems suggested that the differential of a polynomial in $\mathbb{Z}_2$ is as I would expect:
$$\begin{align}
&f = x^6 + x^3 + x + 1 \\
&f' = 6x^5 + 3x^2 +1 \mod 2 \\
&f'= x^2 + 1 \\
\...
- 585
0
votes
1
answer
381
views
Do there exist polynomials not computable in polynomial time?
Motivation: Computing a problem in $k$ memory slots
Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$?
Thanks... Good luck!
Edit. I ...
6
votes
2
answers
1k
views
Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?
I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials here....
- 261
1
vote
2
answers
622
views
Solve a set of non linear Equations on Galois Field
I have the following set of equations:
$$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$
$$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$
$M_1, M_2, x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m).$ I want to ...
- 63
11
votes
2
answers
13k
views
Finding irreducible polynomials over GF(2) with the fewest terms
I'm investigating an idea in cryptography that requires irreducible polynomials with coefficients of either 0 or 1 (e.g. over GF[2]). Essentially I am mapping bytes to polynomials. For this reason, ...
- 213