$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

불필요한 연산이 없는 카라슈바 알고리즘과 하드웨어 구조

An Efficient Architecture for Modified Karatsuba-Ofman Algorithm

초록

Divide-and-Conquer방법은 병렬 곱셈기의 구성에 잘 적용되며 가장 대표적으로 카라슈바 방법이 있다. Leone은 최적 반복 회수를 카라슈바 알고리즘에 적용하였으며 Ernst는 다중 분할 카라슈바 방법을 제안하였다. 본 논문에서는 카라슈바 알고리즘에서 불필요한 연산이 제거된 불필요한 연산이 없는 카라슈바 알고리즘과 효율적인 하드웨어 구조를 제안한다. 본 논문에서 제안하는 알고리즘은 기존의 카라슈바 알고리즘에 비교하여 같은 시간 복잡도를 가지나 공간 복잡도를 효율적으로 감소시킨다. 특히 확장체의 차수 n이 홀수 및 소수일 때 더 효율적이며 최대 43%까지 공간 복잡도를 줄일 수 있다.

Abstract

In this paper we propose the Modified Karatsuba-Ofman algorithm for polynomial multiplication to polynomials of arbitrary degree. Leone proposed optimal stop condition for iteration of Karatsuba-Ofman algorithm(KO). In this paper, we propose a Non-Redundant Karatsuba-Ofman algorithm (NRKOA) with removing redundancy operations, and design a parallel hardware architecture based on the proposed algorithm. Comparing with existing related Karatsuba architectures with the same time complexity, the proposed architecture reduces the area complexity. Furthermore, the space complexity of the proposed multiplier is reduced by 43% in the best case.

참고문헌 (8)

  1. 장남수, 한동국, 정석원, 김창한, '유한체 GF($2^N$)에서 낮은 공간 복잡도를 가지는 새로운 다중 분할 카라슈바 방법의 병렬 처리 곱셈기', 대한전자공학회논문지(SC), 41. 1, pp.33-40, 2004 
  2. 장남수, 김창한, '확장체 GF($P^n$)에서 효율적인 다항식 곱셈 방법', 대한전자공학회논문지(SD), 42. 5, pp.23-30, 2005 
  3. G. Drolet, 'A New Representation of Elements of Finite Fields GF($2^m$) Yielding Small Complexity Arithmetic circuit}, IEEE Trans. on Computers, vol 47, 1998, 353-356 
  4. M. Ernst, M. Jung, F. Madlener, S. Huss, and R. Blumel, 'A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF($2^n$)', In Work shop on Cryptographic Hardware and Embedded Systems (CHES'02), LNCS2523, (2002), 381-399 
  5. N. Koblitz, 'Elliptic Curve Cryptosysterns', Mathematics of Computation, vol. 48, 1987, 203-209 
  6. M. Leone, 'A New Low Complexity Parallel Multiplier for a Class of Finite Fields', In Workshop on Cryptographic Hardware and Embedded Systems (CHES'01), LNCS2162, (2001), 160-170 
  7. C. Paar, 'A new architecture for a parallel finite fields multiplier with Low Complexity Based on Composite Fields', IEEE Trans. on Computers, vol45, no.7, July 1996, 846-861 
  8. F. Rodriguez-Henriquez and C. K. Koc, 'On fully parallel Karatsuba multipliers for GF($2^m)', Proceedings of the international Conference on Computer Science and Technology -CST 2003, Acta Press, Cancun, Mexico, May 2003, 405-410 

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일