What is the inverse of repeated square and multiply algorithm?

DOI10.4064/CM116-1-1MaRDI QIDQ3623254zbMATH OpenOpenAlexFDO

Authors H. Gopalkrishna Gadiyar, K. M. Sangeeta Maini, R. Padma, Mario Romsy

Publication date 16 April 2009

Published in Colloquium Mathematicum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0602154

zbMATH Keywords

\(3x+1\) problemdiscrete logarithmLegendre symbolrepeated square and multiply algorithmsquare root modulo \(p\)

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Cryptography (94A60)

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 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.

Recommendations

• A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
• Square-root algorithms for the discrete logarithm problem (a survey)
• Study of the discrete logarithm problem in \(\mathbb{F}_{p^ 3}\)
• Complexity of a determinate algorithm for the discrete logarithm
• scientific article; zbMATH DE number 3863322

This page was built for publication: What is the inverse of repeated square and multiply algorithm?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3623254)