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^...
user avatar
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 \...
user avatar
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$...
user avatar
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 $...
user avatar
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 $...
user avatar
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'...
user avatar
  • 41.1k
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 ...
user avatar
  • 85.1k
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 ...
user avatar
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 $...
user avatar
  • 7,982
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, ...
user avatar
  • 4,253
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, ...
user avatar
  • 85.1k
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 ...
user avatar
  • 114k
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|$. ...
user avatar
  • 10.3k
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 ...
user avatar
  • 114k
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\...
user avatar
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 ...
user avatar
  • 4,641
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 ...
user avatar
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 ...
user avatar
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})...
user avatar
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 ...
user avatar
  • 21.3k
14 votes

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

You might be interested in Artin-Schreier theory.
user avatar
  • 4,078
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, ...
user avatar
  • 114k
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}$ ...
user avatar
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) ...
user avatar
  • 7,119
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^{...
user avatar
  • 86.8k
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 ...
user avatar
  • 156
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 ...
user avatar
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 $...
user avatar
  • 114k
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 ...
user avatar
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" (...
user avatar

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