Application of Semi-Primitive Roots to the Computation of the Discrete Logarithm Modulo $2^{k}$

In 2004, Fit-Florea and Matula presented an algorithm for computing the discrete logarithm modulo  $2^{k}$ with logarithmic base 3. The algorithm is suitable for hardware support of applications where fast arithmetic computation is desirable.

This talk aims to present a connection between semi-primitive roots of the multiplicative group of integers modulo $2^{k}$ where $k\geq 3$, and the logarithmic base in the Fit-Florea and Matula's algorithm. Using properties of semi-primitive roots modulo $2^{k}$ we generalize the algorithm to find the discrete logarithm modulo $2^{k}$ with any semi-primitive root as the base.