看文章什么的最痛苦了,记录如下:
New Cube Root Algorithm Based on Third Order Linear Recurrence Relation in Finite Field
就是找到有限域Fq上的三次方根的算法,不过对q有要求,满足q≡1(mod 9)。q为5000bits时,不到12秒就可以算出来了,3000bits时只要5秒。并且这种方法可以进一步得到有限域上r次方根算法,不过实现上困难的地方在”double and add”公式上。呃,什么是”double and add”呢?没瞄出来,不过自己也不感兴趣,不过,貌似对于某域上求解x^r≡=c(mod q)这样的r次方根,貌似只要在φ(q)上求出r的逆元便可,是我看错了吗?反正就是没什么兴趣了。其实,后来作者又写了这么一篇(Trace Expression of r-th Root over Finite Field),似乎问题解决得相当不错了。
继续阅读
