| 1 |
1
승수 A, 피승수 B, 모듈러스 N에 대한 모듈러 곱셈 결과값 R을 구하는 워드 기반의 몽고메리 모듈러 곱셈 연산 방법에 있어서,상기 R을 합(S)과 캐리(C)로 구분하여 초기화하는 제1단계;상기 B의 워드 순서 i에 대한 루프를 시작하는 제2단계;상기 i 루프 내에서 상기 A의 워드 순서 j에 대한 루프를 시작하고, 상기 R을 초기화하는 제3단계;상기 j 루프 내에서 상기 A 및 상기 B에 대한 워드 단위의 모듈러 곱셈을 수행하는 제4단계;상기 j 루프 내에서 워드 단위의 덧셈을 최대 3번 수행하는 제5단계;상기 j 루프 및 상기 i 루프를 종료하고 워드 단위의 덧셈을 2번 하는 제6단계; 및최종 결과값(T)이 상기 N보다 크면 최종 결과값에서 상기 N을 뺀 값을 출력하고, 최종 결과값(T)이 상기 N보다 작으면 최종 결과값을 리턴하는 제7단계를 포함하는 모듈라 곱셈 연산 방법
|
| 2 |
2
제1항에 있어서, 상기 제3단계는,상기 i가 상기 B의 첫 번째 워드의 연산을 가리키면(i=0) 상기 R의 초기값을 (S, C)=(0, 0)으로 설정하는 단계;상기 i가 0이 아니고 상기 j가 A의 마지막 워드의 연산을 가리키지 않으면(j≠p-1), 상기 R의 초기값을 (Tj, 0)으로 설정하는 단계;상기 j가 p-1이고, 상기 A의 마지막 워드 연산에 오버플로우가 발생하면, 상기 R의 초기값을 (Tj, 111…1)으로 설정하는 단계;상기 j가 p-1이고, 상기 A의 마지막 워드 연산에 오버플로우가 발생하지 않으면, 상기 A의 마지막 워드 연산의 쉬프트 연산에 오버플로우가 발생하는지 확인하는 단계;상기 A의 마지막 워드 연산의 쉬프트 연산에 오버플로우가 발생한 경우, 상기 R의 초기값을 (1, 111…1)으로 설정하는 단계; 및상기 A의 마지막 워드 연산의 쉬프트 연산에 오버플로우가 발생하지 않은 경우, 상기 R의 초기값을 (Tj, 0)으로 설정하는 단계를 포함하는 모듈라 곱셈 연산 방법
|
| 3 |
3
제2항에 있어서, 상기 제4단계의 모듈러 곱셈 연산은캐리 저장 가산 방법에 의해 두 번의 덧셈 연산을 수행하는 단계; 및상기 R과, 쉬프트 연산을 위한 인자 shift_data와, 몽고메리 보정 인자 m을 산출하는 단계를 포함하는 모듈라 곱셈 연산 방법
|
| 4 |
4
제3항에 있어서, 상기 제5단계는상기 제4단계의 출력 R을 입력으로 하여 S, C, 선 캐리 인자(pre_c)을 합산하고 (pre_c, Tj)를 출력하는 제1 덧셈 단계를 포함하는 모듈라 곱셈 연산 방법
|
| 5 |
5
제4항에 있어서, 상기 제5단계는상기 j가 p-1이면, 상기 A의 마지막 워드에 대한 연산의 오버플로우 발생 여부 확인 인자(check_ovf0)를 상기 pre_c로 설정하고,상기 j가 0이면, 상기 shift_data를 상기 pre_c로 설정하며,상기 제1 덧셈 단계의 출력 Tj-1를 입력으로 하여 Tj-1, shift_data, 다음 캐리 인자(next_c)을 합산하고 (next_c, Tj-1)을 출력하는 제2 덧셈 단계를 포함하는 모듈라 곱셈 연산 방법
|
| 6 |
6
제5항에 있어서, 상기 제5단계는상기 제 2 덧셈 단계가 상기 A의 마지막 워드에 대한 최종 중간값 덧셈인 경우(j=0, i≠0), 상기 A의 마지막 워드에 대한 최종 중간값 덧셈의 오버플로우 발생 여부 확인 인자(check_ovf1)를 상기 next_c로 설정하고,상기 제 2 덧셈 단계가 최종 결과값 덧셈인 경우(i=p-1, j≠0), 상기 제2 덧셈 단계에서 출력된 Tj-1을 입력으로 하여 Tj-1, Nj-1의 1의 보수(~Nj-1), sign_c 를 합산하고 (sign_c, T’j-1)을 출력하는 제3 덧셈 단계를 포함하는 모듈라 곱셈 연산 방법
|
| 7 |
7
제6항에 있어서, 상기 제5단계는A*Bi 열의 곱셈이 종료되지 않은 경우(j≠p-1), 상기 제3단계로 복귀하는 단계;j= p-1이고, i≠ p-1인 경우, 상기 제 2단계로 복귀하는 단계; 및j= p-1이고, i= p-1인 경우, 상기 i 루프 및 j 루프를 빠져나오는 단계를 더 포함하는 모듈라 곱셈 연산 방법
|
| 8 |
8
제7항에 있어서,최종 결과값의 마지막 워드(Tp-1)를 구하기 위해 Tp-1, next_c 를 합산하고 (next_c, Tp-1)을 출력하는 제1 덧셈 단계;상기 출력된 next_c를 상기 check_ovf1으로 설정하고, 상기 출력된 Tp-1을 입력으로 하여 Tp-1, ~Np-1, 및 sign_c 를 합산하고 (sign_c, T’p-1)을 출력하는 제2 덧셈 단계; 및check_ovf0 | check_ovf1 | c_sign 연산의 결과값을, 최종 결과값이 N보다 큰 값인지를 확인하기 위한 check_sign으로 설정하는 단계를 더 포함하는 모듈라 곱셈 연산 방법
|
| 9 |
9
승수 A, 피승수 B, 모듈러스 N에 대한 모듈러 곱셈 결과값 R을 구하는 워드 기반의 몽고메리 모듈러 곱셈 연산 장치에 있어서,상기 R을 합(S)과 캐리(C)로 구분하여 초기화하고, 상기 B의 워드 순서 i에 대한 루프 및 상기 A의 워드 순서 j에 대한 루프를 시작하며, 초기화된 상기 R을 이용하여 상기 j 루프 내에서 상기 A 및 상기 B에 대한 워드 단위의 모듈러 곱셈을 수행하고, 최종 결과값(T)이 상기 N보다 크면 최종 결과값에서 상기 N을 뺀 값을 출력하고, 최종 결과값(T)이 상기 N보다 작으면 최종 결과값을 리턴하는 연산부; 및상기 j 루프 내에서 워드 단위의 덧셈을 최대 3번 수행하고, 상기 j 루프 및 상기 i 루프를 종료하고 워드 단위의 덧셈을 2번 하는가산부를 포함하는 모듈러 곱셈 연산 장치
|
