소수판별 후 상수시간 소인수분해를 위한 순차 모듈로 연산 기반의 보편적그룹화정수모델

• 영문명: Generally Grouped Integer Model Based On Sequential Modular Arithmetic For Primality Testing Followed By Constant Time Factorization
• 발행기관: 미래학회
• 저자명: 이상지(Sang Zee Lee)
• 간행물 정보: 『미래연구』1권 2호, 83~99쪽, 전체 17쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2016.12.30

국문 초록

암호화보안에 필수적인 소수판별과 소인수분해는 원리적인 면에서 밀접하게 서로 연관되어 있지만 시간복잡도를 고려한 연산 알고리즘은 매우 다르게 이원화 되어 있다. 가장 효율적인 소수판별 알고리즘은 일반적이고 무조건적이며 결정론 적으로 다항시간에 소수판별이 가능한 AKS 알고리즘으로 알려져 있다. 반면에 다항시간 소인수분해 알고리즘은 Shor 알고리즘과 같은 양자컴퓨팅 방식 외에는 발표된 것이 없고, 가장 효율적인 것으로 알려진 GNFS 알고리즘은 준지수시간 복잡도로 AKS 알고리즘보다 훨씬 더 오래 걸린다. 암호화보안 분야에서 오랫동안 해결되지 않은 가장 중요한 문제는 소수판별과 소인수분해를 동시에 다항수 시간 이내에 더 빨리 처리하는 알고리즘의 개발로 알려져 있다. 본 논문에서는 소수판 별과 소인수분해 통합 처리가 가능한 순차 모듈로 연산 기반의 보편적그룹화정수 모델(GGIM)을 제안한다. 제안된 방식에 따르면 소수판별과 소인수분해가 일원화로 통합된 정수모델을 기반으로 일반적이고 무조건적이며 결정론적으로 이루어지는 특징을 지닌다. 또한 주어진 홀수 자연수에 대해 소수판별 과정을 통해 합성수로 판별이 이루어진 경우 이후의 소인수분해는 상수시간으로 처리 가능한 특장점을 지닌다. 따라서 본 논문에서 제안된 정수모델을 기반으로 이루어지는 추가 연구는 소수판별에 소요되는 시간을 다항시간 이내로 최적화하는 방향으로 집중할수 있을 것이다. 본 논문을 통하여 새롭게 제안한 GGIM 알고리즘이 앞으로 소수 판별 시간을 단축시킬 수 있는 연구 활성화를 위한 추춧돌이 될 것으로 기대된다.

영문 초록

While primality testing and factorization are mathematically interrelated in principle, they are very different computationally in the algorithm with the time complexity. The most efficient primality test algorithm to be concurrently general, unconditional, deterministic and polynomial is known to be AKS primality test. But no factorization algorithm except for quantum computing like the Shor’s algorithm has been published that can factor all integers in polynomial time. The fastest prime factorization algorithm for a large number is the general number field sieve (GNFS) with sub-exponential time complexity, which usually takes too much longer time than AKS primality test algorithm. In this paper a new Generally Grouped Integer Model (GGIM) based on sequential modular arithmetic is proposed. This proposed methodology is a unified single algorithm for primality test and subsequent factorization, which is concurrently general, unconditional and deterministic. Moreover factorization takes constant time additionally just after a given integer is proved to be composite through primality test. This paper is anticipated to be a starting point for more sophisticated studies on optimization of the time complexity of primality testing based on the proposed model. It is hoped that a new approach proposed in this paper may shed some light on what is really a very difficult subject, polynomial primality test with subsequent constant time factorization, not solved for long time.

목차

1. Introduction

2. Generally Grouped Integer Model (GGIM) based on sequential modular arithmetic

3. The number of steps for sequential modular arithmetic

4. Primality Test

5. Factorization with constant time complexity

6. Exemplary cases

7. Conclusion

키워드

Generally Grouped Integer Model (GGIM) primality constant time factorization AKS GNFS 보편적 그룹화 정수 모델(GGIM) 소수판별 상수시간 소인수분해 순차 모듈로연산