Using the relation between the problem of counting irreducible polynomials over finite fields with some prescribed coefficients to the problem of counting rational points on curves over finite fields whose function fields are subfields of cyclotomic function fields, we count the number of generators of finite fields with powers of trace zero up to some point, answering a question of Z. Reichstein.
For a morphism of a variety X over a number field K, we consider local conditions and a "Brauer-Manin" condition, defined by Hsia and Silverman, for the orbit of a point P in X(K) to be disjoint from a subvariety V of X. We provide evidence that the dynamical Brauer-Manin condition is sufficient to explain the lack of points in the intersection of the orbit of P and V. This evidence stems from a probabilistic argument as well as unconditional results in the case of étale maps.
We give an explicit description of the F_{qi}-rational points on the Fermat curve u^{q-1}+v^{q-1}+w^{q-1}=0, for i=1,2,3. As a consequence, we observe that for any such point (u,v,w), the product uvw is a cube in F_{qi}. We also describe the F_{q2}-rational points on the Fermat surface u^{q-1}+v^{q-1}+w^{q-1}+x^{q-1}=0.
We study a new obstruction to the existence of integral and rational points for algebraic varieties over function fields, the differential descent obstruction. We prove that that is the only obstruction to the existence of integral points in affine varieties in characteristic zero and also, in most cases, for rational points on curves in arbitrary characteristic.
This paper has errors We study the section conjecture of anabelian geometry and the sufficiency of the finite descent obstruction to the Hasse principle for the moduli spaces of principally polarized abelian varieties and of curves over number fields. For the former we show that both the section conjecture and the finite descent obstruction fail in a very controlled way. For the latter, we prove some partial results that indicate that the finite descent obstruction suffices. We also show how this sufficiency implies the same for all hyperbolic curves.
We give examples of sequences of smooth non-isotrivial curves for every genus at least two, defined over a rational function field of positive characteristic, such that the (finite) number of rational points of the curves in the sequence cannot be uniformly bounded.
We prove that the Brauer-Manin obstruction is the only obstruction to the existence of integral points on affine varieties over global fields of positive characteristic p. More precisely, we show that the only obstructions come from etale covers of exponent p or, alternatively, from flat covers coming from torsors under connected group schemes of exponent p.
We prove that a form of finite Galois descent obstruction is the only obstruction to the existence of integral points on integral models of twists of modular curves over function fields.
We prove estimates on character sums on the subset of points of an elliptic curve over F_{Q} with x-coordinate of the form α + t where t varies in F_{q} and α is fixed such that F_{Q} = F_{q}(α). We deduce that, for a suitable choice of α this subset has a point of maximal order in E(F_{Q}). This provides a deterministic algorithm for finding a point of maximal order which for a very wide class of finite fields is faster than other available algorithms.
We present a technique based on bounds of character sums to prove the indifferentiability of hash function constructions based on essentially any deterministic encoding to elliptic curves or curves of higher genus, such as the algorithms by Shallue, van de Woestijne and Ulas, or the Icart-like encodings recently presented by Kammerer, Lercier and Renault. In particular, we get the first constructions of well-behaved hash functions to Jacobians of hyperelliptic curves. Our technique also provides more precise estimates on the statistical behavior of those deterministic encodings and the hash function constructions based on them. Additionally, we can derive pseudorandomness results for partial bit patterns of such encodings.
Let f be a polynomial of degree at least 2 with coefficients in a number field K, let x be a sufficiently general element of K, and let z be a root of f. We give precise conditions under which Newton iteration, started at the point x, converges v-adically to the root z for infinitely many places v of K. As a corollary we show that if f is irreducible over K of degree at least 3, then Newton iteration converges v-adically to any given root of f for infinitely many places v. We also conjecture that the set of places for which Newton iteration diverges has full density and give some heuristic and numerical evidence.
We prove a non-existence result for special divisors of large dimension on curves over finite fields with many points. We also give a family of examples where such divisors exist under less stringent hypotheses.
We prove that a form of finite Galois descent obstruction is the only obstruction to the existence of S integral points on integral models of twists of modular curves over Q, for any finite set of primes S. We deduce this from an existence theorem for elliptic curves over Q satisfying certain local conditions.
We discuss the question of whether the Brauer-Manin obstruction is the only obstruction to the Hasse principle for integral points on affine hyperbolic curves. In the case of rational curves we conjecture a positive answer, we prove that this conjecture can be given several equivalent formulations and relate it to an old conjecture of Skolem. We show that for elliptic curves minus one point the question has a negative answer.
We study the hash function from a finite field into an elliptic curve over that field which has recently been introduced by T. Icart. In particular we slightly adjust and prove the asymptotic formula conjectured by T. Icart for the image size of this function.
We discuss the problem of constructing elements of multiplicative high order in finite fields of large degree over their prime field. We prove that the values on points of order small with respect to their degree of rational functions on an elliptic curve have high order. We discuss several special cases, including an old construction of Wiedemann, giving the first non-trivial estimate for the order of the elements in this construction.
Let K be a number field or a one-dimensional function field, we consider a rational map of degree at least two defined over K, and a point P in P^{1}(K) with infinite orbit under the action of the map, and Z a finite set of points. We prove a local-global criterion for the intersection of the orbit of P and the finite set Z. This is a special case of a dynamical Brauer-Manin criterion suggested by Hsia and Silverman.
Akiyama and Goto have proposed a cryptosystem based on rational points on curves over function fields (stated in the equivalent form of sections of fibrations on surfaces). It is easy to construct a curve passing through a few given points, but finding the points, given only the curve, is hard. We show how to break their original cryptosystem by using algebraic points instead of rational points and discuss possibilities for changing their original system to create a secure one.
We prove that the Hasse principle for conics over function fields is a simple consequence of a provable case of the Artin-Tate conjecture for surfaces over finite fields.
We discuss the problem of constructing elements of multiplicative high order in finite fields of large degree over their prime field. We prove that for points on a plane curve, one of the coordinates has to have high order. We also discuss a conjecture of Poonen for subvarieties of semiabelian varieties for which our result is a weak special case. Finally, we look at some special cases where we obtain sharper bounds.
We obtain a lower bound on the multiplicative order of Gauss periods which generate normal bases over finite fields. This bound improves the previous bound of J. von zur Gathen and I. E. Shparlinski.
We view an algebraic curve over Q as providing a one-parameter family of number fields and obtain bounds for the average value of some standard prime ideal counting functions over these families which are better than averaging the standard estimates for these functions.
For a prime p and an absolutely irreducible modulo p polynomial f(U,V) in Z[U,V] we obtain an asymptotic formulas for the number of solutions to the congruence f(x,y) = a mod p in positive integers x < X, y < Y, with the additional condition gcd(x,y)=1. Such solutions have a natural interpretation as solutions which are visible from the origin. These formulas are derived on average over a for a fixed prime p, and also on average over p for a fixed integer a.
We prove that for a large class of subvarieties of abelian varieties over global function fields, the Brauer-Manin condition on adelic points cuts out exactly the rational points. This result is obtained from more general results concerning the intersection of the adelic points of a subvariety with the adelic closure of the group of rational points of the abelian variety.
We discuss some applications of the theory of algebraic curves to the study of S-boxes in symmetric cryptography.
We study error-correcting codes constructed from projective surfaces over finite fields using the generalized Goppa construction. We obtain bounds for the minimal distance of these codes by understanding how the zero sets of functions on a surface decompose into irreducible components. We also present a decoding algorithm for these codes based on the Luby-Mitzenmacher algorithm for LDPC codes.
For an elliptic curve over a function field and a subgroup of rank at least six, we prove that the reduction of the subgroup modulo a place v covers the group of points of the curve modulo v for a positive proportion of v's.
For infinitely many primes p, the minimal distance of the binary quadratic residue code of length p is O(p/log log p).
We present an algorithm to compute r-th roots in a finite field with q^{m} elements with complexity O((log m + rlog q)m^{2}(log q)^{2}) for certain choices of m and q.
In this note we give a lower bound for the minimal distance of the double circulant binary quadratic residue codes.
We describe an algorithm that improves on the standard algorithm for computing the minimal distance of cyclic codes.
We discuss a class of binary cyclic codes and their dual codes. The minimum distance is determined using algebraic geometry, and an application of Weil's theorem. We relate the weights appearing in the dual codes to the number of rational points on a family of genus 2 curves over a finite field.
We construct (k,n)-arcs in PG(2,q) with k approximately q^{2}/d and n approximately q/d for each divisor d of q-1.
The main result of this paper is that, in a precise sense, a positive proportion of all hypersurfaces in P^{n} of degree d defined over Q are everywhere locally solvable, provided that n,d > 1 and (n,d) is not (2,2). This result is motivated by a conjecture discussed in detail in the paper about the proportion of hypersurfaces as above that are globally solvable, i.e., have a rational point.