Polynomial representations of the Diffie-Hellman mapping

Edwin El Mahassni*, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


We obtain lower bounds on the degrees of polynomials representing the Diffie-Hellman mapping (gx,gy) → gxy, where g is a primitive root of a finite field double-struck F signq of q elements. These bounds are exponential in terms of log q. In particular, these results can be used to obtain lower bounds on the parallel arithmetic complexity of breaking the Diffie-Hellman cryptosystem. The method is based on bounds of numbers of solutions of some polynomial equations.

Original languageEnglish
Pages (from-to)467-473
Number of pages7
JournalBulletin of the Australian Mathematical Society
Issue number3
Publication statusPublished - Jun 2001


Dive into the research topics of 'Polynomial representations of the Diffie-Hellman mapping'. Together they form a unique fingerprint.

Cite this