Montgomery Multiplication and Squaring Algorithms in GF(2~k)

摘要

The current paper presents a fast implementation of group-level finite field Montgomery algorithms using two look-up tables. The proposed algorithm simultaneously computes Montgomery multiplication and squaring, thereby making modular exponentiation much faster. Plus, the proposed method is more efficient than existing multipliers when considering the tradeoff of computation time for table space. The use of tables reduces the number of operations, saves time through pre-computation, and avoids the complicated computations required in the Montgomery method. Consequently, the proposed look-up table-based algorithms have the advantage of speed and are particularly suitable for cryptographic applications, where k is large, and in memory-constrained environments, such as smart cards and embedded cryptosystems.