정말 큰 프라임을 생성합니다

Question

나는 놀고 있고 RSA의 구현을 쓰려고 노력하고 있습니다. 문제는 키 쌍을 생성하는 데 관여하는 거대한 소수를 생성하는 데 갇혀 있다는 것입니다. 누군가가 거대한 프라임/가능한 프라임을 생성하는 빠른 방법을 알려줄 수 있습니까?

Answer 1

소수를 정확히 생성하지 않습니다. 무작위로 큰 홀수를 생성 한 다음 다른 홀수를 무작위로 생성하지 않으면 해당 숫자가 프라임인지 테스트합니다. 기본적으로 임의의 시도를 통해 프라임을 "치는"확률을 기본적으로 말하는 소수의 일부 법칙이 있습니다 (2/ln n)

예를 들어, 512 비트 랜덤 소수를 원한다면 2/(512*ln (2))에서 하나를 찾을 수 있으므로 시도하는 숫자 중 177 개 중 약 1 개가 프라임이 될 것입니다.

숫자가 프라임인지 테스트하는 방법에는 여러 가지가 있습니다. 좋은 것은 "Miller-Rabin Test"입니다. 이 질문에 대한 또 다른 답변에 언급 된 바와 같이.

또한 OpenSSL은 프라임 테스트에 좋은 유틸리티를 가지고 있습니다.

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

방법을 살펴보십시오 truecrypt 그렇게합니다. 또한 살펴보십시오 라빈 밀러 큰 유사 형을 테스트하기 위해.

Answer 3

당신은 당신이 어떤 언어를 사용하고 있는지 언급하지 않았습니다. 일부는이 내장을 수행하는 방법이 있습니다. 예를 들어, Java에서는 전화만큼 쉽습니다. NextProbablePrime () Biginteger에.

Answer 4

이전 답변이 잘못되었습니다. 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.

나는 포스터가 소수의 수가 없다는 (실제) 증거를 잘못 기억하고 있다고 생각합니다.

Answer 5

모노는 Java와 마찬가지로 오픈 소스 인 Biginteger 클래스를 가지고 있습니다. 당신은 그것들을 볼 수 있습니다. 아마 휴대용 :) g'luck

Answer 6

U. Maurer로 인한 알고리즘이있어 임의의 입증 가능 (통계적으로 고도로 확신 할 수있는) 프라임이 특수 크기의 모든 프라임 세트에 거의 균일하게 분포되어 있습니다. 상당히 효율적인 파이썬 구현이 있습니다.http://s13.zetaboards.com/crypto/topic/7234475/1/