Design of a linear systolic array for computing modular multiplication and squaring in \(\text{GF}(2^m)\) (Q5948833): Difference between revisions

Many public key cryptosystems make heavy use of modular arithmetics, with the modular exponentiation being the operation that plays important role in the overall time complexity of such algorithms. Standard implementation of the exponentiation operation makes use of a series of squaring and multiplication operations. In the paper linear systolic array for computing the modular multiplication and squaring simultaneously in \(GF(2^m)\) is proposed -- the array can be efficiently used for the modular exponentation in \(GF(2^m)\). The authors first analyze Montgomery multiplication algorithm to identify the common computational parts to perform concurrent execution of both modular squaring and multiplication in the modular exponentiation. Then they use formal approach to derive resulting systolic array, namely after deriving a dependence graph for the recurrence Montgomery algorithm a space-time transformation is applied. As a result linear systolic array with unidirectional data flow with \(m+1\) processing elements and latency \(3m+1\) is proposed.