GN⁺: 1024비트 소수 생성의 어려움

• 소개
  • 소수는 쉽게 설명할 수 있지만 엄청난 복잡성을 내포하고 있음
  • 수학적 개념, 흥미로운 시각화, 암호학 등 다양한 분야에서 활용됨
  • 코딩을 통해 소수 생성에 도전해보기로 함
• 도전 과제
  • RSA 알고리즘에 사용할 수 있는 소수 생성하기
  • 현재 RSA 키로 적합한 길이는 2048 비트이므로, 1024 비트 크기의 소수 2개가 필요함
  • 제약 조건:
    • 처음부터 직접 코드 작성 (외부 의존성 없이)
    • 노트북의 AMD Ryzen 7 CPU와 16GB RAM만 사용
    • "합리적인" 시간 내에 소수 생성
  • Rust 언어 선택
• 16비트 소수 생성
  • 의사 난수 생성기 /dev/urandom을 이용해 난수 생성
  • 간단한 소수 판별법인 시험적 나눗셈(Trial Division) 사용
  • 평균 40ms 내에 16비트 소수 생성 가능
• 64비트 소수 생성
  • 최적화된 시험적 나눗셈 알고리즘 구현
    • 6k±1 형태의 수만 확인
    • 작은 소수 목록을 미리 생성하여 쉽게 나눌 수 있는 수 먼저 걸러내기
  • 최적화 후 약 6초 소요
  • 더 큰 수에는 결정적 알고리즘으로는 한계가 있음
• 확률적 소수 판별법
  • 페르마의 소정리(Fermat's Little Theorem) 활용
    • 합성수도 조건을 만족시킬 수 있는 문제점 존재 (Pseudoprimes)
  • 밀러-라빈 소수 판별법(Miller-Rabin Primality Test)
    • 페르마 판별법을 개선한 확률적 판별법
    • 합성수가 항상 어떤 밑(base)에 대해 Pseudoprime이 되는 경우는 없음
    • 오류 확률이 매우 낮아 실용적으로 사용 가능
• 128비트 소수 생성
  • 밀러-라빈 판별법으로 빠르게 생성 가능 (평균 0.03초)
  • u128 자료형의 한계로 인해 1024비트까지 확장하기 어려움
• 1024비트를 위한 BigInt 구현
  • 여러 번의 시도를 통해 점진적으로 개선
    • 시도 1: 숫자의 각 자릿수를 배열에 저장
    • 시도 2: 숫자를 이진수 형태로 저장
    • 시도 3: 숫자를 바이트 단위 청크로 저장
    • 시도 4: 숫자를 u64 단위 청크로 저장
    • 시도 5: 사칙연산 알고리즘 최적화
  • 밀러-라빈 판별법 및 전체 로직 최적화
  • 멀티스레딩을 활용한 병렬 처리
• 최종 결과
  • 약 40ms 내에 1024비트 소수 생성 가능 (8ms ~ 800ms)
  • 병렬 처리를 통해 평균 0.04초 소요

GN⁺의 의견

• 시도와 실패를 반복하며 점진적으로 개선해 나가는 과정이 인상적이었음
  • 단순한 구현에서 시작하여 각 단계마다 새로운 아이디어를 적용하고 최적화를 수행
  • 실패를 겪더라도 포기하지 않고 문제의 원인을 파악하고 해결책을 모색
• 저자의 수학적 배경 지식이 부족함에도 불구하고 관련 자료를 찾아보고 이해하려 노력한 점이 돋보임
  • 페르마의 소정리, 밀러-라빈 판별법 등 필요한 수학적 개념을 학습
  • 어려운 내용도 구현이 가능한 수준까지 이해하고 적용
• 고정 길이 정수 자료형의 한계를 극복하기 위해 직접 BigInt를 구현한 것이 인상적
  • 단순히 기존 라이브러리를 사용하는 것이 아니라, 내부 동작 원리를 이해하고 최적화를 수행
  • 다양한 아이디어를 시도하며 점진적으로 개선해 나가는 모습이 돋보임
• 멀티스레딩을 활용한 병렬 처리로 성능을 크게 향상시킨 것이 흥미로웠음
  • 독립적인 계산을 수행하는 문제의 특성을 잘 파악하고 활용
  • 단순히 빠른 속도를 추구하는 것이 아니라, 문제의 특성을 고려한 효과적인 접근
• 암호학적으로 안전한 수준은 아니지만, 학습과 탐구의 과정으로서 큰 의의가 있는 프로젝트로 보임
  • 실용적인 활용보다는 저자의 호기심과 도전 정신이 돋보이는 과제
  • 과정에서 얻은 통찰과 경험이 향후 저자의 성장에 큰 도움이 될 것으로 기대됨

[neo]

Hacker News 의견

• 관련하여, 몇몇 암호화폐는 작업 증명 함수의 일부로 큰 소수 찾기와 관련된 것들을 사용함. 약 8년 전에는 매우 빠른 소수 판정 구현으로 많은 돈을 벌 수 있었음. 저자는 한동안 riecoin을 위한 채굴 소프트웨어의 작성자이자 관리자였음.

• 이 기사에서는 빠른 소수 판정을 위한 최고의 최적화인 Montgomery 곱셈을 생략함. 이는 빠른 실용적인 모듈러 지수 연산 구현의 기초가 됨.

• Niall Emmart가 공개한 CGBN은 정말 엄청나게 빠른 GPU bigint 라이브러리임. 여전히 내가 알고 있는 가장 빠른 batch modexp 구현임.

• Python은 pow(x, y, m) → x^y % m을 계산하는 꽤 좋은 modexp를 내장하고 있음. 이를 통해 Fermat이나 Miller-Rabin 소수 판정을 쉽게 구현할 수 있음.

• 처음에는 확률적 소수 판정 개념이 이상했고 거대한 수를 다룰 수 있는 결정론적 알고리즘을 찾으려 했지만, APR-CL과 ECPP가 수학적으로 너무 복잡해서 이해하기 어려웠음. RSA를 포함한 거의 모든 곳에서 확률적 알고리즘을 사용한다는 것을 깨달음.

• 특정 최대 수 범위에 대해 Miller-Rabin을 결정론적으로 만드는 것은 자명함. 주어진 범위에서 모든 유사소수를 제외하는 것으로 증명된 기저들을 선택하면 됨.

• 한 줄의 인라인 어셈블리로 큰 수 곱셈을 간단하게 만들 수 있음. C 언어에 확장 곱셈 개념을 추가했으면 함. 하드웨어 지원은 어디에나 있음.

• Fermat 테스트로 충분했는데, 소수가 실제로 소수가 아니면 알고리즘이 작동하지 않기 때문임. 하지만 암호화/복호화 메시지를 성공적으로 수행할 수 있는 비소수 P/Q 값이 존재하지 않는다고 증명될 수 있는지는 모르겠음.

• 프로젝트에 얼마나 걸렸는지 궁금함. 저자는 Karatsuba, Toom-Cook, 복소수 FFT, NTT, Schönhage–Strassen을 구현했음. Silverman의 'A Friendly Introduction to Number Theory'를 추천함.

• 큰 수를 곱하는 자체 코드를 작성했을 때 수학 논문의 고수준 설명을 실제 연산으로 옮기는 것이 얼마나 힘든지 공감됨. 기수 관련 설명에 약간의 문제가 있음.

• 수를 새로 생성하는 대신 2를 더하는 마지막 최적화는 보안을 약간 깨뜨림. 소수는 균등하게 분포되어 있지 않아서 큰 소수 간격 바로 다음에 오는 소수로 편향되기 때문임.

• Fermat의 소정리 설명에 약간 오류가 있음. a^(p-1)이 p로 나누어 떨어진다고 했는데 a^(p-1) - 1이 p로 나누어 떨어져야 함. 모듈러 산술 용어로는 맞게 설명됨.