Efficient multiplication for finite fields of p characteristic - LI Yin 1; CHEN Gong-liang1; LI Jian-hua1 (Tongxin xuebao)
Based on residue arithmetic,a new form of polynomial named PAPB in Fp[x] had been constructed.The amount and distribution of such irreducible polynomials had also been investigated.Then,an efficient algorithm for multiplication modulo PAPB had been proposed using residue arithmetic and Chinese remainder theorem.In the end,the result analysis was given.The theoretic analysis and simulation experiment show that for some finite field of medium prime characteristic,the given algorithm only costs O（k1.5） operations in Fp while the multiplication modulo irreducible binomial cost O（k2） operations,which shows a better performance.As a result,the work presents an interesting perspective for optimal extension field and elliptic curve cryptography.