中断了几天,接着看文章,希望能坚持下去,无论在哪里。
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)这三种情况的平方根算法。
继续阅读