Search

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$.

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 ≥3, 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.

This brief introduces a new method to compute in parallel the roots of a polynomial locator of degree four in a Reed-Solomon decoder. The novelty of this brief is the introduction of an algorithm that transforms the polynomial locator obtained with the Peterson-Gorenstein-Zierler’s algorithm into an equivalent one that allows a direct search for the four roots that indicate the location of the symbols in error. This new solution improves a previous approach proposed in the literature for a quadruple-error-correction decoder (QEC) that requires a cubic aid equation. This previous solution does not work in the cases in which the cubic aid does not have a solution. In contrast, the proposal of this brief works in 100% of cases (with $t\leq 4$ ) as it solves an equivalent polynomial. This new algorithm allows two different implementations: a fully parallel architecture which provides an extremely low latency at an extra area cost, and a fully serial architecture with less area, but a higher latency.

Lattice sieving in two 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 sieving in three dimensions will provide a significant speedup in medium characteristic. Our method is to 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 F p 6 ${{\mathbb{F}}_{{{p}^{6}}}}$ , with p 6 having 423 bits. Our overall timing is 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 one key obstruction to the implementation of the tower number field sieve.

In this paper we consider the curves C k ( p , a ) : y p − y = x p k + 1 + a x defined over 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 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.

Throughout this paper we let p be a prime number, let \(q=p^r\) and let \(\mathbb {F}_{q^n}\) denote a finite field with \(q^n\) elements, where n is a positive integer.

[EN] 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. These results demonstrate that there is a lot more scope for constructing self-orthogonal AG codes than was previously known., G. McGuire was partially supported by Science Foundation Ireland Grant 13/IA/1914. The remainder authors were partially supported by the Spanish Government and the EU funding program FEDER, Grants MTM2015-65764-C3-2-P and PGC2018-096446-B-C22. F. Hernando and J. J. Moyano-Fernandez are also partially supported by Universitat Jaume I, Grant UJI-B2018-10.

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

We present JKL-ECM, an implementation of the elliptic curve method of integer factorization which uses certain twisted Hessian curves in a family studied by Jeon, Kim and Lee. This implementation takes advantage of torsion subgroup injection for families of elliptic curves over a quartic number field, in addition to the ‘small parameter’ speedup. We produced thousands of curves with torsion$\mathbb{Z}/6\mathbb{Z}\oplus \mathbb{Z}/6\mathbb{Z}$and small parameters in twisted Hessian form, which admit curve arithmetic that is ‘almost’ as fast as that of twisted Edwards form. This allows JKL-ECM to compete with GMP-ECM for finding large prime factors. Also, JKL-ECM, based on GMP, accepts integers of arbitrary size. We classify the torsion subgroups of Hessian curves over$\mathbb{Q}$and further examine torsion properties of the curves described by Jeon, Kim and Lee. In addition, the high-performance curves with torsion$\mathbb{Z}/2\mathbb{Z}\oplus \mathbb{Z}/8\mathbb{Z}$of Bernsteinet al. are completely recovered by the$\mathbb{Z}/4\mathbb{Z}\oplus \mathbb{Z}/8\mathbb{Z}$family of Jeon, Kim and Lee, and hundreds more curves are produced besides, all with small parameters and base points.

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.

Supersingular elliptic curves have played an important role in the development of elliptic curve crytography. Scott Vanstone introduced the first author to elliptic curve cryptography, a subject that continues to be a rich source of interesting problems, results and applications. One important fact about supersingular elliptic curves is that the number of rational points is tightly constrained to a small number of possible values. In this paper we present some similar results for curves of higher genus. We also present an application to the problem of determining abelian varieties that occur as jacobians.

In this paper we give a linearized generalization of a theorem by Carlitz and an odd prime extension of a theorem by Payne concerning permutation polynomials over finite fields. We give an application of our result which classifies the permutation polynomials of the form x^-^1+L(x) in odd characteristic, where L(x) is a linearized polynomial.

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 to enumerate 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.

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.

Text We prove two congruence results concerning Kloosterman sums over finite fields. The first result concerns the coefficients of the characteristic polynomial over Q of a Kloosterman sum, and the second result gives a characterisation of ternary Kloosterman sums modulo 27. We use methods from algebraic number theory such as Stickelbergerʼs theorem and the Gross–Koblitz formula, as well as Fourier analysis. Video For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=VJcB6W_PQ0s .

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

Kloosterman sums are exponential sums on finite fields that have important applications in cryptography and coding theory. We use Stickelberger's theorem and the Gross-Koblitz formula to determine the value of the binary Kloosterman sum at a modulo 64, modulo 128, and modulo 256 in terms of coefficients of the characteristic polynomial of a.

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 present recursions for the division polynomials, which differ in their flavour. We prove a uniqueness form for elements of the function field of an Edwards curve. We also present results concerning the coefficients of these polynomials, which may aid computation.

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

Let K be a field and let M m × n ( K ) denote the space of m × n matrices over K . We investigate properties of a subspace M of M m × n ( K ) of dimension n ( m - r + 1 ) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M m × n ( K ) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.

We consider the weight distribution of the binary cyclic code of length 2^n-1 with two zeros @a^a,@a^b. Our proof gives information in terms of the zeta function of an associated variety. We carry out an explicit determination of the weight distribution in two cases, for the cyclic codes with zeros @a^3,@a^5 and @a,@a^1^1. These are the smallest cases of two infinite families where finding the weight distribution is an open problem. Finally, an interesting application of our methods is that we can prove that these two codes have the same weight distribution for all odd n.

We study PN and APN functions over the integers modulo n. We give some construction techniques based on Costas arrays, which allow us to construct APN permutations on Z"p"-"1 where p is a prime. Although PN permutations do not exist, one set of our functions is very close to being a set of PN permutations.

We give a construction of cocyclic Butson–Hadamard matrices from bilinear forms over finite Frobenius rings, which generalizes previous constructions. We then prove a classification result, showing that the resulting matrices depend only on the additive group of the underlying module of the form.

The authors give a construction of multiblock space-time block codes from cyclic division algebras with a given nth root of unity as the nonnorm element. The construction uses local class field theory. Multiblock codes with M blocks can achieve an M-fold increase in diversity.

We introduce two new infinite families of APN functions, one on fields of order 22k for k not divisible by 2, and the other on fields of order 23k for k not divisible by 3. The polynomials in the first family have between three and k+2 terms, the second family's polynomials have three terms.

We present a general criterion for near bent functions to be bent on a hyperplane. Let n=3k+/-1 be odd and let d=4^k-2^k+1. We show that the Kasami-Welch function Tr(x^d) is a bent function when restricted to the hyperplane of trace 0 elements in F"2"^"n.

In the early 1980s Dan Hughes wrote two papers on semi-symmetric 3-designs, which are closely related to quasi-3 designs. In 1973 Peter Cameron asked whether the dual design of any quasi-3 design must also be quasi-3. In this article, we answer that question. We give some general constructions of quasi-3 designs which enable us to give the answer. The answer is no.

We use elementary facts about quadratic forms in characteristic 2 to evaluate the sign of some Walsh transforms in terms of a Jacobi symbol. These results are applied to the Walsh transforms of the Gold and Kasami-Welch functions. We prove that the Gold functions yield bent functions when restricted to certain hyperplanes. We also use the sign information to determine the dual bent function.

We study the Plotkin bound for codes over a finite Frobenius ring R equipped with the homogeneous weight. We show that for codes meeting the Plotkin bound, the distribution on R induced by projection onto a coordinate has an interesting property. We present several constructions of codes meeting the Plotkin bound and of Plotkin-optimal codes. We also investigate the relationship between Butson–Hadamard matrices and codes over R meeting the Plotkin bound.

Using Hadamard matrices and mutually orthogonal Latin squares, we construct two new quasi-symmetric designs, with parameters 2 ? (66,30,29) and 2 ? (78,36,30). These are the first examples of quasi-symmetric designs with these parameters. The parameters belong to the families 2 ? (2u 2 ? u,u 2 ? u,u 2 ? u ? 1) and 2 ? (2u 2 + u,u 2,u 2 ? u), which are related to Hadamard parameters. The designs correspond to new codes meeting the Grey---Rankin bound.

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

A theorem of Bannai and Sawano shows that certain four-weight spin models exist if and only if certain quasi-3 designs exist. We verify that the known quasi-3 designs, other than SDP designs, do not give rise to four-weight spin models.