Tagged Questions

4
votes
2answers
34 views

Linear polynomials of finite fields

I have a final tomorrow, and I was looking over some exercises in my textbook. However, I can't seem to work this problem out. Let $F$ be a field of $p^n$ elements and let $\alpha \in F^*$, where ...
1
vote
1answer
53 views

Solve equations in a field with characteristic p.

Let $p$ be a prime and $K$ a field with characteristic $p$. How to solve the equation $x^2+2=0$ in the field $K$? Here $x, 2, 0 \in K$. Is it equivalent to solve the equation $x^2+2 = 0 \pmod p$? What ...
8
votes
3answers
187 views

Solve $x^3+x \equiv 1 \pmod p$

Find all the primes $p$ so that $$x^3+x \equiv 1 \pmod p \tag{1}$$ has integer solutions. We consider $x$ and $y$ are the same solutions iff $x\equiv y \pmod p.$ We can prove that $(1)$ cannot ...
1
vote
1answer
41 views

Finding quadratic residues in a finite field by using a primitive element

Let $1+2x$ be a primitive element of the field $\mathbb F_9$ obtained via the irreducible polynomial $$x^2 + 1$$ over the base field $\mathbb F_3$. i) Make a list of the elements of $\mathbb F_9$ ...
1
vote
1answer
60 views

Rational and irrational fractions over finite fileds [duplicate]

I've been told that over the field $\mathbb{F}_7$ the square root of $2$ is actually $3$. How come? Why does it happen?
3
votes
2answers
105 views

Polynomial $x^3- xy^3$ and the like over finite fields.

Let $f_{a,n}(x_1,x_2)$ be a polynomial in $\mathbb{F}_p[x_1,x_2]$, where $\mathbb{F}_p$ is a finite field or oder $p$ (perhaps, we may first assume that $p$ is prime) depending on $a\in\mathbb{F}_p$ ...
5
votes
0answers
91 views

Proof that $t^8+2t^6+4t^4+t^2+1$ is reducible in $\mathbb{F}_p$

Prove that the polynomial $t^8+2t^6+4t^4+t^2+1$ is reducible in $\Bbb F_p$, for all $p\in \Bbb P$. Here are some examples: $t^8+2t^6+4t^4+t^2+1=(1 + t + t^4)^2\pmod{2}$ $t^8+2t^6+4t^4+t^2+1=(1 + t) (2 ...
2
votes
1answer
32 views

Representing an element mod $n$ as a product of two primes

Given a positive integer $n$ and $x \in (\mathbb{Z}/n\mathbb{Z})^*$ what is the most efficient way to find primes $q_1,q_2$ st $$q_1q_2 \equiv x \bmod n$$ when $n$ is large? One option is just to ...
10
votes
1answer
100 views

Orientation on finite dimensional vector spaces over finite fields.

For finite-dimensional $\mathbb R$-vector spaces, we define an orientation to be an equivalence class of ordered bases, where $B_1 \sim B_2$ iff the change of basis matrix $A$ taking $B_{1}$ to ...
8
votes
3answers
146 views

Using Hensel's Lemma to Factor a Polynomial over $\mathbb{Z}_4[x]$

We recently learned about codes over $\mathbb{Z}_4$, and Hensel's Lemma. The lemma is as follows: Let $f(x) \in \mathbb{Z}_4[x]$. Suppose $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$, where $h_1(x), ...
1
vote
1answer
76 views

Largest power of a prime dividing $q^m-1$

For positive integers $x$ and $d$ let $v_d(x)$ be the largest power of $d$ dividing $x$. Let $q>1$, $m$ a natural number, and $l$ a prime dividing $q-1$. Then I want to show that ...
13
votes
2answers
369 views

Formula for number of solutions to $x^4+y^4=1$, from Ireland and Rosen #8.18.

There is a sequence of three exercise in Ireland and Rosen's Introduction to Modern Number Theory, Chapter 8, page 106. I can do the first two, but can't finish the third. I can include the proofs to ...
0
votes
1answer
56 views

Formal identity for sum of polynomials over a finite field.

Suppose $F$ is a finite field of order $q$ a prime power. If $f\in F[x]$ of degree $t$, set $|f|=q^t$. Let $\sigma(f)=\sum_{g\mid f}|g|$ where the sum is over the monic divisors of $f$. Why does ...
3
votes
1answer
60 views

Generators for $\mathbb F_p^*$

Let $p$ be prime, then it is a well-known fact that $\mathbb F_p^*= \mathbb F_p -\{0\}$ is a cyclic group under multiplication. Are there any methods to determine the generators of this cyclic or any ...
3
votes
1answer
54 views

Abelian groups related to $(\mathbb{Z}/p\mathbb{Z})^*$, with order close to $p$ — analogous to elliptic curve groups, but simpler

I'm looking for a construction of a group $H$ that is "a sister" to $(\mathbb{Z}/p\mathbb{Z})^*$, in the following rough sense: Each element of $H$ can be represented by one or a few elements of ...
3
votes
2answers
69 views

Are nonsquares actually squares in extensions of even degree?

I was playing around with finite fields, and noticed that if $F$ is a finite field, and $E$ an extension of odd degree, then every nonsquare $a\in F$ is again a nonsquare in $E$. I found this out by ...
2
votes
1answer
54 views

Showing $x^n=\alpha$ has $n$ solutions in a field extension of degree $n$.

Suppose $F$ is a field of cardinality $q$, and $n$ is an integer such that $n\mid q-1$. Now let $K$ be an extension of degree $n$ over $F$. Why does $x^n=\alpha$ have $n$ solutions in $K$ for any ...
1
vote
1answer
46 views

$a(x) \bmod m(x)$ for $m(x) > a(x)$?

Suppose we have polynomials over $GF (2^8)$. $a(x) = x^8$. $m(x) =x^8+x^4+x^3+x+1$ A textbook says that. $x^8 \bmod m(x) = [m(x) - x^8]=(x^4+x^3+x+1)$ So I would like to understand, how do we ...
1
vote
1answer
92 views

Field construction

Explain how to construct a field of order $343$ not using addition and multiplication tables. I understand that every finite field has order $p^n$ for some prime $p$. Since $343$ is $7^3$, let ...
5
votes
1answer
87 views

Irreducible polynomials over $F_q$ with exponents of the form $q^k - 1$.

Let $q$ be some prime power. Is there an explicit family of irreducible polynomials in $F_q[X]$ of the form $\sum_j a_j X^{q^j - 1}$? Thanks!
2
votes
2answers
72 views

Encode the message $[1,1,0,1,1,0,1]$ in BCH code based on the field $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1}$

So here's what I understand so far: $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1} = GF(16)$ The code is written as $[x^{14},x^{13},x^{12},x^{11},x^{10},x^{9},x^{8}$ $|$ ...
0
votes
1answer
50 views

The probability of sum of $k$ randomly chosen numbers from $\mathbb{Z}_p$ being zero

Let $\{x_i\}_{i \in [k]}$ be randomly chosen independently from the uniform distribution over $\mathbb{Z}_p$. What is the probability that $\Sigma_{i\in [k]} x_i = 0$?
1
vote
1answer
169 views

Proving a polynomial irreducible over finite field [duplicate]

Possible Duplicate: How do I prove that $x^p-x+a$ is irreducible in a field of $p$ elements when $a\neq 0$? How to prove that $x^p - x - 1$ is irreducible over $F_{p}[x]$. I thought ...
0
votes
1answer
276 views

Reed-Solomon Code calculation

I have a Reed-Solomon Code which can correct t=2 errors. The generator polynomial is $p(X) = X^3 + X + 1$ and $p(a) = a^3 + a + 1 = 0$ this means $a^3 = a + 1$ What is the degree of generator ...
8
votes
4answers
227 views

Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$

Let $\mathbb F$ be field with $q$ element and $\operatorname{char}(\mathbb F)\neq2$. I want to know about the number of solutions of this equation: $$x^2_1+x^2_2+\dots+x^2_n=0 \text{ where } x_i\in ...
5
votes
1answer
190 views

Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})[X]$

Is it possible to determine how many irreducible factors $X^p-1$ in the polynomial ring $(\mathbb{Z}/q \mathbb{Z})[X]$ has and maybe even the degrees of the irreducible factors? ($p,q$ are a primes ...
5
votes
1answer
736 views

Existence of irreducible polynomials over finite field

Let $F$ be a finite field. How do we prove that for each $n \in \mathbb{N}$ there is an irreducible polynomial of degree $n$? One can assume that $F = \mathbb{F}_{p^m}$ where $p$ is prime. If $n \ge ...
2
votes
1answer
89 views

The digit base and the NTT convolution

Suppose I'm using a number theoretic transform (NTT) in an integer field $GF(p)$. I assume that $2n$-th root of unity exists for such a $p$, and I want to compute a convolution of two $n$-length ...
2
votes
1answer
105 views

Discrete log of consecutive numbers

I am trying to understand the relation of additive and multiplicative structure of finite field of prime cardinality. Let's say I have a set that behaves nice additively - an interval $I = ...
5
votes
2answers
217 views

A question on Jacobi sums

I am trying to work through Ireland and Rosen's Number theory book. Following is ex. 26, ch.8(Gauss and Jacobi sums). Let $p$ be a prime. $p\equiv 1\mod{4}$, $\chi$ a multiplicative character of ...
5
votes
2answers
3k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
-9
votes
1answer
628 views

A Hunt for a Mathematical Machine That Gives Points

The central question is : Is there any method for Producing the global Points on the curve (any cubic curve, or at least a Degree-2 curve ) , if we have local Part with us ? Explanation: ...
2
votes
2answers
440 views

What is Galois Field

When I am reading some algorithm related to error correction. To generate some polynomial it uses finite-field which is Galois field. I am not from mathematical background. Can anybody explain me in ...
1
vote
1answer
144 views

How to nicely extend finite field?

I'm working on an implementation of Miller's algorithm that computes the Weil pairing (elliptic curves, cryptography). In order to do that, I have to implement finite fields. So far I have managed to ...
-1
votes
1answer
165 views

Finite extension of $\mathbb Q_p$

Let $\mathbb K/\mathbb Q_p$ be a finite extension of $p-$adic field $\mathbb Q_p$. Let ${\mathcal O}=\{x\in K\;:\;|x|\leq1\}$ and ${\mathcal P}=\{x\in K:\;|x|<1\}$, here $|\cdot|$ is the absolute ...
5
votes
3answers
377 views

Other ways to deduce Cyclicity of the Units of certain groups?

The group of units of the rings $\text{GF}(p^r)$ and $\mathbb{Z}/p^r\mathbb{Z}$ are both cyclic (except for the exception of prime powers are not cyclic when $p=2$ and $r\ge 3$). This is a strong ...
8
votes
1answer
193 views

Is $\mathbb{Q}_p(\zeta_p)$ the same as $\mathbb{Q}_p(p^{\frac{1}{p-1}})$?

It seems so. $\mathbb{Q}_p(\zeta_p)$ is a $p-1^{th}$ extension of $\mathbb{Q}_p$ which doesn't extend the residue field; and so is $\mathbb{Q}_p(p^{\frac{1}{p-1}})$. However I can't see how to express ...