论文标题
半主题根和离散对数模块$ 2^k $
Semi-primitive roots and the discrete logarithm module $2^k$
论文作者
论文摘要
我们在$ k \ geq 3 $中的乘法整数$ 2^{k} $的半质量根之间建立了连接，而fit-florea and Matula（2004）引入了算法中的对数基础，用于计算离散的对数Modulo Modulo $ 2^{k} $。 fit-florea和Matula使用了半启示根3模型的属性$ 2^{k} $来获得其结果，并为其他可能的基础提供了转换公式。我们表明，他们的结果可以扩展到任何半重要的root modulo $ 2^{k} $，还提供了其算法的广义版本，以找到离散的对数模型$ 2^{k} $。密码学，符号计算和其他应用程序中的各种应用可能会受益于更高的精确硬件整数算术。该算法适用于需要快速算术计算的应用程序的硬件支持。
We establish 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 algorithm introduced by Fit-Florea and Matula (2004) for computing the discrete logarithm modulo $2^{k}$. Fit-Florea and Matula used properties of the semi-primitive root 3 modulo $2^{k}$ to obtain their results and provided a conversion formula for other possible bases. We show that their results can be extended to any semi-primitive root modulo $2^{k}$ and also present a generalized version of their algorithm to find the discrete logarithm modulo $2^{k}$. Various applications in cryptography, symbolic computation, and others can potentially benefit from higher precision hardware integer arithmetic. The algorithm is suitable for hardware support of applications where fast arithmetic computation is desirable.
