REARY 큰 소수 생성

나는 놀고있어 RSA 구현을 작성하려고합니다. 문제는 키 쌍을 생성하는 데 필요한 대규모 소수를 생성해야한다는 것입니다. 누군가가 거대한 소수/확률을 생성하는 빠른 방법을 가르쳐 주시겠습니까?REARY 큰 소수 생성

정확하게 소수를 생성하지 마십시오. 무작위로 큰 홀수를 생성 한 다음, 그 수가 소수인지 테스트합니다. 다른 수가 무작위로 생성되지 않으면 테스트합니다. 임의의 시도를 통해 소수를 "치는"확률은 (2/ln n)

입니다. 예를 들어, 512 비트 임의의 소수를 원할 경우, 1/2 (512 * ln (2)) 시도하는 숫자의 약 177 개가 소수입니다.

숫자가 소수인지 테스트 할 수있는 방법은 여러 가지가 있습니다. 위에 언급 한 "Miller-Rabin 테스트"가 좋습니다. 거의 균일 무작위 증명 (콘트라스트 통계적 높은 확률) 소수를 생성 의한 U. 마우어하는 알고리즘이있다

$ openssl prime 119054759245460753 
1A6F7AC39A53511 is not prime

2009-07-20 23:57:27 mox1

감사합니다. 이것은 제가 가지고 있던 많은 문제를 설명합니다. – computergeek6

당신은 openssl에서도 소수를 생성 할 수 있습니다 :'openssl prime -generate -bits 512' – mykhal

TrueCrypt이 어떻게 수행되는지 살펴보십시오. 또한 큰 pseudoprimes 테스트를 위해 Rabin-Miller을 살펴보십시오.

2009-07-18 00:31:12

왜 TrueCrypt가 소수를 생성한다고 가정합니까? 내가 아는 한 대칭 암호화 만 사용합니다. – CodesInChaos

사용중인 언어를 언급하지 않았습니다. 예를 들어, java에서는 BigInteger에서 nextProbablePrime()을 호출하는 것처럼 간단합니다.

2009-07-18 00:32:19

Objective-C를 사용하고 있습니다. – computergeek6

기능이 어떻게 구현되는지에 따라 검색 공간이 줄어들면 주요 선택 항목이 손상 될 수 있습니다. – Stephen

이전의 대답은 잘못된 것입니다 : 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30,031 = 509 *

59 내가 거기에 있다는 포스터는 (실제) 증거를 misremembering 생각입니다은 무수한 소수.

2009-07-18 01:42:30

실제로, 셀 수있는 (그러나 무한한) 소수 만 있습니다. 또한 다른 포스터 (게시물이 삭제 된 것으로 보임)는 증거에서 구조를 잘못 리마 르하지 않고 (오히려 실제로 그게 어떻게되는지) 오히려 그것을 오용하고 있습니다. – oggy

사실. 정수는 셀 수 있으며 "1, 2, ..."가됩니다. 소수도 마찬가지입니다. 그것은 셀 수없는 실수입니다. – jrockway

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

2009-07-20 07:34:16 albertjan

또한 OpenSSL을는 소수에 대해 테스트 할 수있는 좋은 유틸리티를 갖는다 특별한 크기의 모든 소수의 집합에 분산된다. 상당히 효율적인 Python 구현을 가지고 있습니다. http://s13.zetaboards.com/Crypto/topic/7234475/1/

2015-01-20 11:36:05

답변