Research On Fast Implementations Of Multiplications In Finite Field And Ring

The paper is focused on fast implementation of multiplications in finite fields of primecharacteristic GF(p^k), composite fields GF(2ⁿ)^m and rings, so that correlative algorithms arepresented. The research work is as following.Efficient algorithm about multiplication operation a·b·r in GF(p^k) are put forward, wherer is a special fixed element of the field. Through import Montgomery algorithm in ring ofinteger, improvement has been done for the algorithm proposed in [17] and speed upimplementation of the multiplication. Meanwhile, optimized algorithm using redundantrepresentation for GF(p^k) is also put forward.Analysis was done for the parameter selection of Montgomery algorithm in ringF_p [x]/(x·p(x)). Through suitable algorithm parameter and representation change in ring, wereduce the complexity of multiplication in F_p [x]/(x. p(x)).Then extension is done for Bajard's algorithm about efficient multiplication in GF(p^k),we use non-liner binomials instead of liner binomials used in former algorithm and give thenew algorithm. We prove the algorithm theoretically and practically that new algorithm ismore applicable and has more advantages in software implementation. Meanwhile, newalgorithm is extend in composite fields GF(2ⁿ)^m and reduce the complexity of multiplication inGF(2ⁿ)^m.In the end, research work has been done for the existence of the irreducible binomial withm degree in F_2ⁿ[x] and necessary condition is given. Corresponding analysis forimplementation of multiplication in GF(2^)m with binomial field polynomial has been doneand Correlative algorithm has also been brought forward.