已经几天没写了，始终有些过意不去，既然现在记得就再写点吧。
A note on the behaviour of the NFS in the medium prime case: Smoothness of Norms
作者就NFS算法的理论算法复杂度是实际算法运行时间进行了试验，并对其中多项式的选择给出了一些观察的结果，这可以指导我们实际操作的时候如何设定参数的大小。其中在筛阶段的光滑概率似乎还没有很好的计算方法，多项式的的预选择就是先估计这个光滑概率。
Continue reading
天气预报说今天有台风，然后是狂风暴雨的，但是该看的还是要看，继续吧。
On the Arithmetic Complexity of Strassen-Like Matrix Multiplications
矩阵乘法的时间复杂度啊，考虑的是没有稳定问题的情况，比如密码学中有限域元素构成的矩阵。n=2^k时，是这个5n^2:81 + 0:5n^2:59 + 2n^2:32；n=8*2^k时，是这个3:55n^2:81 + 0:148n^2:59 + 1:02n^2:32。跟原来的复杂度比起来，感觉改进不大，具体做法没细看，扫了一眼，不适合自己看，记住这个复杂度就好。
Continue reading
中断了几天，接着看文章，希望能坚持下去，无论在哪里。
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)这三种情况的平方根算法。
Continue reading
无论去到哪里，希望可以坚持下去，每天至少看三篇文章。
Relation collection for the Function Field Sieve
小特征有限域（F(2^1039)和F(3^647)）上离散对数问题求解的算法，作者主要的贡献是提出了“关系集合”和“小特征有限域上运算”的优化算法，然后实现的时候遇到了一大堆我看不懂的东西，比如：格，环同态，结式等等。最后貌似作者也没最终算出来，不过这种大项目也只适合“有钱人”玩。太多复杂的过程，和小修小补我是看不上眼的，是我心态问题吧……给个关键字，FFS（Function Field Sieve）。
Continue reading
看文章什么的最痛苦了，记录如下：
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），似乎问题解决得相当不错了。
Continue reading