What is the inverse of repeated square and multiply algorithm?

• Autorzy: H. Gopalkrishna Gadiyar , K. M. Sangeeta Maini , R. Padma , Mario Romsy
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 11Y16: Algorithms; complexity
• 68Q25: Analysis of algorithms and problem complexity
• 68W40: Analysis of algorithms

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Colloquium Mathematicum
• Rocznik: 2009
• Tom: 116
• Numer: 1
• Strony: 1-14

Daty

wydano

2009

Twórcy

autor

H. Gopalkrishna Gadiyar

• AU-KBC Research Centre, M. I. T. Campus of Anna University, Chromepet, Chennai 600 044, India

autor

K. M. Sangeeta Maini

• AU-KBC Research Centre, M. I. T. Campus of Anna University, Chromepet, Chennai 600 044, India

autor

R. Padma

• AU-KBC Research Centre, M. I. T. Campus of Anna University, Chromepet, Chennai 600 044, India

autor

Mario Romsy

• Institut für theoretische Informatik, und Mathematik, Universität der Bundeswehr München, 85577 Neubiberg, Germany

Identyfikatory

DOI

10.4064/cm116-1-1