Fast Finite Field Calculation Algorithm And Implementation

The calculation speed over finite fields greatly affects the performance of ECC implementation. So, to find a fast algorithm for finite field calculation becomes a hot field in recent cryptography researches. Through analyzing the different structure of finite fields (,,,), we insist to find optimal finite fields for software applications.This thesis is divided into two parts. The first one is the research on the feature of composition fields and optimal extension fields as well as the fast algorithm in those fields. The other one is the implementation of those improved algorithms. The main focus concentrates on the two most time consuming arithmetic in finite field calculation, field inversion and field multiplication. By analyzing in detail the performance of algorithms in composition fields, we have drawn a conclusion that the time consuming of square is less than that of multiplication with itself. So, we put forward an optimized exponential algorithm in which the multiplication with itself was substituted mostly by square. Through expanding of composition fields, the time consuming of optimal algorithm is , where n is the number of bits of exponential. Obviously, comparing with normal exponential algorithm, the optimal one is better.After analyzing several classic algorithms of field-inversion and polynomial multiplication in optimal fields, we propose two efficient algorithms to modified field inversion and polynomial multiplication algorithms. The test results show that the speed performance of the improved field-inversion algorithm has been increased nearly 5 times and the improved polynomial multiplication algorithm has been increased nearly 4 times.