What is the inverse of repeated square and multiply algorithm?

Autor:	H. Gopalkrishna Gadiyar, K. M. Sangeeta Maini, R. Padma, Mario Romsy
Rok vydání:	2009
Předmět:	Iterated logarithm Discrete mathematics Quantities of information Modular exponentiation Pollard's kangaroo algorithm Logarithm Discrete logarithm General Mathematics Binary logarithm Algorithm Baby-step giant-step Mathematics
Zdroj:	Colloquium Mathematicum. 116:1-14
ISSN:	1730-6302 0010-1354
DOI:	10.4064/cm116-1-1
Popis:	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 efficiently. 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 are given by bypassing this difficulty. One of the algorithms was inspired by the famous 3x+1 problem.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::120796675b697c275b08fbb4994939f2 https://doi.org/10.4064/cm116-1-1 Zobrazit plný text záznamu