What is the inverse of repeated square and multiply algorithm?

H. Gopalkrishna Gadiyar, et al. "What is the inverse of repeated square and multiply algorithm?." Colloquium Mathematicae 116.1 (2009): 1-14. <http://eudml.org/doc/284321>.

@article{H2009,
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.},
author = {H. Gopalkrishna Gadiyar, K. M. Sangeeta Maini, R. Padma, Mario Romsy},
journal = {Colloquium Mathematicae},
keywords = {repeated square and multiply algorithm; discrete logarithm; Legendre symbol; square root modulo ; problem},
language = {eng},
number = {1},
pages = {1-14},
title = {What is the inverse of repeated square and multiply algorithm?},
url = {http://eudml.org/doc/284321},
volume = {116},
year = {2009},
}

TY - JOUR
AU - H. Gopalkrishna Gadiyar
AU - K. M. Sangeeta Maini
AU - R. Padma
AU - Mario Romsy
TI - What is the inverse of repeated square and multiply algorithm?
JO - Colloquium Mathematicae
PY - 2009
VL - 116
IS - 1
SP - 1
EP - 14
AB - 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.
LA - eng
KW - repeated square and multiply algorithm; discrete logarithm; Legendre symbol; square root modulo ; problem
UR - http://eudml.org/doc/284321
ER -