Abstract. We consider the set [Formula: see text] of [Formula: see text]-matrices with integer elements of size at most [Formula: see text] and obtain upper bounds on the number of matrices from [Formula: see text], for which the characteristic polynomial has a fixed discriminant [Formula: see text]. When [Formula: see text], this corresponds to counting matrices with a repeated eigenvalue and thus is related to counting nondiagonalizable matrices. For [Formula: see text], this problem seems not to have been studied previously, while for [Formula: see text], both our approach and the final result improve on those of A. J. Hetzel, J. S. Liew, and K. Morrison [ Amer. Math. Monthly, 114 (2007), pp. 491–499].

Abstract. Given a monic polynomial [Formula: see text] over a residue ring [Formula: see text] modulo an integer [Formula: see text] and a discrete interval [Formula: see text] of [Formula: see text] consecutive integers, considered as elements of [Formula: see text], we obtain a new upper bound for the additive energy of the set [Formula: see text], where [Formula: see text] denotes the image set [Formula: see text]. We give an application of our bounds to multiplicative character sums, improving a previous result of Shkredov and Shparlinski [ Proc. Steklov Math. Inst., 303 (2018) pp. 239–258].

Abstract We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n – 1) additions.

Abstract We give upper bounds on the power moments of the number of fixed points of a family of subset sum pseudorandom number generators, introduced by Rueppel (Analysis and design of stream ciphers, Springer-Verlag, Berlin, 1986).

We obtain upper bounds on the cardinality of Hilbert cubes in finite fields, which avoid large product sets and reciprocals of sum sets. In particular, our results replace recent estimates of N. Hegyvári and P. P. Pach [ J. Number Theory, 217 (2020), pp. 292--300], which appear to be void for all admissible parameters. Our approach is different from that of Hegyvári and Pach and is based on some well-known bounds of double character and exponential sums over arbitrary sets, due to A. A. Karatsuba [ Dokl. Akad. Nauk SSSR, 319 (1991), pp. 543--545] and N. G. Moshchevitin [ Mat. Sb., 198 (2007), pp. 95--116]), respectively.

We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n - 1) additions. Our result is based on bounds on the height of the annihilating polynomials in the Perron theorem and an effective form of the Lindemann-Weierstrass theorem which is due to Sert (1999).

We obtain new bounds of exponential sums modulo a prime $p$ with sparse polynomials $a_0x^{n_0} + \cdots + a_{\nu}x^{n_\nu}$. The bounds depend on various greatest common divisors of exponents $n_0, \ldots, n_\nu$ and their differences. In particular, two new bounds for binomials are obtained, improving previous results in broad ranges of parameters.

We prove, for a sufficiently small subset $\mathcal{A}$ of a prime residue field, an estimate on the number of solutions to the equation $(a_1-a_2)(a_3-a_4) = (a_5-a_6)(a_7-a_8)$ with all variables in $\mathcal{A}$. We then derive new bounds on trilinear exponential sums and on the total number of residues equaling the product of two differences of elements of $\mathcal{A}$. We also prove a refined estimate on the number of collinear triples in a Cartesian product of multiplicative subgroups and derive stronger bounds for trilinear sums with all variables in multiplicative subgroups.

Finding primitive roots in a finite field of p4elements of characteristic p remains to be a hard computational problem with the bottlenecks coming from both locating a small set of possible candidates and also factoring pn- 1 in order to test these candidates. Kopparty et al. (2016) have introduced a question of designing a fast algorithm to find primitive roots with a short advice from an oracle. Trivially, for an m-bit prime p, such a primitive root can be fully described by about mn bits of information received from an all-powerful oracle. Here, we have shown that one can achieve this in polynomial time and with about (1/2 + o(1))m + O(log n) bits of advice.

We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.

There is a well-known asymptotic formula, due to W. M. Schmidt [Duke Math. J., 35 (1968), pp. 327--339], for the number of full-rank integer lattices of index at most $V$ in ${\mathbb{Z}}^n$. This set of lattices $L$ can naturally be partitioned with respect to the factor group ${\mathbb{Z}}^n/L$. Accordingly, we count the number of full-rank integer lattices $L \subseteq {\mathbb{Z}}^n$ such that ${\mathbb{Z}}^n/L$ is cyclic and of order at most $V$, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is $(\zeta(6) \prod_{k=4}^n \zeta(k))^{-1} \approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.

We introduce and use some new arguments to improve upper bounds of Chung and of Lu, Wan, Wang, and Zhang on the diameter of some Cayley graphs constructed from polynomials over a finite field.

For a set M = {-μ, -μ + 1, ... , λ} \ {0} with nonnegative integers λ, μqmodulo an integer q > 1 is called a (λ, μ; q)-covering set if MS = {ms mod q : m ∈ M, s ∈ S} = Zq. Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ, μ; q)-covering set S, which is of the size q1+o(1)max{λ, μ}-1/2for almost all integers q ≥ 1 and optimal order of magnitude (that is up to a multiplicative constant) p max{λ, μ}-1if q = p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi that there is a (λ, μ; q)-covering set of size at most q1+o(1)max{λ, μ}-1/2for any integer q ≥ 1, however the proof of this bound is not constructive.

We say that a set ${\mathcal S}$ is additively decomposed into two sets ${\mathcal A}$ and ${\mathcal B}$ if ${\mathcal S} = \{a+b:a\in {\mathcal A}, b \in {\mathcal B}\}$. Here we study additive decompositions of multiplicative subgroups of finite fields. In particular, we give some improvements and generalizations of results of Dartyge and Sárközy on additive decompositions of quadratic residues and primitive roots modulo $p$. We use some new tools such as the Karatsuba bound of double character sums and some results from additive combinatorics.

We consider the problem of recovering a hidden element $s$ of a finite field $\mathbb{F}_q$ of $q$ elements from queries to an oracle that for a given $x \in \mathbb{F}_q$ returns $(x+s)^e$ for a given divisor $e \mid q-1$. We use some techniques from additive combinatorics and analytic number theory that lead to more efficient algorithms than the naive interpolation algorithm; for example, they use substantially fewer queries to the oracle.

Let E be an elliptic curve over a finite field Fqof q elements, with gcd(q,6)=1, given by an affine Weierstraß equation. We use x(P) to denote the x-component of a point P=(x(P),y(P)) ∈ E. We estimate character sums of the form Σn=1Nχ(x(nP)x(nQ)) and Σn1,⋯,nk=1Nψ(Σj=1kcjx((Πi=1jni)R)) on average over all Fqrational points P, Q, and R on E, where χ is a quadratic character, ψ is a nontrivial additive character in Fq, and (c1,..., ck) ∈ Fqkis a nonzero vector. These bounds confirm several recent conjectures of Jao, Jetchev, and Venkatesan, related to extracting random bits from various sequences of points on the elliptic curves.

We obtain some theoretical and experimental results concerning various properties (the number of fixed points, image distribution, cycle lengths) of the dynamical system naturally associated with Fermat quotients acting on the set $\{0,\dots,p-1\}$. In particular, we improve the lower bound of Vandiver [Bull. Amer. Math. Soc., 22 (1915), pp. 61–67] on the image size of Fermat quotients on the above set (from $p^{1/2}-1$ to $(1+o(1))p(\log p)^{-2}$). We also consider pseudorandom properties of Fermat quotients such as uniform distribution and linear complexity.

Motivated by a conjecture of Klapper [Finite Fields, Coding Theory, and Advances in Communications and Computing, Marcel Dekker, New York, 1993], we study the distribution of elements $\xi$ of a finite field $\mathbb{F}_{q^n}$ of $q^n$ elements under the action of the transformations $\xi\to(a\xi+b)/(c\xi+d)$ for matrices $\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)\in\mathrm{PGL_2(q)}$. We slightly improve a result of Niederreiter and Winterhof [Finite Fields Appl., 9 (2003), pp. 458–471] towards this conjecture. On the other hand, we also show that the original conjecture is false as stated.

Given a prime p and a positive integer n, we show that the shifted Kloosterman sums SigmaxisinFpnPsi(x + alphaxpn-2)=SigmaxisinF*pnPsi(x+alphax-1)+1, alphaisinF*pn where Psi is a nontrivial additive character of a finite field Fpn of pnelements, do not vanish if alpha belongs to a small subfield Fpm sube Fpn. This complements recent results of P. Charpin and G. Gong which in turn were motivated by some applications to bent functions.

For a Sidelnikov sequence of period p/sup m/-1, tight lower bounds are obtained on its linear complexity L over F/sub p/. In particular, these bounds imply that, uniformly over all p and m, L is close to its largest possible value p/sup m/-1.

For a system of polynomial equations over Q;p; we present an efficient construction of a single polynomial of quite small degree whose zero set over Q;p; coincides with the zero set over Q;p; of the original system. We also show that the polynomial has some other attractive features such as low additive and straight-line complexity.The proof is based on a link established here between the above problem and some recent number theoretic result about zeros of p-adic forms.

In 1989, F. R. K. Chung gave a construction for certain directed h-regular graphs of small diameter.Her construction is based on finite fields, and the upper bound on the diameter of these graphs is derived from bounds for certain very short character sums. Here we present two similar constructions that are based on properties of discrete logarithms and exponential functions in residue rings modulo a prime power. Accordingly, we use bounds for certain sums with additive and multiplicative characters to estimate the diameter of our graphs. We also give a third construction that avoids the use of bounds for exponential sums.

Maximal length feedback with carry shift register sequences have several remarkable statistical properties. Among them is the property that the arithmetic correlations between any two cyclically distinct decimations are precisely zero. It is open, however, whether all such pairs of decimations are indeed cyclically distinct. In this paper we show that the set of distinct decimations is large and, in some cases, all decimations are distinct.

We describe an authentication scheme whose security is based on the hardness of finding roots of systems of sparse polynomial equations in many variables and of high degree. One of the new ideas is the use of many keys. In one authentication session, a small amount of information about only one of them, chosen randomly, is released; this may be useful in other situations as well. Although the practicality of this scheme has still to be investigated, we believe that the new ideas described here may be of independent interest.

We solve two computational problems concerning plane algebraic curves over finite fields: generating a uniformly random point, and finding all points deterministically in amortized polynomial time (over a prime field, for nonexceptional curves).

We obtain lower bounds on the linear and nonlinear complexity profile of a general nonlinear pseudorandom number generator, of the inversive generator, and of a new nonlinear generator called quadratic exponential generator. The results are interesting for applications to cryptography and Monte Carlo methods.

We show that for several natural classes of “structured” matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime p is as hard as computing its exact value. Results of this kind are well known for arbitrary matrices. However the techniques used do not seem to apply to “structured” matrices. Our approach is based on recent advances in the hidden number problem introduced by Boneh and Venkatesan in 1996 combined with some bounds of exponential sums motivated by the Waring problem in finite fields.

We consider a polynomial analogue of the hidden number problem which has recently been introduced by Boneh and Venkatesan. Namely we consider the sparse polynomial approximation problem of recovering an unknown polynomial f(X) \in \F_p[X] with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \in \F_p selected uniformly at random. The case of a polynomial f(X) = α X corresponds to the hidden number problem. The above problem is related to the noisy polynomial interpolation problem and to the sparse polynomial interpolation problem which have recently been considered in the literature. Our results are based on a combination of some number theory tools such as bounds of exponential sums and the number of solutions of congruences with the lattice reduction technique.

Let g be a primitive root modulo a (n+1)-bit prime p. In this paper we prove the uniformity of distribution of the Diffie--Hellman triples (g x , g y , g xy ) as the exponents x and y run through the set of n-bit integers with precisely k nonzero bits in their bit representation provided that $k \ge 0.35 n$. Such "sparse" exponents are of interest because for these the computation of g x , g y , g xy is faster than for arbitrary x and y. In the latter case, that is, for arbitrary exponents, similar (albeit stronger) uniformity of distribution results have recently been obtained by R. Canetti, M. Larsen, D. Lieman, S. Konyagin [ Israel J. Math, 120 (2000), pp. 23--46], and the authors.

One of the long-standing open questions in the theory of parallel computation is the parallel complexity of the integer gcd and related problems, such as modular inversion. We present a lower bound $\Omega (\log n)$ for the parallel time on a concurrent-read exclusive-write parallel random access machine (CREW PRAM) computing the inverse modulo certain n-bit integers, including all such primes. For infinitely many moduli, our lower bound matches asymptotically the known upper bound. We obtain a similar lower bound for computing a specified bit in a large power of an integer. Our main tools are certain estimates for exponential sums in finite fields.

We obtain a lower bound on the linear complexity profile of the power generator of pseudo-random numbers modulo a Blum integer. A different method is also proposed to estimate the linear complexity profile of the Blum-Blum-Shub (1986) generator. In particular, these results imply that lattice reduction attacks on such generators are not feasible.

Recent work by Bernasconi, Damm and Shparlinski proved lower bounds on the circuit complexity of the square-free numbers, and raised as an open question if similar (or stronger) lower bounds could be proved for the set of prime numbers. In this short note, we answer this question affirmatively, by showing that the set of prime numbers (represented in the usual binary notation) is not contained in AC/sup 0/ [p] for any prime p. Similar lower bounds are presented for the set of square-free numbers, and for the problem of computing the greatest common divisor of two numbers.

This paper provides an algorithmic approach to some basic algebraic and combinatorial properties of algebraic curves over finite fields: the number of points on a curve or a projection, its number of absolutely irreducible components, and the property of being "exceptional."

We solve two computational problems concerning plane algebraic curves over finite fields: generating an (approximately) uniform random point, and finding all points deterministically in amortized polynomial time (over a prime field, for non-exceptional curves).

. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of estimating the size of the image of a univariate polynomial is a special case. For curves given by sparse polynomials, the counting problem is #P-complete via probabilistic parsimonious Turing reductions. 1. Introduction One of the most celebrated results in algebraic geometry is Weil's theorem on the number of points on algebraic curves over a finite field. In this paper, we address some computational problems related to this question. Our main results are: ffi A "computational Weil estimate" for projections of curves and images of polynomials, in Section 3. ffi #P-completeness of the exact counting problem for sparse curves, in Section 4. We consider a finite field F q with q elements, an algebraic closure K of F q , a polynomial f 2 F q [x; y] of degree n , the plane curve C = ff = 0g = f(a;...