An original multiplication scheme for the multiplication of polynomials based on Karatsuba's method and modifications of the classical algorithm of the polynomial multiplication effective under a not large amount of nonzero coefficients for one of the multipliers are considered. A hybrid algorithm for the multiplication of polynomials over GF (2{sup}n) is developed. The algorithm makes use of either the modification of the classical algorithm or the algorithm based of Karatsuba's method depending on the form of multipliers. Experimental results of computer tests with the developed library of arithmetic operations in finite fields and in elliptic curves groups confirm the effectiveness of the offered methods. The suggested scheme of multiplication allows apparatus realization as well.
展开▼