
The logarithm of an element \(y\) of a finite field to the base of some fixed primitive element \(\alpha\) is \(x\) if \(y=\alpha^ x\). A probabilistic algorithm to determine logarithms in the finite field \(\mathrm{GF}(p^ 2)\) is given. An isomorphism is established between \(\mathrm{GF}(p^ 2)\) and \(I(\sqrt{m})/(p)\) where \(I(\sqrt{m})\) is the set of integers in the quadratic field \({\mathbb Q}(\sqrt{m})\), \(m\) a square free integer, and \((p)\) is an ideal of \(I(\sqrt{m})\). The structure of the residue class field is used in defining the algorithm. As with previous work, the algorithm requires precomputation and postcomputation stages. The precomputation involves the determination of the logarithms of a fixed set of quadratic primes with small prime norm, the ``smooth'' elements. The postcomputation stage involves the decomposition of the given element, or randomly chosen perturbations of it, into a product of smooth elements. A complexity analysis is given of the algorithm and it is shown to be subexponential.
cryptography, probabilistic algorithm, quadratic field, Analysis of algorithms and problem complexity, Randomized algorithms, Algebraic coding theory; cryptography (number-theoretic aspects), logarithms, complexity analysis, subexponential algorithm, Cryptography, finite field, Number-theoretic algorithms; complexity
cryptography, probabilistic algorithm, quadratic field, Analysis of algorithms and problem complexity, Randomized algorithms, Algebraic coding theory; cryptography (number-theoretic aspects), logarithms, complexity analysis, subexponential algorithm, Cryptography, finite field, Number-theoretic algorithms; complexity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 35 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
