Hostname: page-component-7b7567c8c-8tzhz Total loading time: 0 Render date: 2026-11-19T08:20:42.336Z Has data issue: false hasContentIssue false

Polynomial representations of the Diffie-Hellman mapping

Published online by Cambridge University Press:  17 April 2009

Edwin El Mahassni
Affiliation:
Department of Computing, Macquarie University, New South Wales 2109, Australia, e-mail: eelmaha@ics.mq.edu.au, igor@ics.mq.edu.au
Igor Shparlinski
Affiliation:
Department of Computing, Macquarie University, New South Wales 2109, Australia, e-mail: eelmaha@ics.mq.edu.au, igor@ics.mq.edu.au
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 q 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.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 2001