Fast Irreducibility Testing for XTR Using a Gaussian Normal Basis of Low Complexity

摘要

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(p~2). 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 not ≡ 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(p~2), 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.