http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
인수분해 공식과 정규기저를 이용한 상의 고속 곱셈 역원 연산 알고리즘
장용희(Yong-Hee Jang),권용진(Yong-Jin Kwon) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.5·6
The public-key cryptosystems such as Diffie-Hellman Key Distribution and Elliptical Curve Cryptosystems are built on the basis of the operations defined in :addition, subtraction, multiplication and multiplicative inversion. It is important that these operations should be computed at high speed in order to implement these cryptosystems efficiently. Among those operations, as being the most time-consuming, multiplicative inversion has become the object of lots of investigation. Fermant's theorem says , whereis the multiplicative inverse of . Therefore, to compute the multiplicative inverse of arbitrary elements of , it is most important to reduce the number of times of multiplication by decomposingefficiently. Among many algorithms relevant to the subject, the algorithm proposed by Itoh and Tsujii[2] has reduced the required number of times of multiplication toby using normal basis. Furthermore, a few papers have presented algorithms improving the Itoh and Tsujii's. However they have some demerits such as complicated decomposition processes[3,5]. In this paper, in the case of , which is mainly used in practical applications, an efficient algorithm is proposed for computing the multiplicative inverse at high speed by using both the factorization formulaand normal basis. The number of times of multiplication of the algorithm is smaller than that of the algorithm proposed by Itoh and Tsujii. Also the algorithm decomposesmore simply than other proposed algorithms. Diffie-Hellman 키분배 시스템과 타원곡선 암호시스템과 같은 공개키 기반 암호시스템은상에서 정의된 연산, 즉 덧셈, 뺄셈, 곱셈 및 곱셈 역원 연산을 기반으로 구축되며, 이들 암호시스템을 효율적으로 구현하기 위해서는 위 연산들을 고속으로 계산하는 것이 중요하다. 그 중에서 곱셈 역원이 가장 time-consuming하여 많은 연구 대상이 되고 있다. Fermat 정리에 의해 의 곱셈 역원 은 이므로 의 임의의 원소에 대해 곱셈 역원을 고속으로 계산하기 위해서는, 을 효율적으로 분해하여 곱셈 횟수를 감소시키는 것이 가장 중요하며, 이와 관련된 알고리즘들이 많이 제안되어 왔다. 이 중 Itoh와 Tsujii가 제안한 알고리즘[2]은 정규기저를 사용해서 필요한 곱셈 횟수를 까지 감소시켰으며, 또한 이 알고리즘을 향상시킨 몇몇 알고리즘들이 제안되었지만, 분해과정이 복잡하다는 등의 단점이 있다[3,5]. 본 논문에서는 실제 어플리케이션에서 주로 많이 사용되는 인 경우에, 인수분해 공식 와 정규기저를 이용해서 곱셈 역원을 고속으로 계산하는 알고리즘을 제안한다. 본 논문의 알고리즘은 곱셈 횟수가 Itoh와 Tsujii가 제안한 알고리즘 보다 적으며, 의 분해가 기존의 알고리즘 보다 간단하다.
Filtering 함수를 이용한 효율적인 논리함수 처리
장용희(Jang Yong-hee),권용진(Kwon Yong-jin) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.2B
논리함수를 효율적으로 처리하기 위한 내부데이터 표현방식에 관한 많은 연구가 있어 왔다. 그러나 기존의 논리함수를 표현하고 처리하는 수법들, Truth tables, Parse trees, Cube sets등은 VLSI설계와 같은 대규모 조합문제를 처리하는데 있어서 많은 문제를 내포하고 있다. 그래서 기존의 수법들을 보완한 최근의 연구중의 하나로 이분결정도(Binary Decision Diagrams, BDD'S)가 있다. 이분결정도는 논리함수의 그래프적 표현법으로서 논리함수를 효율적으로 처리할 수 있는 특성[1][2][3]을 가지고 있음이 알려져 있다. 그러나 이분결정도의 크기와 계산기의 계산한계를 초월해서 계산이 불가능한 경우가 종종 발생된다. 이와 같은 문제를 해결하기 위해서 본 논문에서는 논리함수에 대한 내부 데이터 표현방식으로 이분결정도를 채용할 경우에 효과적으로 이분결정도의 크기를 줄이는 방안으로서 filtering 수법을 제안해서 이분결정도의 패키지안에 포함시켰다. 또한 비동기 순서 회로(Asynchronous sequential circuits)의 One-Shot 상태할당문제에 적용하여 논리함수의 내부 데이터 표현방식으로 이분결정도를 사용할 경우 filtering 수법이 이분결정도의 크기 감소에 효과적임을 실험결과를 통해서 보인다.
All - One Polynomial에 의해 정의된 유한체 GF(2m) 상의 새로운 Low - Complexity Bit - Parallel 정규기저 곱셈기
장용희(Yong-Hee Jang),권용진(Yong-Jin Kwon) 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.1·2
대부분의 공개키 기반 암호시스템은 유한체 GF(2^m) 상의 산술 연산들을 기반으로 구축된다. 이들 연산 중 덧셈을 제외한 다른 연산들은 곱셈 연산을 반복하여 계산되므로, 곱셈 연산의 효율적인 구현은 공개키 기반 암호시스템에서 매우 중요하다. 본 논문에서는 All-One Polynomial에 의해 정의된 GF(2^m) 상의 효율적인 Bit-Parallel 정규기저 곱셈기를 제안한다. 게이트 및 시간적인 면에서 본 곱셈기의 복잡도(complexity)는 이전에 제안된 같은 종류의 곱셈기 보다 낮거나 동일하다. 또한, 본 논문의 곱셈기는 아키텍처가 규칙적(regular)이어서 VLSI 구현에 적합하다. Most of pubic-key cryptosystems are built on the basis of arithmetic operations defined over the finite field GF( 2^m) . The other operations of finite fields except addition can be computed by repeated multiplications. Therefore, it is very important to implement the multiplication operation efficiently in public-key cryptosystems. We propose an efficient bit-parallel normal basis multiplier for GF(2^m) fields defined by All-One Polynomials. The gate count and time complexities of our proposed multiplier are lower than or equal to those of the previously proposed multipliers of the same class. Also, since the architecture of our multiplier is regular, it is suitable for VLSI implementation.
All - One 다항식에 의해 정의된 유한체 GF(2m) 상의 효율적인 Bit - Parallel 정규기저 곱셈기
장용희(Yong-Hee Jang),권용진(Yong-Jin Kwon) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A
유한체 GF(2^m) 상의 산술 연산 중 곱셈 연산의 효율적인 구현은 암호이론 분야의 어플리케이션에서 매우 중요하다. 본 논문에서는 All-One 다항식에 의해 정의된 GF(2^m) 상의 효율적인 Bit-Parallel 정규기저 곱셈기를 제안한다. 게이트 및 시간 면에서 본 논문의 곱셈기의 complexity는 이전에 제안된 같은 종류의 곱셈기 보다 낮거나 동일하다. 그리고 본 논문의 곱셈기는 이전 곱셈기 보다 더 효율적이어서 VLSI 구현에 적합하다.