Design of a linear systolic array for computing modular multiplication andsquaring in GF(2(m))

One of the main operations for the public key cryptosystem is tile modular expoaentiation. In this paper, we analyze the Montgomery's algorithm and de sign a linear systolic array for performing both modular multiplication and modular squaring simultaneously The proposed systolic array with less hard ware complexity can be designed by making use of common-multiplicand multip lication in the right-to-left modular exponentiation over GF(2(m)). For the fast computation of the modular exponentiation, the proposed systolic arra y has 1.25 times improvement in area-time complexity when compared to exist ing multipliers. The proposed systolic array suffers a little loss in time complexity, but it has 1.44 times improvement in area complexity since it e xecutes the common parts that exist in the simultaneous computation of both modular multiplication and squaring only once. It could be designed on VLS I hardware and used in IC cards. (C) 2001 Elsevier Science Ltd. All rights reserved.