1 |
1
유한체 GF(2m)의 원소인 제1다항식 A(x)와 소정의 m차 기약다항식인 제2다항식 G(x)를 입력으로 하고, 상기 제1다항식과 상기 제2다항식을 각각 소정의 제1내부변수 및 제2내부변수의 초기값으로 설정한 후 교환연산제어변수, 상기 제1내부변수의 최하위비트값, 및 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값의 동일여부에 따라 상기 제1내부변수가 1이 될 때까지 상기 제1내부변수와 상기 제2내부변수에 대한 교환연산, 쉬프트연산, 및 덧셈연산을 선택적으로 반복수행하는 제1연산부; 상기 교환연산제어변수, 상기 제1내부변수의 최하위비트값, 및 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값의 동일여부에 따라 상기 제1내부변수가 1이 될 때까지 소정의 초기값이 설정된 제3내부변수 및 제4내부변수에 대한 교환연산, 쉬프트연산, 및 덧셈연산을 선택적으로 반복수행하며, 상기 덧셈연산을 수행하는 동안 상기 제2다항식에 대해 G(x)/x 및 (G+Gx)/x 연산을 수행하여 얻어진 G(x), G(x)/x, 및 (G+Gx)/x 중에서 선택된 제3다항식과 상기 제4내부변수의 값을 합산하여 모듈러 감산 연산을 수행하는 제2연산부; 상기 교환연산제어변수, 상기 제1내부변수의 최하위비트값, 및 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값의 동일여부에 따라 상기 제1연산부 및 상기 제2연산부의 동작을 제어하며, 상기 제1내부변수가 1이 되면 상기 제3내부변수를 상기 제1다항식의 역원으로 출력하는 제어부; 및 상기 교환연산제어변수가 저장되는 제어값저장부;를 포함하는 것을 특징으로 하는 유한체에서의 역원 연산 장치
|
2 |
2
제 1항에 있어서, 상기 제1연산부는, 상기 제1내부변수가 저장되는 제1레지스터; 상기 제2내부변수가 저장되는 제2레지스터; 상기 제1레지스터 및 상기 제2레지스터로부터 입력받은 상기 제1내부변수 및 상기 제2내부변수를 가산하여 출력하는 제1가산기; 상기 제1레지스터로부터 입력받은 상기 제1내부변수, 상기 제2레지스터로부터 입력받은 상기 제2내부변수, 및 상기 제1가산기로부터 입력받은 값 중에서 하나의 값을 선택하여 출력하는 제1먹스; 및 상기 제1먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시켜 출력하는 제1쉬프터;를 포함하며, 상기 제어부는 상기 제1내부변수의 최하위비트값이 0이면, 상기 제1먹스가 상기 제1내부변수를 선택하여 출력하도록 제어하고, 상기 제1내부변수의 최하위비트값이 0이 아니면, 상기 제1먹스가 상기 제1가산기로부터 입력되는 값을 선택하여 출력하도록 제어하며, 상기 제어부는 상기 제1내부변수의 최하위비트값이 0이 아닌 경우에 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 동일하면 상기 제1쉬프터가 상기 제1먹스로부터 입력되는 값을 하위비트방향으로 2비트 이동시킨 후 상기 제1레지스터에 저장하도록 제어하고, 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 상이하면 상기 제1쉬프터가 상기 제1먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시킨 후 상기 제1레지스터에 저장하도록 제어한 후 연속적으로 상기 제1쉬프터가 상기 제1먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시킨 후 상기 제1레지스터에 저장하도록 제어하는 것을 특징으로 하는 유한체에서의 역원 연산 장치
|
3 |
3
제 2항에 있어서, 상기 제어부는 상기 교환연산제어변수가 0보다 작으면 상기 제1내부변수값 및 상기 제2내부변수값을 교환하여 각각 상기 제2레지스터 및 상기 제1레지스터에 저장하도록 제어하고, 상기 교환연산제어변수의 부호를 변경하며, 상기 교환연산제어변수는 다음과 같이 정의되는 것을 특징으로 하는 유한체에서의 역원 연산 장치: δ=α-β, 여기서, δ는 상기 교환연산제어변수이고, α 및 β는 각각 |제1내부변수|≤xα와 |제2내부변수|≤xβ를 만족하는 값이다
|
4 |
4
제 1항 또는 제 2항에 있어서, 상기 제2연산부는, 상기 제3내부변수가 저장되는 제3레지스터; 상기 제4내부변수가 저장되는 제4레지스터; 상기 제3내부변수의 하위 2비트값에 따라 상기 G(x), G(x)/x, 및 (G+Gx)/x 중에서 하나를 상기 제3다항식으로 선택하여 출력하는 제2먹스; 상기 제4레지스터로부터 입력받은 상기 제4내부변수와 상기 제2먹스로부터 입력받은 상기 제3다항식을 합산하여 출력하는 제2가산기; 상기 제2가산기로부터 입력받은 값, 상기 제2다항식, 및 상기 제4레지스터로부터 입력받은 상기 제4내부변수 중에서 하나의 값을 선택하여 출력하는 제3먹스; 상기 제3먹스로부터 입력받은 값과 상기 제3레지스터로부터 입력받은 상기 제3내부변수를 합산하여 출력하는 제3가산기; 상기 제3레지스터로부터 입력받은 상기 제3내부변수, 상기 제4레지스터로부터 입력받은 상기 제4내부변수, 및 상기 제3가산기로부터 입력받은 합산값 중에서 하나의 값을 선택하여 출력하는 제4먹스; 및 상기 제4먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시켜 출력하는 제2쉬프터;를 포함하며, 상기 제어부는 상기 제1내부변수의 최하위비트값이 0이면, 상기 제4먹스가 상기 제3내부변수를 선택하여 출력하도록 제어하고, 상기 제1내부변수의 최하위비트값이 0이 아니면, 상기 제4먹스가 상기 제4가산기로부터 입력되는 값을 선택하여 출력하도록 제어하고, 상기 제어부는 상기 제1내부변수의 최하위비트값이 0이 아닌 경우에 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 동일하면 상기 제2쉬프터가 상기 제4먹스로부터 입력되는 값을 하위비트방향으로 2비트 이동시킨 후 상기 제3레지스터에 저장하도록 제어하고, 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 상이하면 상기 제2쉬프터가 상기 제4먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시킨 후 상기 제3레지스터에 저장하도록 제어한 후 연속적으로 상기 제2쉬프터가 상기 제4먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시킨 후 상기 제3레지스터에 저장하도록 제어하는 것을 특징으로 하는 유한체에서의 역원 연산 장치
|
5 |
5
제 4항에 있어서, 상기 제어부는 상기 제1내부변수의 최하위비트값이 0이 아닌 경우에 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 상이하면 상기 제2쉬프터가 상기 제4먹스로부터 입력되는 값을 하위비트방향으로 1비트 이동시키는 과정을 수행하는 동안에 상기 제3가산기가 상기 제2먹스로부터 입력되는 값과 상기 제4레지스터로부터 입력되는 상기 제4내부변수값을 합산하도록 제어하는 것을 특징으로 하는 유한체에서의 역원 연산 장치
|
6 |
6
제 4항에 있어서, 상기 제어부는 상기 교환연산제어변수가 0보다 작으면 상기 제3내부변수값 및 상기 제4내부변수값을 교환하여 각각 상기 제4레지스터 및 상기 제3레지스터에 저장하도록 제어하고, 상기 교환연산제어변수의 부호를 변경하며, 상기 교환연산제어변수는 다음과 같이 정의되는 것을 특징으로 하는 유한체에서의 역원 연산 장치: δ=α-β, 여기서, δ는 상기 교환연산제어변수이고, α 및 β는 각각 |제1내부변수|≤xα와 |제2내부변수|≤xβ를 만족하는 값이다
|
7 |
7
유한체 GF(2m)의 원소인 제1다항식 A(x)와 소정의 m차 기약다항식인 제2다항식 G(x)를 각각 소정의 제1내부변수 및 제2내부변수의 초기값으로 설정하는 단계; 소정의 제3내부변수 및 제4내부변수의 초기값을 각각 1과 0으로 설정하는 단계; 소정의 교환연산제어변수가 0이면, 상기 제1내부변수를 하위비트 방향으로 1비트 이동시키고, 상기 제3내부변수를 하위비트 방향으로 1비트 이동시킨 후 상기 제2다항식과의 모듈러 연산을 수행하는 단계; 상기 교환연산제어변수가 0이 아닌 경우에 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 동일하면, 상기 제1내부변수를 상기 제1내부변수와 상기 제2내부변수의 합산값으로 변경하고, 상기 제3내부변수를 상기 제3내부변수와 상기 제4내부변수의 합산값으로 변경하는 단계; 상기 교환연산제어변수가 0이 아닌 경우에 상기 제1내부변수와 상기 제2내부변수의 최하위비트의 인접비트값이 상이하면, 상기 제1내부변수를 상기 제1내부변수, 상기 제2내부변수, 및 상기 제2내부변수와 x의 곱의 합산값으로 변경하고, 상기 제3내부변수를 상기 제3내부변수, 상기 제4내부변수, 및 상기 제4내부변수와 x의 곱의 합산값으로 변경하는 단계; 상기 제1내부변수를 하위비트 방향으로 2비트 이동시키고, 상기 제3내부변수를 하위비트방향으로 2비트 이동시킨 후 상기 제2다항식과의 모듈러 연산을 수행하며, 상기 교한연산제어변수의 값을 변경하는 단계; 및 상기 제1내부변수가 1이면 상기 제3내부변수를 상기 제1다항식의 역원으로 출력하는 단계;를 포함하는 것을 특징으로 하는 유한체에서의 역원 연산 방법
|
8 |
8
제 7항에 있어서, 상기 교환연산제어변수가 0보다 작으면 상기 제1내부변수값 및 상기 제2내부변수값을 교환하고, 상기 제3내부변수값 및 상기 제4내부변수값을 교환하며, 상기 교환연산제어변수의 부호를 변경하는 단계를 더 포함하며, 상기 교환연산제어변수는 다음과 같이 정의되는 것을 특징으로 하는 유한체에서의 역원 연산 방법: δ=α-β, 여기서, δ는 상기 교환연산제어변수이고, α 및 β는 각각 |제1내부변수|≤xα와 |제2내부변수|≤xβ를 만족하는 값이다
|
9 |
9
제 7항 또는 제 8항에 기재된 유한체에서의 역원 연산 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|
10 |
9
제 7항 또는 제 8항에 기재된 유한체에서의 역원 연산 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|