Ostafe, Alina, Shparlinski, Igor
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...
Some Additive Combinatorics Problems in Matrix Rings (2009)
Ferguson, Ron, Hoffman, Corneliu, Luca, Florian, Ostafe, Alina, Shparlinski, Igor
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...
REVIEWS AND DESCRIPTIONS OF TABLES AND BOOKS (2008)
The numbers in brackets are assigned according to the American Mathematical
On curves over finite fields with Jacobians with small exponent, Int (2008)
We show that finite fields over which there is a curve of a given genus g ≥ 1 with its Jacobian having a small exponent, are very rare. This extends a recent result of W. Duke in the case g = 1. We...
On the Sum-Product Problem on Elliptic Curves (2008)
Ahmadi, Omran, Shparlinski, Igor
Let $\E$ be an ordinary elliptic curve over a finite field $\F_{q}$ of $q$ elements and $x(Q)$ denote the $x$-coordinate of a point $Q = (x(Q),y(Q))$ on $\E$. Given an $\F_q$-rational point $P$ of...
Joint Task Force on Computing Curricula, Computing Curricula 2001, sponsored by (2008)
Igor Shparlinski, Arne Winterhof
Abstract. Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element α ∈ Fp, wherep is prime, from rather short strings of the most significant bits of the...
Eric Allender, Igor Shparlinski, Michael Saks
Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC 0, and raised as an open question if similar (or stronger) lower bounds could be proved for the...
DOI 10.1007/s00200-005-0180-1 (2008)
Igor Shparlinski, Arne Winterhof, I. Shparlinski
Noisy interpolation of sparse polynomials
On Some Weighted Average Values of L-functions (2008)
Let $q\ge 2$ and $N\ge 1$ be integers. W. Zhang (2008) has shown that for any fixed $\epsilon> 0$, and $q^{\epsilon} \le N \le q^{1/2 -\epsilon}$, $$ \sum_{\chi \ne \chi_0} |\sum_{n=1}^N \chi(n)|^2...
Joint Task Force on Computing Curricula, Computing Curricula 2001, sponsored by (2008)
Igor Shparlinski, Arne Winterhof
Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a ”hidden ” element α ∈ IFp, where p is prime, from rather short strings of the most significant bits of the...
Marek Karpinski, Igor Shparlinski
We obtain new lower bounds on the number of non zeros of sparse polynomials and give a fully polynomial time (ffl; ffi) approximation algorithm for the number of non-zeros of multivariate sparse...
On Routing In Circulant Graphs (2007)
Jin-yi Cai, George Havas, Ajay Nerurkar, Igor Shparlinski
We investigate various problems related to circulant graphs -- finding the shortest path between two vertices, finding the shortest loop, and computing the diameter. These problems are related to...
Finding Points on Curves over Finite Fields (Extended Abstract) (2007)
Joachim Gathen, Igor Shparlinski
Joachim von zur Gathen Igor Shparlinski FB Mathematik-Informatik School of MPCE Universitat--GH Paderborn Macquarie University 33100 Paderborn, Germany Sydney, NSW 2109, Australia...
Joint Task Force on Computing Curricula, Computing Curricula 2001, sponsored by (2007)
Igor Shparlinski, Arne Winterhof
Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a "hidden " element # IF p, where p is prime, from rather short strings of the most significant bits of...
On Decimations of ℓ-Sequences ∗ (2007)
Mark Goresky, Ram Murty, Igor Shparlinski
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...
In this survey, we review two recent applications of a venerable tool: Gau periods. In Section 2, we describe Gau ' original construction, and how it can be used
On the Complexity of Some Arithmetic Problems over IF2[T] (2007)
Eric Allender, Anna Bernasconi, Carsten Damm, Michael Saks, Igor Shparlinski
In this paper, we study various combinatorial complexity characteristics of Boolean functions related to some natural arithmetic problems about polynomials over IF2. In particular, we consider the...
On Decimations of l-Sequences (2007)
Mark Goresky, Andrew Klapper, Ram Murty, Igor Shparlinski
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...
Parameters of Integral Circulant Graphs and Periodic Quantum Dynamics (2007)
Saxena, Nitin, Severini, Simone, Shparlinski, Igor
The intention of the paper is to move a step towards a classification of network topologies that exhibit periodic quantum dynamics. We show that the evolution of a quantum system, whose hamiltonian...
On curves over finite fields with Jacobians of small exponent (2006)
Ford, Kevin, Shparlinski, Igor
We show that finite fields over which there is a curve of a given genus g with its Jacobian having a small exponent, are very rare. This extends a recent result of W. Duke in the case g=1. We also...
On a Generalisation of a Lehmer Problem (2006)
We consider a generalisation of the classical Lehmer problem about the distribution of modular inverses in arithmetic progression, introduced by E. Alkan, F. Stan and A. Zaharescu. Using bounds of...
Klappenecker, Andreas, Roetteler, Martin, Shparlinski, Igor, Winterhof, Arne
We address the problem of constructing positive operator-valued measures (POVMs) in finite dimension $n$ consisting of $n^2$ operators of rank one which have an inner product close to uniform. This...
Complexity of Inverting the Euler Function (2004)
Contini, Scott, Croot, Ernie, Shparlinski, Igor
We present an algorithm to invert the Euler function $\phi(m)$. The algorithm, for a given $n \geq 1$, in polynomial time ``on average'', finds the set $\Psi(n)$ of all solutions $m$ to $\phi(m) =...
Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation (2002)
Russell, Alexander, Shparlinski, Igor
We consider the problem of recovering a hidden monic polynomial f(X) of degree d > 0 over the finite field F of p elements given a black box which, for any x in F, evaluates the quadratic character...
On the Distinctness of Decimations of ℓSequences (2002)
Mark Goresky, Andrew Klapper, Ram Murty, Igor Shparlinski
Abstract. 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...
On certain exponential sums and the distribution of Diffie-Hellman triples (1999)
Ran Canetti, John Friedlander, Igor Shparlinski
Let g be a primitive root modulo a prime p. It is proved that the triples (gx,gy,gxy), x,y�1,…,p�1, are uniformly distributed modulo p in the sense of H. Weyl. This result is based on the...
On The Computational Hardness Of Testing Square-Freeness Of Sparse Polynomials (1999)
Marek Karpinski And, Marek Karpinski, Igor Shparlinski
. We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field IFq of p elements is NP-hard. We also discuss some related open...
A Lower Bound for Primality (1999)
Eric Allender Dept, Eric Allender, Michael Saks, Igor Shparlinski
Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC , and raised as an open question whether similar (or stronger) lower bounds could be proved for...
On The Computational Hardness Of Testing Square-Freeness Of Sparse Polynomials (1999)
Marek Karpinski, Igor Shparlinski
. We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field IFq of p elements is NP-hard. We also discuss some related open...
A Lower Bound for Primality (1999)
Eric Allender, Michael Saks, Igor Shparlinski
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...
On the Ádám Conjecture on Circulant Graphs (1998)
Bernard Mans, Francesco Pappalardi, Igor Shparlinski
We investigate the condition for isomorphism between circulant graphs which is known as the Adam property. We describe a wide class of graphs for which the Adam conjecture holds (and even in a...
Circuit and Decision Tree Complexity of Some Number Theoretic Problems (1998)
Anna Bernasconi, Mathematik Informatik, Trierer Forschungsberichte, Trierer Forschungsberichte, Fachbereich Iv, Fachbereich Iv, ...
We extend the area of applications of the Abstract Harmonic Analysis to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. In...
On the Ádám Conjecture on Circulant Graphs (1998)
Bernard Mans, Francesco Pappalardi, Igor Shparlinski
this paper we study isomorphism between circulant graphs. Such graphs have a vast number of applications to telecommunication network, VLSI design and distributed computation [4, 13, 15, 17]. By...
Zero Testing of p-adic and Modular Polynomials (1997)
Marek Karpinski, Igor Shparlinski
We obtain new algorithms to test if a given multivariate polynomial over p-adic fields is identical to zero. We also consider zero testing of polynomials in residue rings. The results complement a...
Computing Components And Projections Of Curves Over Finite Fields (1997)
. 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...
Orders of Gauß Periods in Finite Fields (1996)
It is shown that Gauss periods of special type give an explicit polynomial-time computation of elements of exponentially large multiplicative order in some finite fields. This can be considered as a...
Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields (1994)
Marek Karpinski, Igor Shparlinski
We obtain new lower bounds on the number of non zeros of sparse polynomials and give a fully polynomial time (ffl; ffi ) approximation algorithm for the number of non-zeros of multivariate sparse...
Counting Curves and Their Projections (1994)
Marek Karpinski, Igor Shparlinski
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...
Counting curves and their projections (1993)
Marek Karpinski, Igor Shparlinski
Abstract. 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...
Counting Curves and Their Projections (1993)
Marek Karpinski, Igor Shparlinski
. 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...