分类目录归档:研究

走别人没有走过的路。

On Some Papers (2)

中断了几天,接着看文章,希望能坚持下去,无论在哪里。

Square Root Algorithm in F(q) for q ≡ 2^s+ 1 (mod 2^(s+1))
平方根算法,之前在课本上看的那个应该是素域上的平方根算法吧,还真没仔细看是否适用于这种扩域上的情况。作者提出的这类平方根算法都很简单,复杂度也很低,只需要一个指数运算。s是满足如下条件的最大整数:2^s|q-1,因为算法有2^(s-1)个,所以暂时也只能解决s很小的情况,比如作者解决了s=2,3,4的情况,也就是q ≡ 5 (mod 8),q ≡ 9 (mod 16),q ≡ 17 (mod 32)这三种情况的平方根算法。
继续阅读

On Some Papers (1)

无论去到哪里,希望可以坚持下去,每天至少看三篇文章。

Relation collection for the Function Field Sieve
小特征有限域(F(2^1039)和F(3^647))上离散对数问题求解的算法,作者主要的贡献是提出了“关系集合”和“小特征有限域上运算”的优化算法,然后实现的时候遇到了一大堆我看不懂的东西,比如:格,环同态,结式等等。最后貌似作者也没最终算出来,不过这种大项目也只适合“有钱人”玩。太多复杂的过程,和小修小补我是看不上眼的,是我心态问题吧……给个关键字,FFS(Function Field Sieve)。
继续阅读

On Some Papers (0)

看文章什么的最痛苦了,记录如下:

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),似乎问题解决得相当不错了。
继续阅读