36
votes

Accepted

### The period of Fibonacci numbers over finite fields

This maybe too elementary for this site, so if your question is closed, you might try asking on MathStackExchange. Many questions about the period can be answered by using the formula
$$ F_n = (A^n-B^...

32
votes

Accepted

### Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?

This is true. Pass to an extension field where the polynomial has a root $r$, notice that the other roots are of the form $r+1$, $r+2$, ..., $r+p-1$. Suppose that $x^p - x +1 = f(x) g(x)$, with $f, g \...

28
votes

### How can I solve a cubic equation in a finite field with characteristic 2?

An alternative approach that works even when $n$ is too large to
store a table of size $2^n$: translate $x$ by $a$ to get $z^3+pz+q = 0$
where $z=x+a$; then multiply by $z$ to get $z^4 + pz^2 + qz = 0$...

25
votes

Accepted

### A curious identity related to finite fields

For prime $q \geq 5$ write the count as
$$
\frac1{1152} q (q-1) (q^3 - 21q^2 + 171 q - c_q)
$$
where
$$
c_q = 483 + 36 \left(\frac{-1}{q}\right) + 64 \left(\frac{-3}{q}\right)
+ \delta_q.
$$
Then for $...

23
votes

### Algebraic dependency over $\mathbb{F}_{2}$

Not for $n=2$. I'm afraid this answer uses a lot more algebraic geometry than the question; I spent some time trying to remove it and failed.
Suppose, for the sake of contradiction, that $f_1$ and $...

23
votes

### The period of Fibonacci numbers over finite fields

I won't address your question about how small the period of $\{F_n \bmod p\}$ can be as $p$ grows, but instead ask if the upper bounds on the period can be achieved infinitely often. For consistency I'...

22
votes

Accepted

### Conjecture: The number of points modulo $p$ of certain elliptic curve is $p$ or $p+2$ for $p$ of form $p=27a^2+27a+7$

The conjecture is true. To prove it, we can restrict to $k=1$ as explained in the comments. Let $\chi$ denote a cubic Dirichlet character modulo $p$; this exists as $p\equiv 1\pmod{3}$, and it is ...

20
votes

Accepted

### Roots of a polynomial in a finite field related to Fermat's Last Theorem

This is true.
Let $P(x) = \sum_{n=1}^{l-1} \frac{x^n}{n} \in {\mathbb F}_l[x]$ (this is $x^{l-1} P_l(x^{-1})$). Then we have $P(1-x) = P(x)$ (check that they have the same derivative and the same ...

20
votes

Accepted

### (Barely) linearly independent vectors over $\mathbb{Z}/2\mathbb{Z}$

Since every $n$ vectors span a space of dimension $n-1$, the whole set $S$ spans a space of dimension $n-1$, and we can assume that $V$ has dimension $n-1$.
Choose $n-1$ linearly independent vectors $...

18
votes

Accepted

### Is hyperelliptic cryptography "practical"?

I am not aware of anybody seriously considering hyperelliptic curves for actual real-world usage, beyond toys, and I would be rather surprised to hear differently from anyone.
As you say, ...

18
votes

Accepted

### Does the equation $x^2+x=a$ have an integer solution?

The answer is yes, and in general if $f(x)\in\mathbb{Z}[x]$ is a monic irreducible polynomial whose Galois group contains a cycle of length $\deg f$ (which is always the case when $\deg f$ is prime, ...

17
votes

### A curious identity related to finite fields

Let $t_1,t_2,t_3,t_4,s_1,s_2,s_3,s_4$ be eight distinct elements of $\mathbb F_q$ such that the middle three coefficients of $(x-t_1)(x-t_2)(x-t_3)(x-t_4)$ are the same as the middle three ...

17
votes

### Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?

The probability that two elements of a finite group $G$ commute is $k(G)/|G|$, where $k(G)$ is the number of conjugacy classes of $G$. Hence the number of pairs of commuting elements is $k(G)|G|$. ...

17
votes

### Polynomials which are functionally equivalent over finite fields

The cardinality of $S_f$ is $p^{ \max(0, d+1-p)}$ because $S_f$ consists of polynomials of the form $f + (x^p-x) g$ with $g$ of degree $\leq d-p$.
The fact that such polynomials lie in $S_f$ follows ...

16
votes

### Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?

Here is an alternate proof of the OP's first conclusion, based on the same idea as David's, but which avoids consideration of coefficients. Let $r$ be a root of $h(x):=x^p-x+1$, so that $r\notin\...

16
votes

Accepted

### Linear permutations commuting with $x\rightarrow x^{-1}$

The answer is no: a linear transformation of $F$ which commutes with $\phi$ is an automorphism of $F$.
This is a seemingly inelegant but simple argument.
Any map $\psi: F \rightarrow F$ can be ...

16
votes

### Is there an $\mathbb{R}$-valued cohomology theory for varieties over $\mathbb{F}_p$?

Let me advertise a conjectural positive answer to a slightly different question. This actually works not only over $\mathbb F_p$ but over its algebraic closure $\overline{\mathbb F}_p$.
Consider the ...

15
votes

Accepted

### Steinberg representation for sporadic simple groups?

The approach that I have taken to generalizing the Steinberg module to finite groups other than groups of Lie type is that, in general, the object we should consider is a chain complex, rather than ...

15
votes

### How many Lie and associative algebras over a finite field are there?

Bjorn Poonen addresses this question for commutative (associative, unital) algebras in The moduli space of commutative algebras of finite rank; asymptotically we have
$$q^{\frac{2}{27} n^3 + O(n^{8/3})...

15
votes

Accepted

### The maximal subset of a finite field where the sum of any subset is non-zero

I could trace this question down to the paper of Erdős and Heilbronn "On the addition of residue classes mod $p$" (Acta Arith. 17 (1970), 227–229), where it is shown that for a prime $p$, if ...

14
votes

### Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?

You might be interested in Artin-Schreier theory.

14
votes

Accepted

### Finite field "contour" sum

What you call finite field contour sums are more usually called exponential sums. Like complex analytic contour integrals, they do not always (or even usually) have a nice exact formula. Instead, ...

14
votes

Accepted

### Algebraic dynamics in finite fields

There is a growing body of literature on dynamics of rational maps over finite fields. The following paper would seem to be relevant.
Ugolini, S., Graphs associated with the map $x\mapsto x+x^{-1}$ ...

14
votes

Accepted

### Can you use Chevalley‒Warning to prove existence of a solution?

Let $f_i \in \mathbb{F}_q[X_1,\dots,X_n]$ have degree at most $d$ for each $i \in [|1,r|]$, and assume that the affine scheme
$$
X = \operatorname{Spec} \mathbb F_q [x_1,\ldots,x_n]/(f_1, \ldots, f_r)
...

14
votes

### Roots of lacunary polynomials over a finite field

Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $\mathbb{F}_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^{...

14
votes

Accepted

### Does this degree 12 genus 1 curve have only one point over infinitely many finite fields?

The polynomial you wrote is the product of the four polynomials $x^3 - r y^3 - z^3$, where $r$ is a root of the polynomial $t^4 - t^3 + t^2 - t + 1$. I did not read your reference, but likely they ...

14
votes

### Cubic polynomials over finite fields whose roots are quadratic residues or non-residues

Yes, it does. Here is a stronger claim:
Theorem 1. Let $F$ be a field of characteristic $\neq2$. Let $c\in F$. Let
$r\in F$ be a nonzero square, and let $n_{1},n_{2}\in F$ be such that the
...

14
votes

Accepted

### Cubic polynomials over finite fields whose roots are quadratic residues or non-residues

EDIT: Following a clever observation of user44191 in the comments:
If $f(x)$ is a monic polynomial, and $c$ a number, then the polynomial $xf(x)^2+c$ has a similar property to your example (the case $...

14
votes

Accepted

### Existence of a polynomial $Q$ of degree $\geq (p-1)/4$ in $\mathbb F_p[x]$ such that $QQ'$ factorizes into distinct linear factors

Such polynomials always exist, examples are Dickson polynomials of the first kind (with parameter $1$). For a positive integer $n$ these degree $n$ polynomials $D_n$ are most conveniently defined ...

13
votes

Accepted

### An efficient isomorphism between finite fields

Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

finite-fields × 677nt.number-theory × 177

ag.algebraic-geometry × 155

co.combinatorics × 108

linear-algebra × 101

polynomials × 99

finite-groups × 53

gr.group-theory × 47

ac.commutative-algebra × 45

reference-request × 44

arithmetic-geometry × 39

rt.representation-theory × 34

coding-theory × 27

matrices × 26

elliptic-curves × 25

additive-combinatorics × 23

fields × 22

ra.rings-and-algebras × 21

finite-geometry × 20

galois-theory × 17

algebraic-groups × 16

abelian-varieties × 16

algebraic-curves × 15

pr.probability × 12

algorithms × 12