논문 08-33-07-02 한국통신학회논문지 '08-07 Vol. 33 No. 7 낮은상관특성과큰선형복잡도를갖는새로운 -진수열군 정회원김영식 *, 정정수 **, 종신회원노종선 **, 신동준 *** New Families of -ary Sequences With Low Correlation and Large Linear Span Young-Sik Kim*, Jung-Soo Chung** Regular Members, Jong-Seon No**, Dong-Joon Shin*** Lifelong Members 요 약 최근에홀수인소수,, 그리고 에대해서 Seo, Kim, No, Shin [1] 이 -sequence와 로 decimation한부분수열들사이의상관분포를유도하였다. 하지만이러한상관분포로부터수열군이자명하게결정되지는않는다. 본논문에서는우선위의상관특성을유지하는수열군을선택하는방법을제시한다. 더나아가서이수열군과동일한상관특성을가지면서도더큰선형복잡도를갖는수열군을새롭게생성할것이다. 끝으로 3진수열의선형복잡도를특정경우에대해서유도하고이경우원래의수열군보다더큰선형복잡도를가짐을보일것이다. Key Words : Cross-correlation, Linear complexity, Linear span, Sequences ABSTRACT For an odd prime,, and, Seo, Kim, No, and Shin [1] derived the correlation distribution of -ary -sequence of period and its decimated sequences by. In this paper, two new families of -ary sequences with family size and maximum correlation magnitude are constructed. The linear complexity of new -ary sequences in the families are derived in the some cases and the upper and lower bounds of their linear complexity for general cases are presented. Ⅰ. 서론오늘날의사불규칙수열은여러가지디지털통신시스템에서많이사용되고있다. 이러한수열들을설계하는데있어서가장중요한요소는수열들의상관특성이지만이에못지않게선형복잡도를 높게만드는것도매우중요하다. 왜냐하면선형복잡도는바로수열을분석하는것이얼마나어려운지에대한정보를제공해주기때문이다. 다시말해선형복잡도가크다는것은수열을분석하고다음값을예측하기위해서그만큼더많은정보가필요하다는의미이다. 본논문은교육과학기술부, 지식경제부, 노동부의출연금으로수행한최우수실험실지원사업과지식경제부및정보통신연구진흥원의 IT 핵심기술개발사업 [2008-F-007-01, 3 차원환경에서의지능형무선통신시스템 ] 에의한연구결과입니다. 본논문은 2008 JCCI 우수논문으로추천되었습니다. * 삼성전자 (kingsi@ccl.snu.ac.kr), ** 서울대학교전기 컴퓨터공학부및뉴미디어통신공동연구소 (integer@ccl.snu.ac.kr, jsno@snu.ac.kr) *** 한양대학교전자전기공학부 (djshin@hanyang.ac.kr) 논문번호 :KICS2008-05-240, 접수일자 :2008 년 5 월 23 일, 최종논문접수일자 :2008 년 7 월 4 일 534
논문 / 낮은상관특성과큰선형복잡도를갖는새로운 - 진수열군 최근에홀수인소수,, 그리고 에대해서 Seo, Kim, No, Shin [1] 이 -sequence와 로 decimation한부분수열들사이의상관분포를유도하였다. 하지만이러한상관분포로부터수열군이자명하게결정되지는않는다. 이논문에서는우선위의상관특성을유지하는수열군을선택하는방법을제시한다. 더나아가서이수열군과동일한상관특성을가지면서도더큰선형복잡도를갖는수열군을새롭게생성할것이다. 끝으로 3진수열의선형복잡도를특정경우에대해서유도하고이경우원래의수열군보다더큰선형복잡도를가짐을보일것이다. Ⅱ. 사전지식 가홀수인소수이고 가 개의원소를갖는유한체라하자. 그러면유한체 에서유한체 로의 trace 함수 는 로정 의된다. 여기서 이고 은 의약수이다. 가 의원시원이라하자. 그러면주기가 인 - 진 -sequence 은다음과같이 trace 함수로나타낼수가있다. 이논문에서는다음의정의들을사용할것이다. 이고 ; 은, 인정수 ; 는 의한원시원 ; 이고. 다음장에서다음의성질들을이용할것이다. 는 의원시원 ; 이고 ; 이고. 이므로주기가 인 개의서로다른 decimation 된수열 ( ) 가존재한다. 그러면 와 사이의상호상관함수는다음과같이정의된다. (1) 여기서 는 1 의 - 차원시복소근이고, 이고 이다. Seo, Kim, No, Shin은다음정리를증명하였다. 정리 1. (Seo, Kim, No, Shin [1]) 가홀수인소수이고, 그리고 라하자. 그러면 -진 -sequence 와 decimation된수열 ( ) 의상호상관분포는다음과같이주어진다. 일때, times times 그렇지않을때, times times 여기서 는 이다. 또한다음과같은관계식도 [1] 에서찾을수있다. Ⅲ. 낮은상관특성을갖는수열군 (2) 정리 1로부터주기가 인 -진수열군을생성할수있다. 이고 가 ( ) 의집합이라하자. 그러면 는 535
한국통신학회논문지 '08-07 Vol. 33 No. 7 이짝수또는홀수일때에따라 와 로나눌수있다. 다음의사전정리는집합 의한가지성질을보여준다. 사전정리 2. 는덧셈에대해닫혀있다. 증명 ) 정수 과 에대해 와 는다음과같이된다. 이기때문에 과 가된다. 수열군 를다음과같이정의하자. 수열군 에포함된두개의수열 와 에대해서 일때 (2) 를사용해서다음을유도할수있다. 그러므로 에서의두개의수열의상호상관값의최대크기는 보다더커질수있다. 상호상관값의최대크기가 로제한되는수열군을생성하기위해서 에서 를만족하는원소들을배제해야만한다. 이런원소들의집합을찾는데다음의사전정리를사용할수있다. 사전정리 3. 증명 ) 와 이기때문에, 모든원소 그리고 가서로다른것을보이는것으로충분하다. 라가정하자. 여기서 이고 이다. 그러면 와사전정리 2는 를함축한다. 즉 와 이다. 를만족하는집합 를찾으면상호상관값의최대값이 인수열군 를생성할수있다. 정리 4. 와 라하자. 그러면수열군 는다음과같이정의된다. 그러면이수열군의자기상관과상호상관함수는집합 에있는값을취하고수열군의크기는 이다. 여기서 이다. 증명 ) 일때 임을보이는것으로충분하다. 즉, 이다. 여기서 이고 이다. 그래서사전정리 2와사전정리 3으로부터 을어렵지않게보일수있다. 위의 는필요조건인 가어느원소라도하나를더더하면만족하지않는다는의미에서최대의집합이다. 이것은사전정리 3로부터쉽게보일수있다. 예제 5. 이고 가 의근이라하자. 그러면다음의수열군 는상호상관값의최대크기로 를갖는다.. 이때 이다. Ⅳ. 큰선형복잡도를갖는 - 진수열군 이제 Seo, Kim, No, Shin [1] 과동일한 decimation 를갖는새로운 -진수열군을유도하자. 우선 [2] 에나오는사전정리 1의 -진형태인다음의사전정리를유도하는것은어렵지않다. 사전정리 6. 라하자. 그리고 가다음과같이정의되는수열이라하자. 그러면, 일때 이고그렇지않으면 이다. 정리 1에서의수열군을사용하면더큰선형복 536
논문 / 낮은상관특성과큰선형복잡도를갖는새로운 - 진수열군 잡도를갖는새로운 -진수열군이다음의정리에서처럼생성될수있다. (5) 정리 7. 과, 이라하자. 그리고 가홀수인소수라하자. 는다음과 같이정의되는 - 진수열이라하자. 여기서 이다. 그러면수열군 에속하는수열들의상관함수는집합 에있는값을취한다. 증명 ) 와 의상관함수는다음과같이쓸수있다. (3) 이고 과 가 를 를기저로정리했을때의각자릿수라하자. 즉, 이다. 여기서 이고 이다. 그러면 이기때문에 임이쉽게유도된다. 그러면 (3) 은다음과같이다시정리할수있다. 여기서 (4) 만일 라면, 안쪽에있는합은 0이된다. 그렇지않은경우에는안쪽의합이 가된다. 그래서우리는 를만족하는 의개수를계산하여야한다. 이제 가 를만족하는 의개수라하자. 이므로, 는다음을만족하는 의개수와같다. 그러면 (4) 는다음과같이다시쓸수있다. (6) [1] 에있는정리 2로부터, 의값은이미 0, 1, 2, 3 중하나를취한다는것이증명되었다. 그래서상관함수는다음의집합에서값을취한다. Ⅴ. 3 진수열군의선형복잡도 수열군 에속한수열들의선형복잡도는다음과같다. 그러나 에속한수열들의선형복잡도를일반적으로유도하는것은쉬운일이아니다. 다음정리에서는 3진수열군의선형복잡도를특별한경우에대해서유도할것이다. 우선지수 는다음과같이 -진으로확장할수있다. (7) 여기서모든 에대해서 는 에속하는서로다른정수들이다. 그리고 는 의 Hamming weight이다. 즉, 의 -진확장에서의 0 이아닌자릿수의개수이다. 일반성을잃지않고서 라가정할수있다. 그러면다음과같이 에속한 3진수열들의선형복잡도를특별한경우에대해유도할수가있다. 정리 8. 만일 또는 와 가모든 에대해서성립하면 에속한수열 의선형복잡도는다음과같이주어진다. 여기서 537
한국통신학회논문지 '08-07 Vol. 33 No. 7 증명 ) 수열 의선형복잡도는다음과같은식에서 0이아닌항의개수와같다는것이잘알려져있다 [3]. 정의에의해다음과같이 의안쪽 trace 함수를전개할수있다. (8) 와 일때 로부터, (8) 의우변은다음과같이쓸수있다. (9) 그러면, 그리고 를사용하면, (9) 는다음과같이된다. 이방정식은 의이차방정식으로볼수있다. 와 라하자. 그러면 가성립한다. 즉 로나타낼수있다. 여기서 는 를만족하는 에속한한원소이다. 그러면 에속한수열은다음과같이쓸수있다. (10) 여기서 이다. 그러면 (10) 은다음과같이전개된다. 로부터, 다음식이성립한다. 이제 일때위의식을각각 와 로지수를올렸을때, 동일한차수의항이없음을보이자. 만일동일한차수의항이있다면, 어떤정수 와, 그리고 에대해서다음식이성립된다. (11) 여기서 이다. 이므로우변은 로나눠지지않지만좌변은나눠진다. 따라서모순이고그러므로중복되는차수는존재하지않는다. 따라서수열의선형복잡도는 (10) 를전개했을때의서로다른 의항들의개수의정확히 배가된다. 이제다음의두가지경우를생각해보자. Case 1) 가 0 인경우 : 가다음과같이정의된다. (12) (7) 를사용하면, 는다음과같이된다. 이때 라하면 가되고 이기때문에 는 에대해 0이아니다. 따라서 의항의개수는 개이다. 이경우선형복잡도는 이다. Case 2) 가 0 이아닌경우 : 는다음과같이된다. 여기서 는다음과같다. 일때, 가두개의항으로구성되어있으므로 는항이 4개이다. 일때, 이다. 그러면 가두개의항으로구성되어있으므로일반적으로는 8개의항을갖는다. 그러나가운데 로부터 또는 가성립 538
논문 / 낮은상관특성과큰선형복잡도를갖는새로운 - 진수열군 할때항수가하나더줄어들게된다. 따라서증명이완료된다. Ⅵ. 결론이논문에서는 Seo, Kim, No, Shin[1] 의논문에대한보충으로서수열군을생성하는방법을제시하였고그선형복잡도도유도하였다. 또한더큰선형복잡도를갖는새로운수열군을생성하는방법을제시하였고 3진수열의특정조건에대해서선형복잡도를유도하였다. 후자의수열군은전자의경우를 인특별경우로포함하고있으며 인경우일반적으로선형복잡도는크게증가하게된다. 따라서전자의수열군과동일한상관특성을가지면서도더높은보안성을제공해줄수있다. 참고문헌 [1] E.-Y. Seo, Y.-S. Kim, J.-S. No, and D.-J. Shin, Cross-correlation distribution of p-ary m-sequence of period and its decimated sequences by, in Proc. IEEE Int. Symp. Information Theory (ISIT2007), Nice, France, Jun. 24-29, 2007, pp.2516-2520. [2] R. A. Scholtz and L. R. Welch, GMW sequences, IEEE Trans. Inf. Theory, Vol.IT-30, No.3, pp.548-553, May 1984. [3] R. E. Blahut, Transform techniques for error control codes, IBM J. Res. Develop., Vol.23, pp.299-315, 1979. 김영식 (Young-Sik Kim) 정회원 2001년 2월서울대학교전기공학부공학사 2003년 2월서울대학교전기컴퓨터공학부석사 2007년 2월서울대학교전기컴퓨터공학부박사 2007년 3월 ~ 현재삼성전자 < 관심분야 > 시퀀스, 암호학, 오류정정부호, 디지털통신 정정수 (Jung-Soo Chung) 정회원 2003년 2월서울대학교전기공학부공학사 2003년 3월 ~ 현재서울대학교대학원전기 컴퓨터공학부석 박사통합과정 < 관심분야 > 시퀀스, 오류정정부호, 디지털통신노종선 (Jong-Seon No) 종신회원 1981년 2월서울대학교전자공학과공학사 1984년 2월서울대학교대학원전자공학과석사 1988년 5월 Univ. of Southern California, 전기공학과공학박사 1988년 2월 ~1990년 7월 Hughes Network Systems, Senior MTS 1990년 9월 ~1999년 7월건국대학교전자공학과부교수 1999년 8월 ~ 현재서울대학교전기컴퓨터공학부교수 < 관심분야 > 시퀀스, 시공간부호, LDPC 부호, OFDM, 이동통신, 암호학신동준 (Dong-Joon Shin) 종신회원 1990년 2월서울대학교전자공학과공학사 1991년 Northwestern Univ. 공학석사 1998년 5월 Univ. of Southern California, 전기공학과공학박사 1999년 4월 ~2000년 8월 Member Technical Staff at Hughes Network Systems 2000년 9월 ~ 현재한양대학교전자통신컴퓨터부교수 < 관심분야 > 부호이론, 시퀀스, 이산수학, 디지털통신 539