[요약]
모듈러 2N-1 연산의 특징을 이용해 효율적인, 즉, 양자 회로의 복잡도가 낮은 양자 모듈러 곱셈기 및 양자 모듈러 곱셈 방법이 개시된다. 본 발명의 실시 예에 따른 양자 모듈러 곱셈기는 N자리(N은 2 이상인 자연수) 제1 큐비트들과 N자리 제2 큐비트들을 곱하는 양자 모듈러 곱셈기로서, 상기 제1 큐비트들 중에서 최하위 제1 큐비트와 상기 제2 큐비트들의 부분 곱을 제1 보조 큐비트들에 저장하는 제1 보조 레지스터 설정부, 상기 제1 큐비트들 중에서 p번째(p는 2 이상이며 N 이하인 자연수) 제1 큐비트와 상기 제2 큐비트들의 부분 곱을 (p-1)번 왼쪽 순환 시프트(left circular shift)하여 제2 보조 큐비트들에 저장하는 제2 보조 레지스터 설정부, 상기 제1 보조 큐비트들과 상기 제2 보조 큐비트들을 모듈러 2N-1 덧셈하고 모듈러 덧셈 결과를 상기 제1 보조 큐비트들에 저장하는 가산부 및 상기 제2 보조 큐비트들을 초기화하는 보조 레지스터 초기화부를 포함하며, 상기 제2 보조 레지스터 설정부, 상기 가산부 및 상기 보조 레지스터 초기화부는 상기 p가 2 부터 N까지 반복하여 수행될 수 있다.
[대표청구항]
N자리(N은 2 이상인 자연수) 제1 큐비트들과 N자리 제2 큐비트들을 곱하는 양자 모듈러 곱셈기에 있어서,상기 제1 큐비트들 중에서 최하위 제1 큐비트와 상기 제2 큐비트들의 부분 곱을 제1 보조 큐비트들에 저장하는 제1 보조 레지스터 설정부;상기 제1 큐비트들 중에서 p번째(p는 2 이상이며 N 이하인 자연수) 제1 큐비트와 상기 제2 큐비트들의 부분 곱을 (p-1)번 왼쪽 순환 시프트(left circular shift)하여 제2 보조 큐비트들에 저장하는 제2 보조 레지스터 설정부;상기 제1 보조 큐비트들과 상기 제2 보조 큐비트들을 모듈러 2N-1 덧셈하고 모듈러 덧셈 결과를 상기 제1 보조 큐비트들에 저장하는 가산부; 및상기 제2 보조 큐비트들을 초기화하는 보조 레지스터 초기화부를 포함하며,상기 제2 보조 레지스터 설정부, 상기 가산부 및 상기 보조 레지스터 초기화부는 상기 p가 2 부터 N까지 반복하여 수행되는 양자 모듈러 곱셈기.
