Source author record

Igor Shparlinski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT math.CO math.DS Computational Complexity Cryptography and Security Data Structures and Algorithms math.AG math.FA

Catalog footprint

Research overview

19works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An effective local-global principle for algebraic varieties and the sum product problem in finite fields

We use recent results about linking the number of zeros on algebraic varieties over $\mathbb{C}$ , defined by polynomials with integer coefficients, and on their reductions modulo sufficiently large primes to study congruences with products and reciprocals of linear forms. This allows us to make some progress towards a question of B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev and I. D. Shkredov (2019) on an extreme case of the Erdős-Szemerédi conjecture in finite fields.

preprint2021arXiv

Order of torsion for reduction of linearly independent points for a family of Drinfeld modules

Let $q$ be a power of the prime number $p$ , let $K={\mathbb F}_q(t)$ , and let $r\ge 2$ be an integer. For points ${\mathbf a}, {\mathbf b}\in K$ which are $\mathbb{F}_q$ -linearly independent, we show that there exist positive constants $N_0$ and $c_0$ such that for each integer $\ell\ge N_0$ and for each generator $τ$ of ${\mathbb F}_{q^\ell}/{\mathbb F}_q$ , we have that for all except $N_0$ values $λ\in{\overline{\mathbb{F}_q}}$ , the corresponding specializations ${\mathbf a}, {\mathbf b}(τ)$ and ${\mathbf b}(τ)$ cannot have orders of degrees less than $c_0\log\log\ell$ as torsion points for the Drinfeld module $Φ^{(τ,λ)}:\mathbb{F}_q[T] {\longrightarrow} {\mathrm{End}}_{\overline{\mathbb{F}_q}}({\mathbb G}_a)$ (where ${\mathbb G}_a$ is the additive group scheme), given by $Φ^{(τ,λ)}_T(x)=τx+λx^q + x^{q^r}$ .

preprint2016arXiv

Bounds on short character sums and L-functions for characters with a smooth modulus

We combine a classical idea of Postnikov (1956) with the method of Korobov (1974) for estimating double Weyl sums, deriving new bounds on short character sums when the modulus $q$ has a small core $\prod_{p\mid q}p$ . Using this estimate, we improve certain bounds of Gallagher (1972) and Iwaniec (1974) for the corresponding $L$ -functions. In turn, this allows us to improve the error term in the asymptotic formula for primes in short arithmetic progressions modulo a power of a fixed prime. As yet another application of our bounds, we substantially extend the region free of Siegel zeros.

preprint2015arXiv

Polynomial Interpolation and Identity Testing from High Powers over Finite Fields

We consider the problem of recovering (that is, interpolating) and identity testing of a "hidden" monic polynomial $f$ , given an oracle access to $f(x)^e$ for $x\in{\mathbb F_q}$ (extension fields access is not permitted). The naive interpolation algorithm needs $O(e\, \mathrm{deg}\, f)$ queries and thus requires $e\, \mathrm{deg}\, f<q$ . We design algorithms that are asymptotically better in certain cases; requiring only $e^{o(1)}$ queries to the oracle. In the randomized (and quantum) setting, we give a substantially better interpolation algorithm, that requires only $O(\mathrm{deg}\, f \log q)$ queries. Such results have been known before only for the special case of a linear $f$ , called the hidden shifted power problem. We use techniques from algebra, such as effective versions of Hilbert's Nullstellensatz, and analytic number theory, such as results on the distribution of rational functions in subgroups and character sum estimates.

preprint2014arXiv

Character Sums and Deterministic Polynomial Root Finding in Finite Fields

We obtain a new bound of certain double multiplicative character sums. We use this bound together with some other previously obtained results to obtain new algorithms for finding roots of polynomials modulo a prime $p$ .

preprint2014arXiv

Congruences with intervals and subgroups modulo a prime

We obtain new results about the representation of almost all residues modulo a prime $p$ by a product of a small integer and also an element of small multiplicative subgroup of $({\mathbb Z}/p{\mathbb Z})^*$ . These results are based on some ideas, and their modifications, of a recent work of J. Cilleruelo and M. Z. Garaev (2014),

preprint2014arXiv

On the Fixed Points of the Map x -> x^x Modulo a Prime

In this paper, we show that for almost all primes p there is an integer solution x in [2,p-1] to the congruence x^x == x mod p. The solutions can be interpretated as fixed points of the map x -> x^x mod p, and we study numerically and discuss some unexpected properties of the dynamical system associated with this map.

preprint2014arXiv

Polynomial Values in Subfields and Affine Subspaces of Finite Fields

For an integer $r$ , a prime power $q$ , and a polynomial $f$ over a finite field ${\mathbb F}_{q^r}$ of $q^r$ elements, we obtain an upper bound on the frequency of elements in an orbit generated by iterations of $f$ which fall in a proper subfield of ${\mathbb F}_{q^r}$ . We also obtain similar results for elements in affine subspaces of ${\mathbb F}_{q^r}$ , considered as a linear space over ${\mathbb F}_q$ .

preprint2013arXiv

Additive Decompositions of Subgroups of Finite Fields

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

preprint2013arXiv

Averaging operators over homogeneous varieties over finite fields

In this paper we study the mapping properties of the averaging operator over a variety given by a system of homogeneous equations over a finite field. We obtain optimal results on the averaging problems over two dimensional varieties whose elements are common solutions of diagonal homogeneous equations. The proof is based on a careful study of algebraic and geometric properties of such varieties. In particular, we show that they are not contained in any hyperplane and are complete intersections. We also address partial results on averaging problems over arbitrary dimensional homogeneous varieties which are smooth away from the origin.

preprint2013arXiv

On the Product of Small Elkies Primes

Given an elliptic curve $E$ over a finite field $\F_q$ of $q$ elements, we say that an odd prime $\ell \nmid q$ is an Elkies prime for $E$ if $t_E^2 - 4q$ is a quadratic residue modulo $\ell$ , where $t_E = q+1 - #E(\F_q)$ and $#E(\F_q)$ is the number of $\F_q$-rational points on $E$ . These primes are used in the presently most efficient algorithm to compute $#E(\F_q)$. In particular, the bound $L_q(E)$ such that the product of all Elkies primes for $E$ up to $L_q(E)$ exceeds $4q^{1/2}$ is a crucial parameter of this algorithm. We show that there are infinitely many pairs $(p, E)$ of primes $p$ and curves $E$ over $\F_p$ with $L_p(E) \ge c \log p \log \log \log p$ for some absolute constant $c>0$ , while a naive heuristic estimate suggests that $L_p(E) \sim \log p$ . This complements recent results of Galbraith and Satoh (2002), conditional under the Generalised Riemann Hypothesis, and of Shparlinski and Sutherland (2012), unconditional for almost all pairs $(p,E)$ .

preprint2012arXiv

On Congruences with Products of Variables from Short Intervals and Applications

We obtain upper bounds on the number of solutions to congruences of the type $(x_1+s)...(x_ν+s)\equiv (y_1+s)...(y_ν+s)\not\equiv0 \pmod p$ modulo a prime $p$ with variables from some short intervals. We give some applications of our results and in particular improve several recent estimates of J. Cilleruelo and M. Z. Garaev on exponential congruences and on cardinalities of products of short intervals, some double character sum estimates of J. B. Friedlander and H. Iwaniec and some results of M.-C. Chang and A. A. Karatsuba on character sums twisted with the divisor function.

preprint2012arXiv

Statistics of Different Reduction Types of Fermat Curves

We present some theoretic bounds and algorithms concerning the statistics of different reduction types in the family of Fermat curves $Y^p = X^s(1-X)$ , where $p$ is prime and $s =1, ..., p-2$ .

preprint2011arXiv

Degree Growth, Linear Independence and Periods of a Class of Rational Dynamical Systems

We introduce and study algebraic dynamical systems generated by triangular systems of rational functions. We obtain several results about the degree growth and linear independence of iterates as well as about possible lengths of trajectories generated by such dynamical systems over finite fields. Some of these results are generalisations of those known in the polynomial case, some are new even in this case.

preprint2011arXiv

Distribution on elements of cosets of small subgroups and applications

We obtain a series of estimates on the number of small integers and small order Farey fractions which belong to a given coset of a subgroup of order $t$ of the group of units of the residue ring modulo a prime $p$ , in the case when $t$ is small compared to $p$ . We give two applications of these results: to the simultaneous distribution of two high degree monomials $x^{k_1}$ and $x^{k_2}$ modulo $p$ and to a question of J.Holden and P.Moree on fixed points of the discrete logarithm.

preprint2011arXiv

On numbers $n$ dividing the $n$ th term of a linear recurrence

Here, we give upper and lower bounds on the count of positive integers $n\le x$ dividing the $n$ th term of a nondegenerate linearly recurrent sequence with simple roots.

preprint2010arXiv

On Small Solutions to Quadratic Congruences

We estimate the deviation of the number of solutions of the congruence $m^2-n^2 \equiv c \pmod q, \qquad 1 \le m \le M, \ 1\le n \le N,$ from its expected value on average over $c=1, ..., q$ . This estimate is motivated by the recently established by D. R. Heath-Brown connection between the distibution of solution to this congruence and the pair correlation problem for the fractional parts of the quadratic function $αk^2$ , $k=1,2,...$ with a real $α$ .

preprint2010arXiv

Some Additive Combinatorics Problems in Matrix Rings

We study the distribution of singular and unimodular matrices in sumsets in matrix rings over finite fields. We apply these results to estimate the largest prime divisor of the determinants in sumsets in matrix rings over the integers.

preprint2009arXiv

On the Degree Growth in Some Polynomial Dynamical Systems and Nonlinear Pseudorandom Number Generators

In this paper we study a class of dynamical systems generated by iterations of multivariate polynomials and estimate the degreegrowth of these iterations. We use these estimates to bound exponential sums along the orbits of these dynamical systems and show that they admit much stronger estimates than in the general case and thus can be of use for pseudorandom number generation.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Igor Shparlinski

Research overview

Is this your work?

19 publications

An effective local-global principle for algebraic varieties and the sum product problem in finite fields

Order of torsion for reduction of linearly independent points for a family of Drinfeld modules

Bounds on short character sums and L-functions for characters with a smooth modulus

Polynomial Interpolation and Identity Testing from High Powers over Finite Fields

Character Sums and Deterministic Polynomial Root Finding in Finite Fields

Congruences with intervals and subgroups modulo a prime

On the Fixed Points of the Map x -> x^x Modulo a Prime

Polynomial Values in Subfields and Affine Subspaces of Finite Fields

Additive Decompositions of Subgroups of Finite Fields

Averaging operators over homogeneous varieties over finite fields

On the Product of Small Elkies Primes

On Congruences with Products of Variables from Short Intervals and Applications

Statistics of Different Reduction Types of Fermat Curves

Degree Growth, Linear Independence and Periods of a Class of Rational Dynamical Systems

Distribution on elements of cosets of small subgroups and applications

On numbers $n$ dividing the $n$ th term of a linear recurrence

On Small Solutions to Quadratic Congruences

Some Additive Combinatorics Problems in Matrix Rings

On the Degree Growth in Some Polynomial Dynamical Systems and Nonlinear Pseudorandom Number Generators

See the researcher in context

Building this map preview

Igor Shparlinski

Research overview

Is this your work?

19 publications

An effective local-global principle for algebraic varieties and the sum product problem in finite fields

Order of torsion for reduction of linearly independent points for a family of Drinfeld modules

Bounds on short character sums and L-functions for characters with a smooth modulus

Polynomial Interpolation and Identity Testing from High Powers over Finite Fields

Character Sums and Deterministic Polynomial Root Finding in Finite Fields

Congruences with intervals and subgroups modulo a prime

On the Fixed Points of the Map x -> x^x Modulo a Prime

Polynomial Values in Subfields and Affine Subspaces of Finite Fields

Additive Decompositions of Subgroups of Finite Fields

Averaging operators over homogeneous varieties over finite fields

On the Product of Small Elkies Primes

On Congruences with Products of Variables from Short Intervals and Applications

Statistics of Different Reduction Types of Fermat Curves

Degree Growth, Linear Independence and Periods of a Class of Rational Dynamical Systems

Distribution on elements of cosets of small subgroups and applications

On numbers nnn dividing the nnnth term of a linear recurrence

On Small Solutions to Quadratic Congruences

Some Additive Combinatorics Problems in Matrix Rings

On the Degree Growth in Some Polynomial Dynamical Systems and Nonlinear Pseudorandom Number Generators

See the researcher in context

Building this map preview

On numbers $n$ dividing the $n$ th term of a linear recurrence