问离散对数问题- Pohlig Hellman $GF(2^p)$
EN

Cryptography用户

提问于 2018-05-05 17:19:43

回答 1查看 131关注 0票数 0

如果我需要使用多项式$GF(2^{60})$我知道这个算法是如何与数字一起工作的，那么我想问如何修改Pohlig算法，但是我无法想象如何使用多项式进行一些操作。例如，如果我需要执行$g^{\frac{p-1}{q^e}}$。我怎么能用多项式做这件事？

发布于 2018-05-06 05:31:11

像$GF(2^n)$这样的域用多项式模$f(x)$的剩余类表示，其中GF(2)$中的$f \是一个具有二元系数的不可约的$n$次多项式。有$2^n这样的多项式$$a(x)=a_0+a_1 x+ \cdots+ a_{n-1} x^{n-1}.$$

加法是通过模2的系数加法。当将两个多项式相乘时，取乘积模$f(x)$的其余部分。

您可以使用平方和乘(请参阅这里)来计算幂$$a(x)^k=a(x)^{k_0+2 k_1+ 2^2 k_2+ \cdots+ 2^t k_t}，$$注意不时地减少模$f(x)$，因此平方的程度不会太大。

票数 1

页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://crypto.stackexchange.com/questions/58971

复制

相似问题

问离散对数问题- Pohlig Hellman $GF(2^p)$EN