Fast Algorithm And Its Application In Ecc. Oef Achieved

The security of Elliptic Curve Cryptography(ECC) is based on the difficulty of elliptic curve discrete logarithm. This paper researches fast algorithm over OEF and its implementation. The algorithm about ECC is divided into two parts, high-layer and bottom-layer calculation.The high-layer calculation is for point's operation on the ECC(scalar multiplication) and the bottom-layer calculation is for the polynomial multiplication over finite field. The association of them can increase the computation speed on the ECC greatly. We discussed the effective algorithm and the software's implementation on the ECC over finite field( GF ( p m)). This paper researches the feature of optimal extension fields as well as the fast algorithm in these fields, and the fast algorithm about scalar multiplication(kP). After analyzing several classic algorithms of field-inversion and polynomial multiplication in optimal extension fields, we proposed one efficient algorithm to modify polynomial multiplication based on Karatsuba's algorithm. The test results, compared with the normal hard multiplication, show that the speed performance of the improved algorithm has been increased nearly 4% and the computation comcomplexity is lower than Karatsuba's algorithm. By studying the fast algorithm about scalar multiplicationin, we proposed two efficient algorithm named 3P algorithm and MFBW. 3P decreased the computation comcomplexity of scalar multiplicationin, and MFBW algorithm used precomputation to increase the speed. The tested results show a speed increase of 15% than the binary algorithm. Our results are the same or better than Daniel V.Bailey's simulation results based on a certain magnitude.