Fast irreducibility testing for XTR using a gaussian normal basis of low complexity

作     者：Kwon, Soonhak Kim, Chang Hoon Hong, Chun Pyo 

作者机构：Inst. of Basic Science Dept. of Mathematics Sungkyunkwan University Suwon 440-746 Korea Republic of Dept. of Computer and Information Engineering Daegu University Kyungsan 712-714 Korea Republic of 

出 版 物：《Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)》 (Lect. Notes Comput. Sci.)

年 卷 期：2004年第3357卷

页      面：144-158页

核心收录：

主　　题：Cryptography 

摘      要：XTR appeared in 2000 is a very promising alternative to elliptic curve cryptosystem. Though the basic idea behind XTR is very elegant and universal, one needs to restrict the primes p such as p ≡ 2 (mod 3) for optimal normal bases since it involves many multiplications in GF(p2). Moreover the restriction p ≡ 2 (mod 3) is consistently used to improve the time complexity for irreducibility testing for XTR polynomials. In this paper, we propose that a Gaussian normal basis of type (2, k) for small k can also be used for efficient field arithmetic for XTR when p 2 (mod 3). Furthermore we give a new algorithm for fast irreducibility testing and finding a generator of XTR group when p ≡ 1 (mod 3). Also we present an explicit generator of XTR group which does not need any irreducibility testing when there is a Gaussian normal basis of type (2, 3) in GF(p2). We show that our algorithms are simple to implement and the time complexity of our methods are comparable to the best ones proposed so far. © Springer-Verlag 2005.