유한체 $GF(2^n)$에서 두 원소의 곱셈을 수행하는 공간 복잡도가 낮은 병렬 처리 곱셈기의 구현에 있어서 divide-and-conquer 방법은 유용하게 사용된다. 이를 이용한 가장 널리 알려진 알고리듬으로는 카라슈바 (Karatsuba-Ofman) 알고리듬과 다중 분할 카라슈바(Multi-Segment Karatsuba) 알고리듬이 있다. Leo ne은 카라슈바 알고리듬의 최적화된 반복 횟수를 제안하였고, Ernst는 다중 분할 카라슈바 방법을 이용한 일반적이고 확장 가능한 유한체 곱셈기를 제안하였다. 본 논문에서는 Ernst가 제시한 다중 분할 카라슈바 병렬 처리 곱셈기의 복잡도를 제시한다. 또한 기존 방법의 병렬 처리 곱셈기와 시간 복잡도는 같지만 공간 복잡도는 낮은 새로운 다중 분할 카라슈바 방법의 병렬 처리 곱셈기를 제안하며 그에 따른 최적화된 반복 횟수를 제안한다. 나아가서 제안하는 곱셈기가 몇몇 유한체에서 카라슈바 방법의 병렬 처리 곱셈기 보다 공간 복잡도에서 효과적임을 제시한다.
The divide-and-conquer method is efficiently used in parallel multiplier over finite field $GF(2^n)$. Leone Proposed optimal stop condition for iteration of Karatsuba-Ofman algerian(KOA). Ernst et al. suggested Multi-Segment Karatsuba(MSK) method. In this paper, we analyze the complexity of a parallel MSK multiplier based on the method. We propose a new parallel MSK multiplier whose space complexity is same to each other. Additionally, we propose optimal stop condition for iteration of the new MSK method. In some finite fields, our proposed multiplier is more efficient than the KOA.
