Analysis of Behaviors of Additive Group Cellular Automata

Abstract

VLSI시대는 선형 기계와 특히 국소적인 이웃을 갖는 셀룰라 오토마타(Cellular Automata, 이하 CA)의 연구에 새로운 국면을 예고하였다. VLSI 구현은 국소적으로 상호 연결된 간단하고 규칙적이며 모듈러하고 작은 단위로 확장 연결이 가능한 구조가 적합한데, 이는 그러한 성질을 가진 CA가 적합하다. 또한 CA는 선형 상태 함수들의 여원에 의하여 구성된 기계의 한 유형이라는 것과 LFSR보다 속도와 응용 면에서 뛰어나다는 장점을 가지고 있다. 이러한 CA는 Von Neumann에 의하여 자체 재생산이 가능한 모델로 소개되었으며 여러 학문 분야에서 응용되고 있다. Wolfram은 CA의 가장 간단한 구조로 에서의 1차원 CA를 제안하였으며, 이후 Das등에 의하여 행렬 대수에 의하여 이를 체계화하였다. 오늘날 LFSR의 대안으로 제안된 CA는 LFSR과 달리 분석이 어려워 이에 대한 분석과 이를 바탕으로 해쉬, 패턴 생성, 키교환과 암호학 등에서 널리 응용되어지고 있다. 본 논문에서는 CA에 대한 기본 개념과 성질을 살펴보고, 룰 60 또는 102를 갖는 선형 유니폼 group CA(Linear Uniform Group CA, LUGCA)로부터 유도된 각 여원 벡터에 대응하는 여원 CA가 가능한 최대 동일 길이의 사이클로 나누어지는 성질을 분석하고, Das의 추측이 사실임을 보인다. 또한 가능한 최대 동일 길이로 사이클이 나누어지는 룰 60 ,102 또는 204를 갖는 선형 하이브리드 group CA(Linear Hybrid Group CA, LHGCA)로부터 유도된 각 여원 벡터에 대응하는 여원 CA를 분석한다. 또한 LUGCA와 LHGCA에서 키 교환 프로토콜에 유용한 여러 함수를 구성하고 이러한 함수와 여원 연산자간의 관계를 분석한다. 그리고 룰 90 또는 150을 갖고 최대 길이 수열을 생성하는 CA(Maximum-Length CA, MLCA)로부터 생성된 수열을 분석하고, 90/150 MLCA에서 나타나는 각 열의 위상이동차에 대한 성질을 분석한다. 이를 이용하여 90/150 MLCA의 위상이동차를 구하는 알고리즘을 제안한다. 또한 LFSR에 기반한 CCSG(Clock-controlled shrinking generator)를 분석하고 이에 대응하는 비대칭인 최소 차수의 선형 CA를 모델링한다. 마지막으로 GF(2)의 확장체인 GF(2^(p))에서의 그룹 CA의 구조와 특성다항식을 분석한다.