Resolving large prime(s) variants for discrete logarithm computation

A J Holt, J H Davenport

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We conduct an investigation of large prime variant modifications to the well-known index calculus method for discrete logarithm computation modulo a prime p. We highlight complications in this technique that do not occur in its analogue application in factoring, and show how a simple adaption of the methods of [16] can be used to resolve relations such that the yield of the technique is within some E of that obtained in factoring. We then consider how these techniques scale to the use of more large primes, and demonstrate how the techniques of [10], [16] allow us to resolve relations involving more large primes, such that yield is generally the same as that obtained in factoring. Finally, we consider the impact that 'large prime' relations have on both the linear algebra stage of the index calculus method, and on actual discrete logarithm computation - a problem with no analogue in factoring.
Original languageEnglish
Title of host publicationCryptography and Coding, Proceedings
Pages207-222
Number of pages16
Volume2898
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science

Fingerprint Dive into the research topics of 'Resolving large prime(s) variants for discrete logarithm computation'. Together they form a unique fingerprint.

  • Cite this

    Holt, A. J., & Davenport, J. H. (2003). Resolving large prime(s) variants for discrete logarithm computation. In Cryptography and Coding, Proceedings (Vol. 2898, pp. 207-222). (Lecture Notes in Computer Science).