일반기술

확장체에서 다항식 곱셈장치 및 방법

확장체에서 다항식 곱셈장치 및 방법이 개시된다. 검색부는 소정의 분할차수 S에 대해 입력된 확장체의 차수 n이 하위경계값 Sk-1와 상위경계값 Sk 사이에 존재하도록 하는 k를 검색한다. 상태값결정부는 하위경계값 Sk-1과 상위경계값 Sk 사이의 구간을 하위경계값 Sk-1보다 크고 상위경계값 Sk보다 작은 복수의 분할값에 의해 분할하여 형성된 복수의 분할구간 중에서 확장체의 차수 n이 속하는 분할구간의 상위경계값을 상태값으로 결정한다. 최적차수결정부는 수학식 n'=State·Sk-2에 의해 얻어진 값을 최적의 확장체 차수로 결정한다. 여기서, n'는 최적의 확장체 차수이고, State는 상태값을 의미한다.본 발명에 따르면, 확장체의 차수가 비교적 큰 경우에도 불구하고 계수-곱셈의 경우 3배 이상 연산량을 줄일 수 있다.본 발명은 확장체에서 다항식 곱셈장치 및 방법에 관한 것으로, 보다 상세하게는, 다중분할 카라슈바 방법에 의한 다항식곱셈을 효율적으로 수행할 수 있는 다항식 곱셈장치 및 방법에 관한 것이다.인수분해 문제, 이산대수 문제 등을 기반으로 하는 대다수의 공개키 암호 시스템은 지수 연산을 기반으로 한다. 지수 연산은 알고리즘에 따라 장단점을 가지며, 이들 알고리즘의 효율성은 곱셈 연산의 연산량을 기준으로 한다. 따라서 유한체 곱셈 연산의 효율적인 구성은 하드웨어 및 소프트웨어 분야에서 오랜 기간 동안 화제가 되어왔으며 현재까지도 활발히 연구중이다. 알고리즘의 효율성은 자원의 사용이나 복잡도 등이 기준이 되며 이중에서 복잡도는 알고리즘의 가치를 판단하는가장 큰 기준이다. 일반적으로 유한체의 크기를 n이라 하면 대략의 복잡도를 O(n)등으로 표현한다.