서지주요정보
On the weight and nonlinearity of rotation symmetric boolean functions = 회전대칭 불함수의 해밍무게 및 비선형성 연구
서명 / 저자 On the weight and nonlinearity of rotation symmetric boolean functions = 회전대칭 불함수의 해밍무게 및 비선형성 연구 / Hyeon-Jin Kim.
발행사항 [대전 : 한국과학기술원, 2008].
Online Access 원문보기 원문인쇄

등록번호

8019706

소장위치/청구기호

학술문화관(문화관) 보존서고

DMA 08006

도서상태

이용가능

반납예정일

#### 초록정보

Recently, rotation symmetric Boolean functions have taken strong attention and exhibited their usefulness. For example, important questions in coding theory were given answers by heuristic or theoretical searches in the function class. The functions are also applied to design an efficient hash algorithm. On the other hand, for quadratic rotation symmetric functions with single orbit, their exact weight and nonlinearity were formulated in [4, 21]. We improve parts of their results. It is observed that the n-variable quadratic boolean functions $f_{n,s} (x) := \sum^n_{i=1} x_i x_{i+s-1}$ for $2 \leq s \leq \lceil \frac{n}{2}\rceil$ , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weight and nonlinearity are exactly characterized by the cyclic subgroup \langle{s-1} \rangle$of$\Bbb{Z}_n$. If$\frac{n}{gcd(n,s-1)}$, the order of$s-1$, is even then the weight and nonlinearity of$f_{n,s}$are the same and given by$2^{n-1} - 2^{\frac{n}{2}+gcd(n,s-1)-1}$. If the order is odd then$f_{n,s}$is balanced and its nonlinearity is given by$2^{n-1} - 2^{\frac{n+gcd(n,s-1)}{2}-1}$. Enlarging it slightly, we also characterize the exact weight of$g_{n,s} (x) := f_{n,s} (x) + \sum_{i=1}^n x_i$. Finally, we touch a conjecture, given in [24], of the nonexistence of bent functions which are homogeneous rotation symmetric of degree$\geq3$, and give a positive answer to it for a very limited case. 최근 회전대칭 불함수가 매우 유용한 특성들을 드러내면서 많은 관심의 대상이 되고 있다. 예를 들어, 부호이론에서 중요한 문제들을 해결하는 함수들이, 회전대칭 불함수공간에 대한 실험적 및 이론적 탐색을 통하여 발견되었다. 또한, 회전대칭 불함수를 이용하여 효율적인 해시 알고리즘을 설계하는 연구도 시도되었다. 다른 한편으로, 매우 단순한 회전대칭 불함수들에 대한 해밍무게와 비선형성의 정확한 공식들이 발견되었다 [4, 21]. 우리는 그 공식들을 개선하고자 한다. n-변수 2차 회전대칭 불함수로서,$2 \leq s \leq \lceil \frac{n}{2} \rceil$인 정수 s에 대하여 주어진$f_{n,s} (x) := \sum_{i=1}^n x_i x_{i+s-1}$는, 고정된 n과 서로 다른 s값의 선택에 대하여 아핀동치가 성립되지 않음을 확인하였다. 우리는 이 함수들의 정확한 해밍무게와 비선형성이, 잉여류군$\BbbZ_n$의 순환부분군$\lange s-1 \rangle$의 구조에 의해 정확하게 기술될 수 있음을 보인다. 만약 s-1의 차수$\frac{n}{gcd(n,s-1)}$이 짝수라면 함수의 해밍무게와 비선형성은 동일하고 그 값은$2^{n-1} - 2^{\frac{n}{2}+gcd(n,s-1)-1}$로 주어진다. 만약 그 차수가 홀수라면 함수의 해밍무게는 균형을 이루고 비선형성은$2^{n-1} - 2^{\frac{n+gcd(n,s-1)}{2}-1}$로 주어진다. 우리는 이 공식을 약간 확장하여 함수$g_{n,s}(x) := f_{n,s}(x) + \sum_{i=1}^n x_i\$ 의 정확한 해밍무게 공식도 발견하였다. 마지막으로, [24]에서 제시된 추측으로서, 차수가 3이상인 회전대칭 동차 bent 함수의 비존재성에 대하여 잠깐 살펴보고, 매우 제한된 상황에서 그 추측이 성립한다는 것을 보인다.

#### 서지기타정보

청구기호 {DMA 08006 v, 38 p. : 삽화 ; 26 cm 영어 저자명의 한글표기 : 김현진 지도교수의 영문표기 : Sang-Geun Hahn 지도교수의 한글표기 : 한상근 학위논문(박사) - 한국과학기술원 : 수리과학과, References : p. 36-38
QR CODE