▲neo 7달전 | parent | favorite | on: GN⁺: 1024비트 소수 생성의 어려움(glitchcomet.com)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로 나누어 떨어져야 함. 모듈러 산술 용어로는 맞게 설명됨.
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로 나누어 떨어져야 함. 모듈러 산술 용어로는 맞게 설명됨.