Patent ID: 6061706
Filing Date: 2000-05-09
Classification: G06F

Abstract:
A systolic linear-array modular multiplier for implementing modular multiplication S=AB2.sup.-(n+6) mod M, wheren is an integer, representing an ability to operate the n-bit multiplication in the modular multiplication;A is an (n+3)-bit binary number a.sub.n+2 a.sub.n+1 . . . a.sub.1 a.sub.0 ;B is an (n+3)-bit binary number b.sub.n+2 b.sub.n+1 . . . b.sub.1 b.sub.0 ; andmod M is an n-bit binary odd number m.sub.n-1 m.sub.n-2 . . . m.sub.1 m.sub.0, where m.sub.0 =1,the systolic linear-array modular multiplier comprising:a linear array of n/2+2 processing elements with an identical architecture and an external AND gate so as to perform an n-bit multiplication, each of said processing elements including:a plurality of full adders;a plurality of AND gates; anda plurality of D-type flip-flops;wherein all of the above are interconnected in said processing elements to permit said systolic linear-array modular multiplier to implement modular multiplication S=AB2.sup.-(n+6) mod M by the steps of:(1) performing the following pre-computation step:M=((8-m.sub.2 m.sub.1 m.sub.0).sup.-1 mod 8)MT=(M[-].+-.1)div8, assuming T=t.sub.n-1 . . . t.sub.1 t.sub.0 ;(2) definingS.sub.0 =0;q.sub.-2 =q.sub.-1 =0(3) performing the following iteration loop:for i=0 to n+6 doq.sub.i =S.sub.i mod 2S.sub.i-1 =S.sub.i div 2+q.sub.i-2 T+b.sub.i Aend;and(4) performing the following computation:S.sub.n+8 =S.sub.n+7 +2q.sub.n+[s]5 TS=S.sub.n+8 +4q.sub.n+6 T,wherein after operations of the steps, S=AB2.sup.-(n+6) mod M is obtained with input parameters of A, B, and M.