일상생활 속에서 공개키 암호는 암호화, 키 분배, 인증 등과 같은 분야에서 널리 사용되고 있다. 대표적인 공개키 암호 알고리즘에는 RSA(Rivest-Shamir-Adleman), 타원 곡선 암호, Diffie-Hellman 등 다양한 알고리즘이 존재한다. 현재 컴퓨팅 파워로는 해독할 수 없다고 여겨지던 공개키 알고리즘은 1994년 피터 쇼어(Peter Shor)가 제안한 Shor 알고리즘이 양자 컴퓨터에 적용되면 공개키 암호 알고리즘이 다항 시간 안에 해독 가능함이 증명되며, Shor 알고리즘에 관해 다양한 연구가 진행되고 있다. Shor 알고리즘을 양자 컴퓨터에 구현하려면 큐비트 부족, 디코히런스, 게이트 오류 등의 제약을 극복해야 한다. 이를 해결하기 위해 한정된 큐비트와 게이트로 효율적인 연산을 수행하는 최적화 연구가 활발히 이루어지고 있다.

본 논문은 Shor 알고리즘 최적화를 위한 양자 회로에서의 곱셈 연산 구현을 위해, Shor 알고리즘 및 해당 알고리즘의 최적화 방향에 관해서 설명한다. 본 연구에서는 양자 회로에서의 Strassen 알고리즘의 구현을 위해 NTT를 설계하였으며, 설계한 NTT의 구현을 위해 덧셈, 곱셈, 모듈러 연산을 수행하는 연산 모듈을 구현하였다. 구현한 모듈을 기반으로 Strassen 알고리즘을 구현하며, 나아가 기존의 곱셈 알고리즘과의 양자 자원량 비교를 통해 제안하는 알고리즘의 효율성을 검증한다.