Finite fields are structures arising in abstract algebra. The order of a finite field is always a prime power, and for each prime power $q$ there is a single isomorphism type. It is usually denoted by $\mathbb{F}_q$ or $\operatorname{GF}(q)$.
2
votes
1answer
201 views
The number of subspaces of a vector space
Let $V$ be a vector space of dimension $n$ over $\mathbb{F}_q$, and let $U$ be a subspace of dimension $k$. I want to compute the number of subspaces $W$ of $V$ of dimension $m$ such that $W\cap U=0$.
...
1
vote
1answer
45 views
irreducibilty of a polynomial over finite field
$f=x^4-x^3+14x^2+5x+16$,
$1$. considering it a polynomial with coeficent in $\mathbb{F}_3$, it has no roots
$2$. Considering it a polynomial with coeficent in $\mathbb{F}_3$,it is a product of two ...
0
votes
1answer
34 views
Multiplication over $F_{2^{31}-1}$ by power of $2$
I'm reading the source code of a stream cypher (zuc):
I cannot understand properly why they define the multiplication by power of 2 in this way:
...
10
votes
0answers
85 views
Combinatorics in finite vector space
Let $q$ be a prime power and $V$ a finite $\mathbb F_q$-vector space with two subspaces $I$ and $J$.
Let $k$, $a$ and $b$ be non-negative integers.
Determine the number of subspaces $K$ of $V$ ...
7
votes
0answers
102 views
Error correction code handling deletions and insertions
I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length.
I'm looking for error correction code that would allow me to append one or more ...
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 ...
5
votes
0answers
51 views
Subgroup Structure of $\mathrm{SL}(2, p^2)$, and Its Irreducible Characters
I am taking a course in representation theory of finite groups,and somehow I ended up getting assigned to write a report on subgroup structure and irreducible characters of $\mathrm{SL}(2,7)$ and ...
4
votes
0answers
76 views
Minimal polynomial of a finite purely inseparable field extension
Given $F$, a field with characteristic $p > 0$, and a finite purely inseparable field extension $E$. Then prove that the minimal polynomial $f(x)$ of any $\alpha \in E\backslash F$ will be of the ...
4
votes
0answers
96 views
Existence of a special set of q+2 points in the finite affine plane over $\mathbb F_q$
I am working in the finite affine plane over $\mathbb F_q$ with $q=2^n$.
Such a plane has $q^2$ points, $q^2+q$ lines, each line has $q$ points, and by a point is passing $q+1$ lines.
There are $q+1$ ...
3
votes
0answers
53 views
Deligne and the four Weil statements about polynomials over finite fields?
This article mentions he recently won 3 million of some money. Does anyone have a link to the original Deligne paper that proves this, and could anyone give a basic rundown of how "counting points on ...
3
votes
0answers
109 views
when do two rational elliptic curves have identical size when reduced mod $p$ for all primes $p$?
If $E_1$ and $E_2$ are two elliptic curves over $\mathbb{Q}$ such that $|E_1(\mathbb{F}_p)|=|E_2(\mathbb{F}_p)|$ for all primes $p$, what does this tell us about the relationship between $E_1$ and ...
3
votes
0answers
68 views
Does composing the Frobenius with an automorphism give another Frobenius
Let $X_0$ be a variety over $\mathbf{F}_q$. Consider the Frobenius $F_0:X_0\to X_0$. Let $X= X_0\times \bar{\mathbf{F}_q}$ and let $F:X\to X$ be $F_0 \times \textrm{id}$.
Let $f:X\to X$ be an ...
3
votes
0answers
296 views
Hardness of finding eigenvalues over finite fields
How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?)
How ...
2
votes
0answers
44 views
Irreducible polynomial roots and representations for Galois field elements in normal basis
I am trying to understand some topics in the literature and came across the following problem. Say I have a field $GF(2^4)$ defined by the irreducible polynomial $r(z) = z^4 + z + 1$, and I want to ...
2
votes
0answers
29 views
Discrete logarithm - strange polynomials
If $p$ is a prime number and $\omega$ is a fixed primitve root for $\mathbb{Z}/p\mathbb{Z}$, then we can define the discrete logarithm of $x \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ as the unique number ...
2
votes
0answers
39 views
Different elliptic curves over given $\mathbb{F}_q$ can have different orders?
As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders?
I assume yes. Let $q:=5$. Wikipedia gives $9$ points for ...
2
votes
0answers
88 views
What's the fastest way to solve these equations with powers in a field?
This is for an algorithm I'm working on. Perhaps we can work together!
We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find ...
1
vote
0answers
55 views
Full Rank Matrix with a specific construction
Assume that we have a $p \times p$ matrix $Z$ over $\mathbb{F}_{2^p}$
$$Z=\begin{bmatrix}
w_1 & w_1^2& w_1^4& ... & {w_1}^{2^{\frac{p}{2}-1}} & \alpha_1w_1 & ...
1
vote
0answers
21 views
root of binary matrix
There is a square matrix A defined over the field GF(2). It means there are zeros and ones in its cells, xor stands for element summation, logical and - for multiplication.
Is there any way to find ...
1
vote
0answers
13 views
“Randomize” output of a Linear Feedback Shift Register for the same taps?
I'm using a (Galois) LFSR to sample a large array, ensuring that each entry is only visited once. I simply skip past the entries that exceed the array length.
With the same taps then the array entry ...
1
vote
0answers
68 views
How does trigonometry in a Galois field work?
This is a follow-up to this question. I'm interested in doing trigonometry in finite fields on a computer. I do not understand precisely how trigonometric functions are supposed to work in a finite ...
1
vote
0answers
69 views
Generators of Finite Fields and Quadratic Extensions
I want to show that if an element in $\beta \in K$ where $|K|=p^n$ is a generator for $K^*$, i.e. has order $p^n-1$, then there is a generator $\alpha\in L$, $[L,K]=2$ i.e. of order $(p^n)^2-1$, such ...
1
vote
0answers
263 views
Generator and char. polynomial for a binary Galois Field produced by an external-XOR LFSR
My question is regarding LFSRs (Linear Feedback Shift Registers), and the binary Galois Field produced by them (also commonly termed GF($2^n$) ).
I understand that a given n-bit LFSR produces a ...
0
votes
0answers
27 views
Elements of the form $aX^2 + bY^2$ in a finite field.
For cardinality reasons, we know that every element in a finite field $F$ is a sum of two squares. If I fix $a,b\in F$ with $a,b\neq 0$, can every element in $F$ be written in the form $aX^2 + bY^2$ ...
0
votes
0answers
37 views
Let $p$ be a prime. $f(x) = 1 + x + x^2 + … + x^{p-1}$. Show that for any field F the irreducible factors of f(x) in F[x] all have the same degree
Let $p$ be a prime and set $f(x) = 1 + x + x^2 + ... + x^{p-1}$.
Show that for any field $F$ the irreducible factors of $f(x)$ in $F[x]$ all have the
same degree.
If $\operatorname{char}F=0$ , then ...
0
votes
0answers
53 views
How to list all irreducible polynomials in a field?
I am currently trying to refresh my memory on some basic primary polynomials, apologies if my terminologies aren't correct:
For example, I have a field $\Bbb F_{2^3}$ and generates a list of ...
0
votes
0answers
31 views
Approximating a Euclidian Algorithm
Given the problem of computing the GCD of two given elements over any finite field with characteristic 2.
$$ r_1 = q_1r_2 + r_3 \\
r_2 = q_2r_3 + r_4 \\
r_3 = q_3r_4 + r_5 \\
\vdots \\
...
0
votes
0answers
32 views
Euclidean Algorithm Order
Given the problem of computing the GCD of two given elements over any finite field with characteristic. Exist any pattern, rule, relation, among residues $r_1, r_2, r_3 ...$?
$$ r_1 = q_1r_2 + r_3 \\
...
0
votes
0answers
64 views
How can commuting with Frobenius imply the order of an element in the inertia group.
In this video, one asserts, in the beginning, that, for $\tau\in \mathbb V_0$ such that $\tau$ generates $V_0/V_1$ in the quotient group, and $\sigma\in \mathbb Z$ which is a Frobenius in $\mathbb ...
0
votes
0answers
27 views
The mathematics behind Sobol sequences
I am using Sobol sequence as random number generator in a computer program.
Beyond just making the program work, I would like to learn the mathematics behind the Sobol sequence (and other ...
0
votes
0answers
127 views
Is the Algebraic Closure of a Finite Field Algebraically Closed?
A Lemma stated:
Let $F$ be a finite field, of prime characteristic $p$, and with algebraic closure $\overline{F}$. The polynomial $x^{p^{n}} - x$ has $p^{n}$ distinct zeros in $\overline{F}$.
The ...
0
votes
0answers
127 views
Isomorphism of sets
What is an isomorphism of sets?
I know in general an isomorphism is a structure-preserving bijective map between two algebraic structures. But what algebraic structure does a set have? Does a ...
0
votes
0answers
46 views
For any prime $p \equiv 1\pmod{5}$ what integers $\{a_0, \dots, a_4\}$ satisfy $(\sum_{i=0}^{4}{a_ig^i})(\sum_{i=0}^{4}{a_ig^{-i}})=p^2$?
For any prime $p \equiv 1 \pmod{5}$ do there exist 5 integers $\{a_0, \dots, a_4\}$, each of absolute value less than $p$, satisfying $\sum_{i=0}^{4}{a_i}=p$, ...
0
votes
0answers
88 views
Vector subspace and nullspace
Let $W$ be a vector subspace of $\mathbb{F}_2^n$ and $w \in \mathbb{F}_2^n$. Suppose that $w \cdot v = 0$ for all $v \in \text{NullSpace}(W)$. Does it imply that $w \in W$?
0
votes
0answers
206 views
The field of Laurent series on finite fields
Well, it is hard to find a good references on The field of Laurent series on finite fields. Let $F_q$ be any finite field, and denote $F_q((t))$ is the field of Laurent series on $F_q$. Please show ...
