초록 ▼

본 발명은 카라슈바 곱셈기에 관한 것으로, 특히 기존의 이진체에서 정의된 타원곡선의 카라슈바 병렬 곱셈기가 가지는 불필요한 연산을 제거함으로써 공간 복잡도와 시간 복잡도를 줄이기 위해, 기존의 카라슈바 알고리즘에 NRKOA(Non-Redundant Karatsuba-Ofman Algorithm) 알고리즘을 결합함으로써, 불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법을 제공하는데 그 목적이 있다. 따라서 공간 복잡도에서 효율성을 가지는 효과가 있으며, 이로 인해 낮은 공간 복잡도가 요구되는 스마트 카드, 모바일 디바이스 등에 효율

본 발명은 카라슈바 곱셈기에 관한 것으로, 특히 기존의 이진체에서 정의된 타원곡선의 카라슈바 병렬 곱셈기가 가지는 불필요한 연산을 제거함으로써 공간 복잡도와 시간 복잡도를 줄이기 위해, 기존의 카라슈바 알고리즘에 NRKOA(Non-Redundant Karatsuba-Ofman Algorithm) 알고리즘을 결합함으로써, 불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법을 제공하는데 그 목적이 있다. 따라서 공간 복잡도에서 효율성을 가지는 효과가 있으며, 이로 인해 낮은 공간 복잡도가 요구되는 스마트 카드, 모바일 디바이스 등에 효율적으로 적용될 수 있는 효과가 있다.

대표청구항 ▼

불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법에 있어서,입력되는 값의 차수를 확인하는 제 1 단계;상기 제 1 단계에서 차수가 7 이상이면, 입력값() 및 연산을 위한 계수에 관한 초기화를 수행하는 제 2 단계;상기 제 2 단계의 초기화가 완료되면, 상기 입력값에 대한 사전 덧셈 연산을 수행하여 상기 각각의 입력값에 대한 합을 구하는 제 3 단계;상기 입력값에 대한 합을 구한 후, NRHKOA(NON-REDUNDANT KARATSUBA-OFMAN ALGORITHM) 연산을 수행하여 의 값을 구하는 제4 단계; 및상기 제 1 단계

불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법에 있어서,입력되는 값의 차수를 확인하는 제 1 단계;상기 제 1 단계에서 차수가 7 이상이면, 입력값() 및 연산을 위한 계수에 관한 초기화를 수행하는 제 2 단계;상기 제 2 단계의 초기화가 완료되면, 상기 입력값에 대한 사전 덧셈 연산을 수행하여 상기 각각의 입력값에 대한 합을 구하는 제 3 단계;상기 입력값에 대한 합을 구한 후, NRHKOA(NON-REDUNDANT KARATSUBA-OFMAN ALGORITHM) 연산을 수행하여 의 값을 구하는 제4 단계; 및상기 제 1 단계 내지 제 4 단계를 통해 얻어진 을 입력값으로 대치하여 상기 제 2 단계로 진행하여 상기 제 2 단계 이하의 과정을 재귀반복함으로써 출력을 구하는 제 5 단계를 포함하는 불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법.제 1 항에 있어서,상기 제 5단계의 출력은 <수학식 13>과 같음을 특징으로 하는 불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법.제 1 항 또는 제 2 항에 있어서,상기 제 3 단계의 입력값에 대한 합은, <수학식 14>와 <수학식 15>를 통해 이루어지는 것을 특징으로 하는 불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법.여기서, I는 0부터 M2-1까지의 값으로 변화됨.제 3 항에 있어서,상기 제 4 단계의 NRHKOA 연산은, <표 7>을 통해 그 결과를 제공하는 것을 특징으로 하는 불필요한 연산을 줄이도록 하는 카라슈바 곱셈 방법.