A Novel Systolic Linear Array Architecture for Partitioning Montgomery Modular Multiplication
Zhou Yu · 2006
A new partitioning Montgomery modular multiplication algorithm(PMMM) is proposed in this paper together with a hardware architecture proper for it to get high simultaneity and performance.And the architecture is a liner high- index systolic array one that is refined from the one proposed by C.D.Walter.While Walter used (n+1) (n+2)PEs to accomplish Montgomery modular multiplication,we use n+2 PEs,and the simultaneity is two times higher than Walter' sone.Utilizing the new architecture in modular exponentiation operation,we can reduce the latencies of non- square modular multiplication to half of that of[3]in the cost of one precomputation,and the latencies of square modu- lar are the same as in [3],in that the speed is faster.Of course,to keep balance between speed and hardware resource, we also provide methods to realize modular multiplication and exponentiation with n/2+1 PEs,for which we have also provided comprehensive analysis.