GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

현대 디지털 세계의 많은 보안은 단순한 수학적 트릭에 의존하고 있습니다. 즉, 두 개의 큰 소수를 곱하는 것은 매우 쉽지만, 결과값만을 보고 어떤 두 숫자가 사용되었는지 알아내는 것은 매우 어렵다는 점입니다. 이 일방통행식 구조는 온라인 뱅킹, 개인 메시지, 그리고 보안 통신을 보호하는 RSA 암호화의 기초가 됩니다. 수십 년 동안 이 코드를 깨는 유일한 방법은 올바른 쌍을 찾을 때까지 가능한 모든 숫자의 조합을 시도하는 것이었으며, 이는 너무나 방대한 작업이라 가장 강력한 슈퍼컴퓨터라 할지라도 큰 키(key) 값을 해결하려면 우주의 나이보다 더 긴 시간이 걸릴 정도였습니다. 양자 컴퓨터가 언젠가 이 코드를 즉각적으로 해독할 것을 약속하고 있지만, 아직 그 단계에는 도달하지 못했습니다. 이는 고전 컴퓨터가 무차별 대입(brute force)이 아닌, 누락된 숫자를 찾는 과정을 에너지와 균형의 퍼즐로 다룸으로써 문제를 해결할 새로운 방법을 찾아야 하는 공백을 남깁니다.

인도 공과대학교 마드라스(IIT Madras)의 연구진은 고사양 게임이나 비디오 렌더링용 컴퓨터에 들어가는 칩인 표준 그래픽 처리 장치(GPU)를 사용하여 이 과제에 도전하는 새로운 방법을 개발했습니다. 숫자를 직접 추측하는 대신, 그들은 이 문제를 언덕과 골짜기가 있는 지형으로 변환했으며, 여기서 해답은 가장 깊은 골짜기의 맨 밑바닥에 위치합니다. 그들은 두 개의 숨겨진 소수의 비트들을 각각 두 가지 상태 중 하나를 가질 수 있는 작은 스위치들의 격자 위에 매핑했습니다. 목표는 두 개의 올바른 소인수를 수학적으로 인코딩하는 가장 낮은 에너지 상태의 구성을 만드는 특정 스위치 배열을 찾는 것이었습니다.

이를 해결하기 위해 연구팀은 금속을 냉각하여 결함을 제거하는 물리적 과정을 모방한 '시뮬레이티드 어닐링(simulated annealing, 담금질 기법)'이라는 기술을 사용했습니다. 디지털 버전에서 시스템은 무작위의 스위치 배열과 높은 수준의 '열' 상태에서 시작하여 스위치들이 자유롭게 뒤집힐 수 있도록 합니다. 시스템이 냉각됨에 따라 스위치들은 더 안정적인 패턴으로 자리 잡게 됩니다. 연구진은 이 소프트웨어가 수천 개의 계산을 동시에 수행할 수 있는 강력한 단일 그래픽 칩인 NVIDIA GH200에서 실행되도록 설계했습니다. 그들이 만든 수학적 지도는 대부분 비어 있기 때문에(즉, 대부분의 스위치는 서로 상호작용하지 않음), 연구진은 실제로 존재하는 연결에만 집중하도록 작업을 조직했습니다. 이를 통해 오류 없이 많은 스위치를 동시에 업데이트할 수 있었으며, 이는 두 개의 상호작용하는 스위치가 정확히 동시에 변경되지 않도록 보장하는 영리한 정렬 방법을 필요로 했습니다.

시스템이 항상 완벽한 답을 즉시 찾아낸 것은 아니었습니다. 테스트에서 이 어닐러(annealer)는 일관되게 정답에 매우 근접한 결과에 도달했으며, 종종 실제 숫자와 몇 퍼센트 이내의 오차를 보였습니다. 이 마지막 간극을 메우기 위해 연구진은 컴퓨터의 최선의 추측 근처의 숫자들을 확인하는 두 번째 단계인 '유도 탐색(guided search)'을 추가했습니다. 그들은 소수가 될 가능성이 없는 숫자들을 건너뛰는 필터링 방법을 사용하여 필요한 작업량을 획기적으로 줄였습니다. 100비트 숫자의 경우, 초기 설정부터 최종 인수를 찾는 것까지 전체 과정은 단일 머신에서 6분 조금 넘게 걸렸습니다. 이는 동일한 작업을 수행하는 전통적인 방식보다 현저히 빠른 속도입니다.

연구진은 16비트에서 128비트에 이르는 숫자들에 대해 이 파이프라인을 테스트했습니다. 100비트 숫자를 단 몇 분 만에 성공적으로 인수 분해했지만, 그들은 이 방법이 여전히 정확한 답을 찾기 위해 최종 탐색 단계에 의존한다는 점을 언급했습니다. 이 최종 단계의 속도는 초기 추측이 진실에 얼마나 가까운지에 따라 크게 달라집니다. 연구진은 자신들의 방법이 기존의 더 단순한 추측들보다 훨씬 더 나은 시작점을 일관되적으로 제공하며, 이를 통해 최종 탐색에 필요한 시간을 대폭 줄였다는 것을 발견했습니다. 또한 그들은 '코퍼스미스 방법(Coppersmith's method)'이라고 알려진 특정 수학적 기술을 사용하면 더 큰 숫자에 대해서도 프로세스 속도를 높일 수 있어, 128비트 숫자에 대한 시간을 몇 달에서 며칠로 단축할 수 있음을 입증했습니다.

이 연구는 현재의 암호화 표준을 깨뜨리는 것은 아닙니다. 왜냐데 테스트된 숫자들은 일반적으로 수백 자릿수의 숫자를 사용하는 실제 보안 환경의 숫자들보다 훨씬 작기 때문입니다. 그러나 이 연구는 적절한 수학적 구조와 병렬 처리 최적화를 갖춘 고전 컴퓨터가 이와 같은 유형의 문제를 이전 생각보다 훨씬 더 효율적으로 해결할 수 있음을 증명합니다. 이 연구는 병목 현상이 더 이상 컴퓨터의 순수한 속도가 아니라, 초기 추측을 얼마나 잘 정교화할 수 있느냐에 달려 있음을 시사합니다. 만약 미래의 개선을 통해 컴퓨터가 해답에 더욱 가까워질 수 있다면, 최종 탐색 단계가 매우 작아져 전체 과정이 언젠가 '다항 시간(polynomial time)' 내에 실행될 수도 있으며, 이는 암호학의 지형을 바꿀 이론적인 속도입니다. 현재로서는, 연구진은 문제의 독특한 형태를 존중하고 현대 그래픽 칩의 거대한 병렬 처리 능력을 활용함으로써, 겉보기에 불가능해 보이는 수학적 잠금장치를 풀 수 있는 퍼즐로 바꿀 수 있음을 보여주었습니다.