4 . 2 에서 제시 된 패턴 검색 방법 에 의해 단순 패턴 들 에 대한 위치 가 주어지 면 , 본 발명 에 따른 새로운 다항식 컨 볼루 션 연산 방법 이 사용 될 수 있 다 . 도 2 는 본 발명 에 따른 다항식 컨 볼루 션 연산 방법 을 구현 한 알고리즘 의 간단 한 형태 를 나타내 는 도면 이 다 . 본 발명 에 따른 알고리즘 은 도 1 에 도시 된 Bailey 등 이 제안 한 다항식 컨 볼루 션 연산 방법 을 구현 한 알고리즘 의 개량 버전 으로 간주 될 수 있 다 . 이 개량 된 알고리즘 은 4 . 2 에서 제시 된 패턴 검색 방법 에 의해 이진 다항식 a ( X ) 의 비트 스트링 표현 에서 검색 된 단순 패턴 들 의 위치 를 입력 으로 받 고 , 또한 일반 다항식 c ( X ) 를 입력 으로 받 아 컨 볼루 션 t ( X ) = a ( X ) * c ( X ) 를 계산 한다 . 단 , 알고리즘 을 좀 더 일반 화 할 수 있 도록 인자 w 를 추가 하 였 는데 , 이 는 4 . 2 에서 의 패턴 검색 방법 이 검색 하 고자 하 는 패턴 의 최대 길이 를 나타낸다 . 즉 , 4 . 2 에서 기술 된 바 와 같이 단순 패턴 ' 11 ', ' 101 ', ' 1001 ', ' 10001 ', ' 100001 ' 들 을 찾 고 , 인접 한 ' 1 ' 사이 에 0 이 5 개 이상 연속 되 는 패턴 은 무시 할 경우 , w = 6 이 된다 . 또한 , 기술 을 간단 하 게 하 기 위하 여 단순 패턴 을 기호 로 p 1 = ' 11 ', p 2 = ' 101 ', p 3 = ' 1001 ', p 4 = ' 10001 ', p 5 = ' 100001 ' 과 같이 표기 하 고 , 단순 패턴 에 포함 되 지 못한 격리 된 ' 1 ' 을 p 0 로 표기 하 였 다 . 도 2 의 알고리즘 에서 , 제 1 행 내지 제 8 행 은 사전 계산 단계 로서 , 인덱스 계산 을 포함 하 는 2 ( w - 1 ) N + ( w - 1 ) 번 의 정수 덧셈 을 필요 로 한다 . 반면 에 , 도 2 에 도시 된 알고리즘 의 제 9 행 내지 제 26 행 은 컨 볼루 션 단계 로서 , 2 ( d 0 + d 1 + … + dw - 1 + 1 ) N 번 의 덧셈 과 N 번 의 모듈러 감산 을 필요 로 한다 . 따라서 도 2 에 도시 된 알고리즘 에 요구 되 는 총 계산 량 은 , 2 ( d 0 + d 1 + … + dw - 1 + w ) N + ( w - 1 ) 번 의 덧셈 과 N 번 의 모듈러 감산 이 다 . 도 1 에 도시 된 기존 의 알고리즘 이 2 ( d + 1 ) N 번 의 덧셈 과 N 번 의 모듈러 감산 을 필요 로 했 다는 것 을 상기 해 보 자 . 일반 적 으로 는 d 0 + d 1 + … + dw - 1 + w 는 d + 1 보다 훨씬 더 작 으므로 , 도 2 에 도시 된 본 발명 에 따른 알고리즘 에 의한 상당 한 속도 향상 을 기대 할 수 있 다 .