Computing Logarithms in Finite Fields of Characteristic Two

From MaRDI portal





Let \(\alpha\) be primitive element of \(\mathrm{GF}(2^n)\), where \(\alpha\) is a zero of the primitive polynomial \(f(x)\) over \(\mathrm{GF}(2)\). Let \(\beta\) be an element of \(\mathrm{GF}(2^n)\), given as a polynomial \(g(x)\) of degree \(<n\). The logarithm of \(\beta\) is the exponent \(i\) such that \(\alpha^i=\beta\). The computation of this logarithm is in general time consuming. In the present paper an algorithm is proposed which is a variation of an idea of \textit{L. Adleman} [in: Proc. IEEE 20th annual symposium on foundations of computer science, 55--60 (1979; Zbl 0418.68002)]. The main idea is the following. If \(\deg g(x)<(n-1)/2\) the problem is considered ``easy by factoring \(g(x)\); this part of the algorithm is described separately. By the Euclidean algorithm one can find two polynomials \(r(x)\), \(t(x)\), each of degree \(\leq(n-1)/2\), such that \(t(x) g(x)\equiv r(x) \bmod f(x)\). Therefore \(\log \beta =\log g(x)=\log r(x)-\log t(x)\), and thus the problem is reduced to two ``easier cases. The paper compares the new method with the algorithm proposed by Adleman.




Cited in
(27)








This page was built for publication: Computing Logarithms in Finite Fields of Characteristic Two

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