All reports by Author Igor E. Shparlinski:

__
TR04-035
| 10th April 2004
__

Scott Contini, Ernie Croot, Igor E. Shparlinski#### Complexity of Inverting the Euler Function

__
TR02-071
| 6th June 2002
__

Bruno Codenotti, Igor E. Shparlinski#### Non-approximability of the Permanent of Structured Matrices over Finite Fields

__
TR00-045
| 23rd June 2000
__

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski#### On the Security of Diffie--Hellman Bits

__
TR00-041
| 19th May 2000
__

Igor E. Shparlinski#### Security of Polynomial Transformations of the Diffie--Hellman Key

__
TR00-040
| 19th May 2000
__

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski#### Security of the Most Significant Bits of the Shamir Message Passing Scheme

__
TR99-027
| 17th July 1999
__

Marek Karpinski, Igor E. Shparlinski#### On the computational hardness of testing square-freeness of sparse polynomials

__
TR99-021
| 8th April 1999
__

Igor E. Shparlinski#### ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

__
TR99-010
| 1st April 1999
__

Eric Allender, Igor E. Shparlinski, Michael Saks#### A Lower Bound for Primality

Comments: 1

__
TR98-056
| 31st August 1998
__

Anna Bernasconi, Igor E. Shparlinski#### Circuit Complexity of Testing Square-Free Numbers

__
TR98-054
| 26th August 1998
__

Igor E. Shparlinski#### On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

Scott Contini, Ernie Croot, Igor E. Shparlinski

We present an algorithm to invert the Euler function $\varphi(m)$. The algorithm, for a given integer $n\ge 1$, in polynomial time ``on average'', finds theset $\Psi(n)$ of all solutions $m$ to the equation $\varphi(m) =n$. In fact, in the worst case the set $\Psi(n)$ is exponentially large and cannot be ... more >>>

Bruno Codenotti, Igor E. Shparlinski

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 the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Boneh and Venkatesan have recently proposed a polynomial time

algorithm for recovering a ``hidden'' element $\alpha$ of a

finite field $\F_p$ of $p$ elements from rather short

strings of the most significant bits of the remainder

mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected

uniformly at ...
more >>>

Igor E. Shparlinski

D. Boneh and R. Venkatesan have recently proposed an approach to proving

that a reasonably small portions of most significant bits of the

Diffie--Hellman key modulo a prime are as secure the the whole key. Some

further improvements and generalizations have been obtained by

I. M. Gonzales Vasco ...
more >>>

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Boneh and Venkatesan have recently proposed a polynomial time

algorithm for recovering a ``hidden'' element $\alpha$ of a

finite field $\F_p$ of $p$ elements from rather short

strings of the most significant bits of the remainder

mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly

at random ...
more >>>

Marek Karpinski, Igor E. Shparlinski

We show that deciding square-freeness of a sparse univariate

polynomial over the integer and over the algebraic closure of a

finite field is NP-hard. We also discuss some related open

problems about sparse polynomials.

Igor E. Shparlinski

We show that a pseudo-random number generator,

introduced recently by M. Naor and O. Reingold,

possess one more attractive and useful property.

Namely, it is proved that for almost all values of parameters it

produces a uniformly distributed sequence.

The proof is based on some recent bounds of exponential

more >>>

Eric Allender, Igor E. Shparlinski, Michael Saks

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

Anna Bernasconi, Igor E. Shparlinski

In this paper we extend the area of applications of

the Abstract Harmonic Analysis to the field of Boolean function complexity.

In particular, we extend the class of functions to which

a spectral technique developed in a series of works of the first author

can be applied.

This extension ...
more >>>

Igor E. Shparlinski

Lower bounds are obtained on the degree and the number of monomials of

Boolean functions, considered as a polynomial over $GF(2)$,

which decide if a given $r$-bit integer is square-free.

Similar lower bounds are also obtained for polynomials

over the reals which provide a threshold representation

more >>>