Several methods for finding a basis conversion matrix between two different bases in an extension field have been proposed. Among them, the one based on Gauss period normal basis (GNB) is on average the most efficient. However, since it needs to construct a certain tower field , some inefficient cases in which the towering degree becomes large have been reported. This paper first determines that such inefficient cases are caused by the GNB condition. In order to overcome this inefficiency, we propose a method that does not use any GNB in the target extension field , but instead uses a certain polynomial basis in derived by a certain small cyclic group in . This causes re- laxation of the condition for the towering degree . In addition, our experimental results show that the proposed method substantially accelerates the computation time for finding a basis conversion matrix.

Recently, ordinary pairing-friendly elliptic curves whose embedding degree is 1 have been often focused on, for example some composite order pairing-based cryptographies do. In the case of non-symmetric pairings whose embedding degree is larger than 2, recent efficient pairing techniques such as Rate and Xate pairings adopt a certain special rational point group with an efficient isomorphic mapping and then accelerate pairing-related operations such as a pairing calculation and a scalar multiplication. Based on cubic, quartic, and sextic twists, this paper shows how to activate these efficient techniques together with point compression on pairing-friendly curves of embedding degree 1.

Recently, efficient pairings such as optimal-ate, R-ate, and Xate pairings have been proposed. On the other hand, some pairing-based cryptographic protocols need several pairing calculations for one procedure. Thus, multi-pairing technique will be efficiently applied. This paper optimizes Xate pairing for multi-pairing and then evaluates its efficiency with comparing to the other efficient pairings. Then, it is shown that the multi-pairing with the optimized Xate pairing is the most efficient.

Self-dual normal basis is efficient for the arithmetic operations in extension field and especially trace calculation. However, self-dual normal bases do not exist in when characteristic p is odd and degree m is even. This paper proposes a method to construct an efficient normal basis for trace calculation when extension degree is even. In this paper, we call it pseudo self-dual normal basis.

This paper describes a fast image filtering processor. This dedicated processor is able to convolve a circular FIR filter of diameter 16 pixels to an image of 512×512 pixels within 0.5 sec by adoption of (a)hexagonal sampling and hexagonally sectioning method to realize the FIR filter and (b) discrete cyclic convolution with the Fermat number transform.

This paper presents a new implementation technique for two dimensional(2-D) finite impulse response(FIR) filter of relatively large support region using the number theoretic transform (NTT). This method uses a sectioning procedure and fast computation technique of 2-D digital cyclic convolution(DCC). As the size of 2-D DCC by direct use of the NTT is restricted small, the support region of FIR filter is further restricted. But, in the sectioning procedure, the cyclicity of the 2-D DCC should not always be rectangular. Therefore, we propose a 2-D DCC with skewingly cyclic extension. Using this new 2-D DCC and Agarwal's 2-D technique of the NTT, we may implement practical 2-D FIR filters with smaller number of computational operations.