Number theoretic methods in cryptography. Complexity lower bounds

zbMath0912.11057MaRDI QIDQ1276548

Igor E. Shparlinski

Publication date: 23 February 1999

Published in: Progress in Computer Science and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

linear recurring sequencesBoolean functionsRSA generatorpermutation polynomialsopen problemsinterpolating polynomialsdiscrete logarithmprime fieldalgebraic functionslower bounds on complexityBlum-Blum-Schub generatordegrees and orders of polynomialsDiffie-Hellman cryptosystempolynomial representations of nonlinear pseudo-random number generatorsprimitive root testingZech logarithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Exponential sums (11T23)

Related Items

On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping ⋮ Polynomial representations of the Diffie-Hellman mapping ⋮ On the statistical properties of Diffie-Hellman distributions ⋮ Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem ⋮ A lower bound for primality ⋮ A note on the interpolation of the Diffie-Hellman mapping ⋮ Polynomial representations of the Lucas logarithm ⋮ On a family of preimage-resistant functions ⋮ Circuit and decision tree complexity of some number theoretic problems ⋮ On the distribution of the Diffie-Hellman pairs ⋮ Incomplete character sums and polynomial interpolation of the discrete logarithm