1 |
1
유한체 다항식 나눗셈 장치에 있어서: 입력 값인 제수 다항식, 피제수 다항식, 기약 다항식를 저장하고, 상기 다항식의 나눗셈 연산의 결과값을 저장하며, 상기 나눗셈 연산을 수행하기 위한 중간 계산값을 저장하는 레지스터부; 상기 레지스터부의 저장값에 대한 배타적 논리합을 수행하는 배타적 논리합 연산부; 상기 레지스터부의 저장값 그리고/또는 상기 배타적 논리합 연산부의 결과값에 대하여 쉬프트 연산을 수행하는 쉬프트 연산부; 상기 제수 다항식 그리고/또는 상기 레지스터부의 저장값의 차수를 구하는 차수 검색부; 및 상기 레지스터부와 쉬프트 연산부의 입력 선택 신호를 생성하기 위하여 상기 레지스터부의 저장값의 차수(order)를 비교하는 차수 비교부를 포함함을 특징으로 하는 유한체 다항식 나눗셈 장치
|
2 |
2
제 1 항에 있어서, 상기 레지스터부는, 상기 제수 다항식을 초기 설정값으로 저장하고, 상기 쉬프트 연산부의 중간 결과값을 저장하는 제1 레지스터; 상기 기약 다항식을 초기 설정값으로 저장하고, 상기 제 1레지스터의 중간 결과값을 저장하는 제2 레지스터; 상기 피제수 다항식을 초기 설정값으로 저장하고, 상기 쉬프트 연산부의 중간 결과값을 저장하고, 상기 다항식의 나눗셈 연산의 결과값을 저장하는 제3 레지스터; 상기 제3 레지스터의 중간 결과값을 저장하는 제4 레지스터; 및 상기 제1 내지 제4 레지스터의 입력을 선택하는 다중화기를 포함함을 특징으로 하는 유한체 다항식 나눗셈 장치
|
3 |
3
제 1 항 또는 제 2 항에 있어서, 상기 배타적 논리합 연산부는, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값에 대한 배타적 논리합 연산을 수행하는 제1 배타적 논리합 연산기; 상기 제3 레지스터의 저장값과 상기 기약 다항식에 대한 배타적 논리합 연산을 수행하는 제2 배타적 논리합 연산기; 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값에 대한 배타적 논리합 연산을 수행하는 제3 배타적 논리합 연산기; 및 상기 제3 배타적 논리합 연산기의 결과값과 상기 기약 다항식에 대한 배타적 논리합 연산을 수행하는 제4 배타적 논리합 연산기를 포함함을 특징으로 하는 유한체 다항식 나눗셈 장치
|
4 |
4
제 1 항 또는 제 2 항에 있어서, 상기 쉬프트 연산부는, 상기 제1 레지스터의 저장값 또는 상기 제1 배타적 논리합 연산기의 결과값에 대한 우측 쉬프트 연산을 수행하는 제1 우측 쉬프트기; 상기 제3 레지스터의 저장값 또는 상기 제2 배타적 논리합 연산기의 결과값 또는 상기 제3 배타적 논리합 연산부의 결과값 또는 상기 제4 배타적 논리합 연산기의 결과값에 대한 우측 쉬프트 연산을 수행하는 제2 우측 쉬프트기; 및 상기 제1 우측 쉬프트기 및 제2 우측 쉬프트기의 입력을 선택하는 다중화기를 포함함을 특징으로 하는 유한체 다항식 나눗셈 장치
|
5 |
5
제 1 항에 있어서, 상기 차수의 비교는, 제1 카운터에 피제수 다항식의 차수를 저장하고, 제2 카운터에 기약다항식의 차수를 저장하며; 상기 제1 카운터가 0이 아니고, 상기 제1 레지스터의 최하위 비트가 0일 때, 상기 제1 카운터를 감소시키며; 상기 제1 카운터가 0이 아니고, 상기 제1 레지스터의 최하위 비트가 0이 아니고, 상기 제1 카운터가 상기 제2 카운터보다 작으면, 상기 제1 카운터와 상기 제2 카운터의 저장값을 교환하고, 상기 제1 카운터를 감소시키며; 상기 제1 카운터가 0이 아니고, 상기 제1 레지스터의 최하위 비트가 0이 아니고, 상기 제1 카운터가 상기 제2 카운터보다 클 때, 상기 제1 카운터를 감소시키며; 상기 제1 카운터가 0이 아니고, 상기 제1 레지스터의 최하위 비트가 0이 아니고, 상기 제1 카운터가 상기 제2 카운터와 같을 때, 상기 제1 카운터에 상기 제1 레지스터의 저장값의 차수를 저장하며; 상기 제1 카운터가 0이 될 때까지 상기한 과정들을 반복하고, 상기 제1 카운터가 0이 되면, 상기 나눗셈 연산을 종료함을 특징으로 하는 유한체 다항식 나눗셈 장치
|
6 |
6
제 2 항의 장치를 이용하여,(a)상기 제수 다항식의 차수를 구하고, 상기 제1 레지스터에 상기 제수 다항식을 저장하고, 상기 제2 레지스터에 상기 기약 다항식을 저장하고, 상기 제3 레지스터에 상기 피제수 다항식을 저장하고, 상기 제4 레지스터에 0을 저장하는 단계;(b)상기 제1 레지스터 저장값의 차수가 0이 아니고, 상기 제1 레지스터의 최하위비트가 0이 아니고, 상기 제1 레지스터 저장값의 차수가 상기 제2 레지스터 저장값의 차수보다 작지 않으면, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값에 대하여 배타적 논리합 연산을 수행한 후 그 결과를 1비트 우측 쉬프트하여 상기 제1 레지스터에 저장하고, 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값에 대한 배타적 논리합 연산 결과를 상기 제3 레지스터에 저장하는 단계;(c)상기 제1 레지스터 저장값의 차수가 0이 아니고, 상기 제1 레지스터의 최하위비트가 0이 아니고, 상기 제1 레지스터 저장값의 차수가 제2 레지스터 저장값의 차수보다 작으면, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값을 교환하고, 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값을 교환하고, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값에 대하여 배타적 논리합 연산을 수행한 후 그 결과를 1비트 우측 쉬프트하여 상기 제1 레지스터에 저장하고, 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값에 대한 배타적 논리합 연산 결과를 상기 제3 레지스터에 저장하는 단계;(d)상기 제1 레지스터 저장값의 차수가 0이 아니고, 상기 제1 레지스터의 최하위 비트가 0일 때, 상기 제1 레지스터의 저장값을 1비트 우측 쉬프트하는 단계;(e)상기 (b) 단계 또는 (c) 단계 또는 (d) 단계가 수행된 후, 상기 제3 레지스터의 최하위 비트가 0일 때, 상기 제3 레지스터의 저장값을 1비트 우측 쉬프트 하는 단계;(f)상기 (b) 단계 또는 (c) 단계 또는 (d) 단계가 수행된 후, 상기 제3 레지스터의 최하위 비트가 0이 아닐 때, 상기 제3 레지스터의 저장값과 상기 기약 다항식에 대하여 배타적 논리합 연산을 수행한 후 그 결과를 1비트 우측 쉬프트하는 단계; 및(g)상기 제1 레지스터의 저장값의 차수가 0이 될 때까지 상기 (b)단계 내지 (f)단계를 반복하여, 상기 제1 레지스터의 저장값의 차수가 0이 되면, 상기 제3 레지스터의 저장값을 출력하는 단계를 포함함을 특징으로 하는 유한체 다항식 나눗셈 방법
|
7 |
6
제 2 항의 장치를 이용하여,(a)상기 제수 다항식의 차수를 구하고, 상기 제1 레지스터에 상기 제수 다항식을 저장하고, 상기 제2 레지스터에 상기 기약 다항식을 저장하고, 상기 제3 레지스터에 상기 피제수 다항식을 저장하고, 상기 제4 레지스터에 0을 저장하는 단계;(b)상기 제1 레지스터 저장값의 차수가 0이 아니고, 상기 제1 레지스터의 최하위비트가 0이 아니고, 상기 제1 레지스터 저장값의 차수가 상기 제2 레지스터 저장값의 차수보다 작지 않으면, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값에 대하여 배타적 논리합 연산을 수행한 후 그 결과를 1비트 우측 쉬프트하여 상기 제1 레지스터에 저장하고, 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값에 대한 배타적 논리합 연산 결과를 상기 제3 레지스터에 저장하는 단계;(c)상기 제1 레지스터 저장값의 차수가 0이 아니고, 상기 제1 레지스터의 최하위비트가 0이 아니고, 상기 제1 레지스터 저장값의 차수가 제2 레지스터 저장값의 차수보다 작으면, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값을 교환하고, 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값을 교환하고, 상기 제1 레지스터의 저장값과 상기 제2 레지스터의 저장값에 대하여 배타적 논리합 연산을 수행한 후 그 결과를 1비트 우측 쉬프트하여 상기 제1 레지스터에 저장하고, 상기 제3 레지스터의 저장값과 상기 제4 레지스터의 저장값에 대한 배타적 논리합 연산 결과를 상기 제3 레지스터에 저장하는 단계;(d)상기 제1 레지스터 저장값의 차수가 0이 아니고, 상기 제1 레지스터의 최하위 비트가 0일 때, 상기 제1 레지스터의 저장값을 1비트 우측 쉬프트하는 단계;(e)상기 (b) 단계 또는 (c) 단계 또는 (d) 단계가 수행된 후, 상기 제3 레지스터의 최하위 비트가 0일 때, 상기 제3 레지스터의 저장값을 1비트 우측 쉬프트 하는 단계;(f)상기 (b) 단계 또는 (c) 단계 또는 (d) 단계가 수행된 후, 상기 제3 레지스터의 최하위 비트가 0이 아닐 때, 상기 제3 레지스터의 저장값과 상기 기약 다항식에 대하여 배타적 논리합 연산을 수행한 후 그 결과를 1비트 우측 쉬프트하는 단계; 및(g)상기 제1 레지스터의 저장값의 차수가 0이 될 때까지 상기 (b)단계 내지 (f)단계를 반복하여, 상기 제1 레지스터의 저장값의 차수가 0이 되면, 상기 제3 레지스터의 저장값을 출력하는 단계를 포함함을 특징으로 하는 유한체 다항식 나눗셈 방법
|