Abstract
We consider the problem of solving systems of equations $P_i (x) \equiv 0(\bmod n_i )i = 1 \cdots k$ where $P_i $ are polynomials of degree d and the $n_i $ are distinct relatively prime numbers and $x < \min (n_i )$. We prove that if $k > {{d(d + 1)} / 2}$ we can recover x in polynomial time provided $\min (n_i ) > 2^{d^2 } $. As a consequence the RSA cryptosystem used with a small exponent is not a good choice to use as a public-key cryptosystem in a large network. We also show that a protocol by Broder and Dolev [Proceedings on the 25th Annual IEEE Symposium on the Foundations of Computer Science, 1984] is insecure if RSA with a small exponent is used.
Keywords
CryptosystemExponentDegree (music)Prime (order theory)PolynomialPublic-key cryptographyModular designDiscrete mathematicsMathematicsKey (lock)CombinatoricsAlgebra over a fieldCryptographyComputer scienceAlgorithmPure mathematicsPhysicsEncryptionMathematical analysis
Affiliated Institutions
Related Publications
SOME PUBLIC-KEY CRYPTO-FUNCTIONS AS INTRACTABLE AS FACTORIZATION
In the RSA public-key crypto system a message M (<R) is encrypted by calculating K≡me (mod R), where 0<K<R and R, e are integers which are made public. The recipient of K can de...
Wave propagation and localization in a long-range correlated random potential
We examine the effect of long-range spatially correlated disorder on the Anderson localization transition in $d=2+\ensuremath{\epsilon}$ dimensions. This is described as a phase...
Deuterium trapping in helium-implanted nickel
By means of ion-beam-analysis techniques, the trapping of deuterium implanted into nickel preimplanted with helium was investigated in the temperature range 100–500 K. Following...
Anatomic validation of left ventricular mass estimates from clinical two-dimensional echocardiography: initial results.
We performed a prospective anatomic validation study to determine the accuracy of left ventricular (LV) mass estimates from clinical two-dimensional echocardiographic (2-D echo)...
Optimization of high-sensitivity fluorescence detection
We present general expressions for the number of photons emitted by a fluorescent chromophore as a function of the intensity and the duration of illumination. The aim is to find...
Publication Info
- Year
- 1988
- Type
- article
- Volume
- 17
- Issue
- 2
- Pages
- 336-341
- Citations
- 170
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
170
OpenAlex
Cite This
Johan Håstad
(1988).
Solving Simultaneous Modular Equations of Low Degree.
SIAM Journal on Computing
, 17
(2)
, 336-341.
https://doi.org/10.1137/0217019
Identifiers
- DOI
- 10.1137/0217019