Massey-Omura 승산기를 위한 최적 정규원소
The Optimal Normal Elements for Massey-Omura Multiplier
0
조회
0
다운로드
0
인용
0
참고문헌
초록
유한체의 곱셈과 나눗셈은 오류정정부호와 암호시스템에서 중요한 산술 연산이다. 유한체 의 원소를 표현하기 위해 다양한 기저가 사용되며 차수가 인 상의 원시다항식으로 구성할 수 있다. 정규기저를 사용하면 곱셈이나 곱셈 역원의 연산을 쉽게 수행할 수 있다. 정규기저 표현을 이용하는 Massey-Omura 승산기는 동일한 2진함수를 사용하여 몇 번의 순회치환으로 곱셈 또는 나눗셈이 수행되며 논리함수의 곱셈항 수가 승산기의 복잡도를 결정한다. 유한체의 정규기저는 항상 존재한다. 그러나 주어진 원시다항식에 대해 최적의 정규원소를 구하는 것은 쉽지 않다. 본 논문에서는 정규기저의 생성 방법을 고찰하고, Massey-Omura 승산기를 이용한 곱셈 또는 곱셈 역원의 계산에서 연산의 복잡도를 최소화할 수 있는 정규기저를 각 원시다항식에 대해 구하여, 최적의 정규원소와 곱셈항의 개수를 제시한다.
Abstract
Finite field multiplication and division are important arithmetic operation in error-correcting codes and cryptosystems. The elements of the finite field are represented by bases with a primitive polynomial of degree over . We can be easily realized for multiplication or computing multiplicative inverse in based on a normal basis representation. The number of product terms of logic function determines a complexity of the Messay-Omura multiplier. A normal basis exists for every finite field. It is not easy to find the optimal normal element for a given primitive polynomial. In this paper, the generating method of normal basis is investigated. The normal bases whose product terms are less than other bases for multiplication in are found. For each primitive polynomial, a list of normal elements and number of product terms are presented.
참고문헌 (12)
- "Bit-Serial Reed-Solomon Encoder", 28, pp.869~874 (1982)
- "VLSI Architectures for Computing Multiplications and Inverses in GF", pp.709~716 (1985)
- "A Fast Algorithm for Computing Multiplicative Inverses in GF", using(rmal bases), pp.31~36 (1986)
- "유한체 GF상에서의 빠른 역원계산 기법", 6(1), pp.145~150 (1996)
- "GF 에서 정규기저를 이용한 고속 곱셈 역원 연산 방법", 13(2), pp.127~132 (2003)
- "Improved Normal Basis Inversion in GF", 33(3), pp.196~197 (1997)
- "Normal Basis of the Finite Field over", 43(2), pp.737~739 (1997)
- "Normal Basis Inversion in Some Finite Fields", pp.701~703
- "Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields GF", 41, pp.962~971 (1993)
- "Normal Bases over Finite Fields thesis for Ph. D. in Combinatorics and Optimization the University of Waterloo" (1993)
- "A New Hardware Architecture for Operation in GF", 51(1), pp.90~92 (2002)
- "Error Control Systems for Digital Communication and Storage" (1995), Prentice-Hall, Englewood Cliffs