Geodesic
What is the inverse of repeated square and multiply algorithm?
H. Gopalkrishna Gadiyar1 ; K. M. Sangeeta Maini1 ; R. Padma1 ; Mario Romsy2
1 AU-KBC Research Centre M. I. T. Campus of Anna University Chromepet, Chennai 600 044, India
2 Institut für theoretische Informatik und Mathematik Universität der Bundeswehr München 85577 Neubiberg, Germany
Colloquium Mathematicum, Tome 116 (2009) no. 1, pp. 1-14

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

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.
DOI : 10.4064/cm116-1-1
Keywords: known repeated square multiply algorithm efficient modular exponentiation obvious question ask algorithm has inverse which would calculate discrete logarithm what its time compexity technical hitch fixing right sign square root heart discrete logarithm problem finite fields characteristic equal paper couple probabilistic algorithms compute discrete logarithm finite fields their time complexity given bypassing difficulty algorithms inspired famous problem

H. Gopalkrishna Gadiyar 1 ; K. M. Sangeeta Maini 1 ; R. Padma 1 ; Mario Romsy 2

1 AU-KBC Research Centre M. I. T. Campus of Anna University Chromepet, Chennai 600 044, India
2 Institut für theoretische Informatik und Mathematik Universität der Bundeswehr München 85577 Neubiberg, Germany 
@article{10_4064_cm116_1_1,
     author = {H. Gopalkrishna Gadiyar and K. M. Sangeeta Maini and R. Padma and Mario Romsy},
     title = {What is the inverse of
 repeated square and multiply algorithm?},
     journal = {Colloquium Mathematicum},
     pages = {1--14},
     publisher = {mathdoc},
     volume = {116},
     number = {1},
     year = {2009},
     doi = {10.4064/cm116-1-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/cm116-1-1/}
}
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 Mathematicum
PY  - 2009
SP  - 1
EP  - 14
VL  - 116
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/cm116-1-1/
DO  - 10.4064/cm116-1-1
LA  - en
ID  - 10_4064_cm116_1_1
ER  - 
%0 Journal Article
%A H. Gopalkrishna Gadiyar
%A K. M. Sangeeta Maini
%A R. Padma
%A Mario Romsy
%T What is the inverse of
 repeated square and multiply algorithm?
%J Colloquium Mathematicum
%D 2009
%P 1-14
%V 116
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/cm116-1-1/
%R 10.4064/cm116-1-1
%G en
%F 10_4064_cm116_1_1
H. Gopalkrishna Gadiyar; K. M. Sangeeta Maini; R. Padma; Mario Romsy. What is the inverse of
 repeated square and multiply algorithm?. Colloquium Mathematicum, Tome 116 (2009) no. 1, pp. 1-14. doi: 10.4064/cm116-1-1

Cité par Sources :