What is the inverse of repeated square and multiply algorithm?

Volume 116 / 2009

H. Gopalkrishna Gadiyar, K. M. Sangeeta Maini, R. Padma, Mario Romsy Colloquium Mathematicum 116 (2009), 1-14 MSC: 11Y16, 68Q25, 68W40. DOI: 10.4064/cm116-1-1

Abstract

It is well known that the repeated square and multiply algorithm is an efficient way of modular exponentiation. The obvious question to ask is if this algorithm has an inverse which would calculate the discrete logarithm and what is its time compexity. The technical hitch is in fixing the right sign of the square root and this is the heart of the discrete logarithm problem over finite fields of characteristic not equal to 2. In this paper a couple of probabilistic algorithms to compute the discrete logarithm over finite fields and their time complexity are given by bypassing this difficulty. One of the algorithms was inspired by the famous $3x+1$ problem.

Authors

  • H. Gopalkrishna GadiyarAU-KBC Research Centre
    M. I. T. Campus of Anna University
    Chromepet, Chennai 600 044, India
    e-mail
  • K. M. Sangeeta MainiAU-KBC Research Centre
    M. I. T. Campus of Anna University
    Chromepet, Chennai 600 044, India
    e-mail
  • R. PadmaAU-KBC Research Centre
    M. I. T. Campus of Anna University
    Chromepet, Chennai 600 044, India
    e-mail
  • Mario RomsyInstitut für theoretische Informatik
    und Mathematik
    Universität der Bundeswehr München
    85577 Neubiberg, Germany
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image