쇼어 알고리즘이란? 양자 컴퓨팅을 사용한 혁신 알고리즘

 

소인수 분해를 기억하는가?
1보다 큰 자연수를 소수인 인수들만의 곱으로 나타내는 방법이다.
즉, 자연수가 소수인 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37,... 의 곱으로 나타낸 방법이다.

소수는 무한히 큰 수가 있는데, 이러한 큰 수의 소인수분해를 빠르게 할 수 있는 알고리즘이 없다.
고전 알고리즘에서, 소인수 분해하는데 드는 시간은 기하급수적으로 커진다.
이러한 특징을 이용해 암호학에서 소인수 분해를 많이 사용한다.
이러한 소인수 분해를 다루는 알고리즘 중 하나가 쇼어 알고리즘이다.

 

쇼어 알고리즘이란?

쇼어 알고리즘(Shor's algorithm)은 1994년, 수학자 피터 쇼어(Peter Shor)가 제안한 알고리즘이다.

이 알고리즘은 양자 컴퓨터를 이용해 큰 정수의 소인수 분해를 효율적으로 수행할 수 있는 방법이다.

 

이 쇼어 알고리즘은 기존의 고전 컴퓨터 소인수분해 알고리즘보다 훨씬 빠른 속도로 소인수 분해를 수행할 수 있어서 암호학에 혁신을, 다른 말로 현대 암호의 위기를 가져왔다.

고전 알고리즘은 큰 수의 소인수 분해를 위한 시간이 지수적으로 증가한다면, 쇼어 알고리즘은 다항식 계산 시간 안에 문제를 해결할 수 있게 된다.

예를 들어 고전 알고리즘에서 2라는 숫자에 암호화키를 붙인 암호를 해독하기 위해, 키의 길이가 10, 11이라면, 2라는 작은 수의 10 제곱은 1024이고, 11 제곱은 2048만큼의 시간이 소비될 수 있다.

쇼어 알고리즘을 이용하면, 키의 길이가 10, 11이라도, 2*10+10, 2*11+10 등 30, 32 정도의 시간만 있으면 해결된다.

 

만약 사용하는 소수가 2가 아닌 무수히 큰 수라면? 고전 알고리즘과 쇼어 알고리즘의 차이는 압도적으로 커지게 된다.

 

쇼어 알고리즘은 양자 컴퓨터에서 사용할 수 있는 알고리즘이라서, 양자 컴퓨터의 가장 혁신적인 성과 중 하나로 꼽히게 되었다.

반응형

 

 

쇼어 알고리즘이 중요한 이유

현대 암호화 기법의 대부분은 큰 수의 소인수 분해가 어려운 점을 이용해 개발되었다 안전한 암호화 알고리즘으로 알려진 RSA 공개키 암호화 알고리즘은 두 개의 큰 소수의 곱으로 이루어진 수를 소인수 분해하는 것이 매우 어렵다는 점을 이용한 것이다.

양자 컴퓨터의 발전을 통해 쇼어 알고리즘이 상용화될 수 있다면, 이러한 암호화 체계는 무너지게 된다. 빠른 속도로 해독할 수 있기 때문이다.

 

양자 컴퓨팅의 발전은 보안 분야에 큰 위협이 될 수 있으며, 양자 컴퓨팅이 상용화되기 전에 양자 컴퓨터에 대한 암호화 기법이 연구되고 있다.

 

 

쇼어 알고리즘의 원리

 

쇼어 알고리즘은 양자 컴퓨팅 기술 중 양자 푸리에 변환(Quantum Fourier Transform)과 양자 중첩과 얽힘(Quantum Superposition and Entanglement) 기술을 이용한다.

양자 푸리에 변환 기술을 이용해 주기성을 빠르게 찾아 내 소인수 분해가 가능하게 만들어주고, 양자 중첩과 얽힘 기술을 이용해서는 병렬 계산을 통해 다양한 가능성을 동시에 탐색해 고전 알고리즘에서는 할 수 없는 대규모 연산을 수행할 수 있게 해 준다.

 

 

쇼어 알고리즘의 가능성

 

이론적으로 쇼어 알고리즘은 무척 강력하고 암호 체계를 무너뜨릴 수 있는 강력한 알고리즘이다.

아직 이를 구현할 수 있는 대규모 양자 컴퓨터가 상용화되지는 않았지만, 구글과 IBM 등 양자 컴퓨터를 개발한 대기업에서 점차 현실화되고 있다.

양자 오류 수정(QEC) 기술이 더 발전하게 된다면, 쇼어 알고리즘을 통한 실질적인 암호 해독도 가능해질 것이다. 쇼어 알고리즘을 사용할 수 있게 되는 것이 양자 컴퓨팅에 대비한 새로운 암호화 체계보다 먼저 된다면, 세계는 큰 혼란이 야기될 수 있을 만큼 쇼어 알고리즘의 상용화는 중요한 문제이다.

 

양자 컴퓨팅의 잠재력

 

쇼어 알고리즘을 통해 양자 컴퓨팅의 잠재력을 알 수 있다. 대규모 양자 컴퓨터가 상용화될 수 있다면, 기존의 암호 체계는 무너질 것이다. 기존 암호화 기술을 대신할 새로운 보안 체계가 필요하며, 양자 안전 암호(Post-Quantum Cryptography) 같은 기술 연구가 활발히 진행 중에 있다.

---

 

양자 컴퓨터의 상용화가 될 것처럼 이슈가 되었다가, 아직은 아니다라며 양자 컴퓨팅 관련 업계의 마케팅이 한 참 진행되고 있다. 어느 기술이 먼저 적용되고 상용화되는지, 양자 암호화 기술과 쇼어 알고리즘의 발전을 주의 깊게 지켜볼 필요가 있을 것 같다.