Search

We realize Frobenius conjugacy classes in Galois groups of certain $q$-polynomials over $\mathbb{F}_q(t)$ using specific degree 1 ideals. We combine this with methods from elementary linear algebra and group theory to realize transvections in some linear Galois groups. This enables the Galois group to be identified as a known classical group in several reasonably general cases., Comment: This updates and extends an earlier version, including a new title and abstract

We construct new stabilizer quantum error-correcting codes from generalized monomial-Cartesian codes. Our construction uses an explicitly defined twist vector, and we present formulas for the minimum distance and dimension. Generalized monomial-Cartesian codes arise from polynomials in $m$ variables. When $m=1$ our codes are MDS, and when $m=2$ and our lower bound for the minimum distance is $3$ the codes are at least Hermitian Almost MDS. For an infinite family of parameters when $m=2$ we prove that our codes beat the Gilbert-Varshamov bound. We also present many examples of our codes that are better than any known code in the literature.

Let $L(x)$ be any $q$-linearized polynomial with coefficients in $\mathbb{F}_q$, of degree $q^n$. We consider the Galois group of $L(x)+tx$ over $\mathbb{F}_q(t)$, where $t$ is transcendental over $\mathbb{F}_q$. We prove that when $n$ is a prime, the Galois group is always $GL(n,q)$, except when $L(x)=x^{q^n}$. Equivalently, we prove that the arithmetic monodromy group of $L(x)/x$ is $GL(n,q)$.

Let $F$ be a field of prime characteristic $p$ and let $q$ be a power of $p$. We assume that $F$ contains the finite field of order $q$. A $q$-polynomial $L$ over $F$ is an element of the polynomial ring $F[x]$ with the property that those powers of $x$ that occur as terms of $L$ with nonzero coefficient have exponent a power of $q$. If the exponent of the leading term of $L$ is $q^n$, we say that $L$ has $q$-degree $n$. We assume that the coefficient of the $x$ term of $L$ is nonzero. We investigate the Galois group $G$, say, of $L$ over $F$, under the assumption that $L(x)/x$ is irreducible in $F[x]$. It is well known that if $L$ has $q$-degree $n$, its roots are an $n$-dimensional vector space over the field of order $q$ and $G$ acts linearly on this space. Our main theorem is the following. We consider a monic $q$-polynomial $L$ whose $q$-degree is a prime, $r$, say, with $L(x)/x$ irreducible over $F$. Assuming that the coefficient of the $x$ term of $L$ is $(-1)^r$, we show that the Galois group of $L$ over $F$ must be the special linear group $SL(r,q)$ of degree $r$ over the field of order $q$ when $q>2$. We also prove a projective version for the projective special linear group $PSL(r,q)$, and we present the analysis when $q=2$.

We investigate some Galois groups of linearized polynomials over fields such as $\mathbb{F}_q(t)$. The space of roots of such a polynomial is a module for its Galois group. We present a realization of the symmetric powers of this module, as a subspace of the splitting field of another linearized polynomial.

Let $F$ be any field. We give a short and elementary proof that any finite subgroup $G$ of $PGL(2,F)$ occurs as a Galois group over the function field $F(x)$. We also develop a theory of descent to subfields of $F$. This enables us to realize the automorphism groups of finite subgroups of $PGL(2,F)$ as Galois groups., Comment: Material already known

For a subgroup of $PGL(2,q)$ we show how some irreducible polynomials over $\mathbb{F}_q$ arise from the field of invariant rational functions. The proofs rely on two actions of $PGL(2,F)$, one on the projective line over a field $F$ and the other on the rational function field $F(x)$. The invariant functions in $F(x)$ are used to show that regular patterns exist in the factorization of certain polynomials into irreducible polynomials. We use some results about group actions and the orbit polynomial, whose proofs are included. An unusual connection to the conjugacy classes of $PGL(2,q)$ is shown. At the end of the paper we present an alternative approach, using Lang's theorem on algebraic groups., Comment: New section added

We present some results about the number of rational points on a certain family of curves defined over a finite field. In a small number of cases the curves have more rational points than expected. Fibonacci numbers make an appearance, as do cyclotomic polynomials.

Lattice sieving in two or more dimensions has proven to be an indispensable practical aid in integer factorization and discrete log computations involving the number field sieve. The main contribution of this article is to show that a different method of lattice enumeration in three dimensions will provide a significant speedup. We use the successive minima and shortest vectors of the lattice instead of transition vectors to iterate through lattice points. We showcase the new method by a record computation in a 133-bit subgroup of $\mathbb{F}_{p^6}$, with $p^6$ having 423 bits. Our overall timing nearly $3$ times faster than the previous record of a 132-bit subgroup in a 422-bit field. The approach generalizes to dimensions 4 or more, overcoming a key obstruction to the implementation of the tower number field sieve.

We present new quantum codes with good parameters which are constructed from self-orthogonal algebraic geometry codes. Our method permits a wide class of curves to be used in the formation of these codes, which greatly extends the class of a previous paper due to Munuera, Ten\'orio and Torres. These results demonstrate that there is a lot more scope for constructing self-orthogonal AG codes than was previously known.

Linearized polynomials over finite fields have been much studied over the last several decades. Recently there has been a renewed interest in linearized polynomials because of new connections to coding theory and finite geometry. We consider the problem of calculating the rank or nullity of a linearized polynomial $L(x)=\sum_{i=0}^{d}a_i x^{q^i}$ (where $a_i\in \mathbb{F}_{q^n}$) from the coefficients $a_i$. The rank and nullity of $L(x)$ are the rank and nullity of the associated $\mathbb{F}_q$-linear map $\mathbb{F}_{q^n} \longrightarrow \mathbb{F}_{q^n}$. McGuire and Sheekey defined a $d\times d$ matrix $A_L$ with the property that $$\mbox{nullity} (L)=\mbox{nullity} (A_L -I).$$ We present some consequences of this result for some trinomials that split completely, i.e., trinomials $L(x)=x^{q^d}-bx^q-ax$ that have nullity $d$. We give a full characterization of these trinomials for $n\le d^2-d+1$.

A fundamental problem in the theory of linearized and projective polynomials over finite fields is to characterize the number of roots in the coefficient field directly from the coefficients. We prove results of this type, of a recursive nature. These results follow from our main theorem which characterizes the number of roots using the rank of a matrix that is smaller than the Dickson matrix.

In general, the L-polynomial of a curve of genus $g$ is determined by $g$ coefficients. We show that the L-polynomial of a supersingular curve of genus $g$ is determined by fewer than $g$ coefficients.

In this paper we consider the curves $C_k^{(p,a)} : y^p-y=x^{p^k+1}+ax$ defined over $\mathbb F_p$ and give a positive answer to a conjecture about a divisibility condition on $L$-polynomials of the curves $C_k^{(p,a)}$. Our proof involves finding an exact formula for the number of $\mathbb F_{p^n}$-rational points on $C_k^{(p,a)}$ for all $n$, and uses a result we proved elsewhere about the number of rational points on supersingular curves.

We consider the question of when the L-polynomial of one curve divides the L-polynomial of another curve. A theorem of Tate gives an answer in terms of jacobians. We consider the question in terms of the curves. The last author gave an invited talk at the 12th International Conference on Finite Fields and Their Applications on this topic, and stated two conjectures. In this article we prove one of those conjectures.

The XL algorithm is an algorithm for solving overdetermined systems of multivariate polynomial equations, which was initially introduced for quadratic equations. However, the algorithm works for polynomials of any degree, and in this paper we will focus on the performance of XL for polynomials of degree $\geq3$, where the optimal termination value of the parameter $D$ is still unknown. We prove that the XL algorithm terminates at a certain value of $D$ in the case that the number of equations exceeds the number of variables by 1 or 2. We also give strong evidence that this value is best possible, and we show that this value is smaller than the degree of regularity. Part of our analysis requires proving that ordinary multinomials are strongly unimodal, and this result may be of independent interest.

We consider the representation of primes as a sum of a prime and twice a triangular number. We prove that a subset of the primes having density 1 is expressible in this form. We conjecture that every odd prime number is expressible as a sum of a twin prime and twice a triangular number. We show that this conjecture implies the existence of infinitely many twin primes.

In this paper we give a different proof of Kuz'min's result on the number of irreducible polynomials with the first two coefficients fixed. Our technique is to relate the question to the number of points on a curve, and to calculate the L-polynomial of the curve., Comment: arXiv admin note: text overlap with arXiv:1605.07229

We provide first slope estimates of the Newton polygon of generalized Artin-Schreier curves, which are proved using the action of Frobenius and Verschiebung on cohomology. We provide a number of applications such as an improved Hasse-Weil bound for this class of curves.

For any positive integers $n\geq 3, r\geq 1$ we present formulae for the number of irreducible polynomials of degree $n$ over the finite field $\mathbb{F}_{2^r}$ where the coefficients of $x^{n-1}$, $x^{n-2}$ and $x^{n-3}$ are zero. Our proofs involve counting the number of points on certain algebraic curves over finite fields, a technique which arose from Fourier-analysing the known formulae for the $\mathbb{F}_2$ base field cases, reverse-engineering an economical new proof and then extending it. This approach gives rise to fibre products of supersingular curves and makes explicit why the formulae have period $24$ in $n$., Comment: 29 pages. Final version. To appear in Finite Fields and Their Applications

We consider the issue of when the L-polynomial of one curve over $\F_q$ divides the L-polynomial of another curve. We prove a theorem which shows that divisibility follows from a hypothesis that two curves have the same number of points over infinitely many extensions of a certain type, and one other assumption. We also present an application to a family of curves arising from a conjecture about exponential sums. We make our own conjecture about L-polynomials, and prove that this is equivalent to the exponential sums conjecture., Comment: 20 pages

We will present many strong partial results towards a classification of exceptional planar/PN monomial functions on finite fields. The techniques we use are the Weil bound, Bezout's theorem, and Bertini's theorem.

This article is about the mathematics of ringing the changes. We describe the mathematics which arises from a real-world activity, that of ringing the changes on bells. We present Rankin's solution of one of the famous old problems in the subject. This article was written in 2003.

The sudoku minimum number of clues problem is the following question: what is the smallest number of clues that a sudoku puzzle can have? For several years it had been conjectured that the answer is 17. We have performed an exhaustive computer search for 16-clue sudoku puzzles, and did not find any, thus proving that the answer is indeed 17. In this article we describe our method and the actual search. As a part of this project we developed a novel way for enumerating hitting sets. The hitting set problem is computationally hard; it is one of Karp's 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today's supercomputer speeds. To make an exhaustive search possible, we designed an algorithm that allowed us to efficiently enumerate hitting sets of a suitable size., Comment: 43 pages

In this article, we give a complete description of the characteristic polynomials of supersingular abelian varieties over finite fields. We list them for the dimensions upto 7.

Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main result is that a quadratic function is CCZ-equivalent to an APN Gold function if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family of APN functions that exist on finite fields of order 2^n where n = 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code associated with such a function., Comment: 13 pg

We prove two results on Kloosterman sums over finite fields, using Stickelberger's theorem and the Gross-Koblitz formula. The first result concerns the minimal polynomial over Q of a Kloosterman sum, and the second result gives a characterisation of ternary Kloosterman sums modulo 27.

In this article a technique for constructing $p$-ary bent functions from near-bent functions is presented. Two classes of quadratic $p$-ary functions are shown to be near-bent. Applying the construction of bent functions to these classes of near-bent functions yields classes of non-quadratic bent functions. We show that one construction in even dimension yields weakly regular bent functions. For other constructions, we obtain both weakly regular and non-weakly regular bent functions. In particular we present the first known infinite class of non-weakly regular bent functions.

In this article, we derive the list of the characteristic polynomials of the Frobenius endomorphism of simple supersingular abelian varieties of dimension $1,~2,~3,~4,~5,~6,~7$ over $\mathbb{F}_q$ where $q=p^n$, $n$ odd.

The existence of certain monomial hyperovals $D(x^k)$ in the finite Desarguesian projective plane $PG(2,q)$, $q$ even, is related to the existence of points on certain projective plane curves $g_k(x,y,z)$. Segre showed that some values of $k$ ($k=6$ and $2^i$) give rise to hyperovals in $PG(2,q)$ for infinitely many $q$. Segre and Bartocci conjectured that these are the only values of $k$ with this property. We prove this conjecture through the absolute irreducibility of the curves $g_k$.

We give results characterising ternary Kloosterman sums modulo 9 and 27. This leads to a complete characterisation of values that ternary Kloosterman sums assume modulo 18 and 54. The proofs uses Stickelberger's theorem, the Gross-Koblitz formula and Fourier analysis.

Let $\mathcal{K}(a)$ denote the Kloosterman sum on the finite field of order $2^n$. We give a simple characterization of $\mathcal{K}(a)$ modulo 16, in terms of the trace of $a$ and one other function. We also give a characterization of $\mathcal{K}(a)$ modulo 64 in terms of a different function, which we call the lifted trace. Our proofs use Fourier analysis, Stickelberger's theorem and the Gross-Koblitz formula., Comment: Minor error corrected in final section

We study the intersection of two particular Fermat hypersurfaces in $\mathbb{P}^3$ over a finite field. Using the Kani-Rosen decomposition we study arithmetic properties of this curve in terms of its quotients. Explicit computation of the quotients is done using a Gr\"obner basis algorithm. We also study the $p$-rank, zeta function, and number of rational points, of the modulo $p$ reduction of the curve. We show that the Jacobian of the genus 2 quotient is $(4,4)$-split.

One of the big questions in the area of curves over finite fields concerns the distribution of the numbers of points: Which numbers occur as the number of points on a curve of genus $g$? The same question can be asked of various subclasses of curves. In this article we classify the possibilities for the number of points on genus 4 hyperelliptic supersingular curves over finite fields of order $2^n$, $n$ odd.

We consider exceptional APN functions on ${\bf F}_{2^m}$, which by definition are functions that are not APN on infinitely many extensions of ${\bf F}_{2^m}$. Our main result is that polynomial functions of odd degree are not exceptional, provided the degree is not a Gold member ($2^k+1$) or a Kasami-Welch number ($4^k-2^k+1$). We also have partial results on functions of even degree, and functions that have degree $2^k+1$.

This paper presents two kinds of division polynomials for twisted Edwards curves. Their chief property is that they characterise the $n$-torsion points of a given twisted Edwards curve. We also present results concerning the coefficients of these polynomials, which may aid computation.

In this paper we derive a recursion for the zeta function of each function field in the second Garcia-Stichtenoth tower when $q=2$. We obtain our recursion by applying a theorem of Kani and Rosen that gives information about the decomposition of the Jacobians. This enables us to compute the zeta functions explicitly of the first six function fields., Comment: 14 pages

We prove a conjecture that classifies exceptional numbers. This conjecture arises in two different ways, from cryptography and from coding theory. An odd integer $t\geq 3$ is said to be exceptional if $f(x)=x^t$ is APN (Almost Perfect Nonlinear) over $\mathbb{F}_{2^n}$ for infinitely many values of $n$. Equivalently, $t$ is exceptional if the binary cyclic code of length $2^n-1$ with two zeros $\omega, \omega^t$ has minimum distance 5 for infinitely many values of $n$. The conjecture we prove states that every exceptional number has the form $2^i+1$ or $4^i-2^i+1$.

We construct Weil numbers corresponding to genus-2 curves with $p$-rank 1 over the finite field $\F_{p^2}$ of $p^2$ elements. The corresponding curves can be constructed using explicit CM constructions. In one of our algorithms, the group of $\F_{p^2}$-valued points of the Jacobian has prime order, while another allows for a prescribed embedding degree with respect to a subgroup of prescribed order. The curves are defined over $\F_{p^2}$ out of necessity: we show that curves of $p$-rank 1 over $\F_p$ for large $p$ cannot be efficiently constructed using explicit CM constructions., Comment: 19 pages

This paper presents division polynomials for twisted Edwards curves. Their chief property is that they characterise the $n$-torsion points of a given twisted Edwards curve. We also present results concerning the coefficients of these polynomials, which may aid computation., Comment: 18 pages, added justification for unique representations of general rational functions in function field of twisted Edwards curve

We present two infinite families of APN functions where the degree of the field is divisible by 3 but not 9. Our families contain two already known families as special cases. We also discuss the inequivalence proof (by computation) which shows that these functions are new., Comment: 12 pages, submitted to Cryptography and Communications