일반기술

몽고메리 모듈러 승산 장치

몽고메리 모듈러 승산 장치가 개시된다. 이 장치는 제1~제n+1 프로세서들을 구비하고, 제p+1 프로세서는 제p 프로세서로부터 입력한 제어 신호에 응답하여, 제p 프로세서로부터 입력한 n+1 비트열의 제1데이타(Ai), m+2 비트열의 제2 데이타(Bi), m+2개의 비트열로 구성되는 제3 데이타(Ni) 및 결과 데이타(Ti)을 이용하여 임시 변수(M) 및 제1 캐리(C=C1C0)를 계산하고 Ai, M 및 C를 저장하거나, 저장한 A, M 및 C와 제p 프로세서로부터 입력한 Ai, Bi, Ni 및 이전 결과값을 이용하여 제2 캐리(C'=C1'C0') 및 현재 결과값(Ti')를 계산하며, 이전 결과값(Ti) 또는 현재 결과값(Ti')과 입력한 Ai를 제p+2 프로세서로 출력하고 제어 신호, Bi 및 Ni들을 소정 시간 지연후에 제p+2 프로세서로 출력하고, 제1 프로세서로 입력되는 이전 결과값(T)과 제어 신호의 최하위 비트를 제외한 비트들은 모든 비트들은 "저" 논리 레벨이고, 제1 프로세서는 제어 신호를 외부로부터 입력하고, 제n+1 프로세서로부터 출력되며 n+m+1 비트열로 구성되는 현재 결과값들은 제1 데이타와 제2 데이타를 몽고메리 모듈러 N 승산한 결과인 것을 특징으로 한다. 그러므로, 몽고메리 모듈러 승산을 고속으로 수행할 수 있고, 하드웨어 설계 비용이 저렴한 효과가 있다.의 비트열로 구성되는 제2 데이타(Bi)를 몽고메리 모듈러 Ni(여기서, N은 m+2개의 비트열로 구성되는 제3 데이타임) 승산하는 본 발명에 의한 몽고메리 모듈러 승산 장치는, 제1~제n+1 프로세서들로 구성되고, 제p+1(여기서, 1≤ p(정수) ≤ n+1) 프로세서는 제p 프로세서로부터 입력한 제어 신호에 응답하여, 제p 프로세서로부터 입력한 상기 Ai, Bi, Ni 및 이전 결과값(Ti)을 이용하여 임시 변수(M) 및 제1캐리(C=C1C0)를 다음 식에 따라 계산하고 상기 Ai를 A로서 저장하며 상기 M 및 상기 C를 저장하거나, 저장한 상기 A, M 및 C와 상기 제p 프로세서로부터 입력한 상기 Ai,Bi, Ni 및 상기 이전 결과값을 이용하여 제2 캐리(C'=C1'C0') 및 현재 결과값(Ti')를 다음 식에 따라 계산하며, 이전 결과값(Ti) 또는 현재 결과값(Ti')과 입력한 Ai를 제p+2 프로세서로 출력하고 상기 제어 신호, Bi 및 Ni들을 소정 시간 지연후에 상기 제p+2 프로세서로 출력하고, 상기 제1 프로세서로 입력되는 상기 이전 결과값(T)과 상기 제어신호의 최하위 비트를 제외한 비트들은 모든 비트들은 "저" 논리 레벨이고, 상기 제1 프로세서는 상기제어 신호를 외부로부터 입력하고, 상기 제n+1 프로세서로부터 출력되며 n+m+1 비트열로 구성되는 상기현재 결과값들은 상기 제1 데이타와 상기 제2 데이타를 몽고메리 모듈러 N 승산한 결과인 것이 바람직하다.M=(Ti + Ai × Bi) MOD r(여기서, r은 소정수이다.)C = Ti + Ai × Bi + M × Ni(여기서, C0은 C DIV r MOD r이고, C1은 C DIV r DIV r이다.)C'= Ti + A × Bi + M × Ni + C0 + C1 × r(여기서, C0'는 C' DIV r MOD r이고, C1'는 C' DIV r DIV r이다.)Ti' = (Ti + A × Bi + M × Ni + C0') MOD r