ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > IGOR E. SHPARLINSKI:
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

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


TR02-071 | 6th June 2002
Bruno Codenotti, Igor E. Shparlinski

Non-approximability of the Permanent of Structured Matrices over Finite Fields

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


TR00-045 | 23rd June 2000
Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

On the Security of Diffie--Hellman Bits

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


TR00-041 | 19th May 2000
Igor E. Shparlinski

Security of Polynomial Transformations of the Diffie--Hellman Key

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


TR00-040 | 19th May 2000
Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Security of the Most Significant Bits of the Shamir Message Passing Scheme

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


TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

On the computational hardness of testing square-freeness of sparse polynomials

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.

more >>>

TR99-021 | 8th April 1999
Igor E. Shparlinski

ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

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


TR99-010 | 1st April 1999
Eric Allender, Igor E. Shparlinski, Michael Saks

A Lower Bound for Primality

Comments: 1

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


TR98-056 | 31st August 1998
Anna Bernasconi, Igor E. Shparlinski

Circuit Complexity of Testing Square-Free Numbers

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


TR98-054 | 26th August 1998
Igor E. Shparlinski

On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

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




ISSN 1433-8092 | Imprint