素域中的一些密码学结论能应用于Galois域吗？
素域中的一些密码学结论能应用于Galois域吗？
提问于 2023-04-18 15:33:58
如整数分解问题和离散对数问题。假设一个大的多项式是由两个生成的多项式相乘得到的，那么把它分解成这两个生成的多项式很难吗？假设A是Galois场的生成元，B是一个随机数，那么NP很难找到x使A^x=B保持不变吗？
回答 1
Cryptography用户
回答已采纳
发布于 2023-04-18 18:24:29
即使整数离散日志(DL)也不知道是NP完全的。正如@poncho在评论中指出的那样，NP\neq coNP很可能意味着DL并不是NP硬的。
它的确切硬度是未知的。当然，Merkle背包公钥密码体制是基于NP难题的，但它被打破了。
关于有限域DL (详见这里)：对于某些设置，它的复杂度是拟多项式，否则它可以是次指数但超多项式。
有关特性2，请参见这个问题这里。
对于有限域上的多项式因式分解，有了Berlekamp算法及其后来的改进。
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://crypto.stackexchange.com/questions/106148
复制相关文章
相似问题
腾讯云开发者
