利用超奇异椭圆曲线进行素性检验(英文)  

A primality test algorithm using supersingular elliptic curves

作　　者：于飞[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《中国科学技术大学学报》2010年第6期577-582,共6页JUSTC

摘　　要：根据超奇异椭圆曲线有理点个数与素数的关系,提出一个具有多项式时间复杂度的素性检验的概率型算法.对于给定的整数N,如果N≡3(mod4)或者N≡1(mod3),该算法具有多项式时间O(log8N).在广义黎曼假设成立的情况下,对于所有整数都具有这一时间复杂度.A new efficient probabilistic algorithm for primality tests was derived from the relation between supersingular elliptic curves and primes. For integers N≡3（mod 4） or N≡1（mod 3）,it can be performed in polynomial time O（log8N）. Assume GRH,the running time holds for other integers.

关 键 词：素性检验 椭圆曲线 Schoof算法 复乘方法 

分 类 号：O156.2[理学—数学]