Java Biginteger 소수

Question

나는 Biginteger 유형의 임의의 소수를 생성하려고 노력하고 있습니다. 즉, 공급하는 최소와 최대 값 사이입니다.

나는 biginteger.probableprime (int bitlength, random)을 알고 있지만, 비트 길이가 출력 된 프라임의 최대/최소값으로 변환되는지 확실하지 않습니다.

감사합니다, Steven1350

Answer 1

BigInteger.probablePrime(bitLength, random) 지정된 비트 길이의 (가능한) 프라임을 반환 할 것입니다. 이는 최대 2^비트 길이 -1의 최대 값과 최소 2^(비트 길이 -1)로 해석됩니다. 내가 답으로 싫어하는만큼, 당신이 숫자 이론을 탐구하기 시작하지 않는 한 아마도 당신의 최선의 방법 일 것입니다.

당신이해야 할 일은 범위가 요구하는 비트 길이를 파악한 다음 probablePrime() 올바른 범위에있는 프라임을 되 찾을 때까지.

Answer 2

Max/Min이 1에 가깝지 않으면 Jprete의 대답은 괜찮습니다.

범위가 좁다면 가장 좋은 방법은 아마도 다음과 같은 일을하는 것입니다.

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

그만큼 프라임의 밀도 전반적으로 상당히 높고 기본적으로 로그 (x)에서 1이므로 소수를 찾기 위해 너무 많은 시간을 반복 할 필요가 없습니다. (예 : 예를 들어 : 약 10 숫자²³, 평균 52 개의 정수 중 하나는 소수입니다. 위의 코드는 6 개의 숫자 중 2 개 중 2 개만 귀찮게하므로 약 10 숫자에 대해 평균 17 배를 반복하게됩니다.²³.)

좋은 원시 테스트가 있는지 확인하고 Java Biginteger에는 하나가 있습니다.

독자를위한 연습으로 위의 기능을 확장하여 30k + x (모듈로 30, 항상 복합재, 8 개만 남아있는 22 개 모듈은 또는 210K를 사용하여 더 많은 복합 숫자를 미리 필터링합니다. + x.

편집 : 참조하십시오 미국 특허 #7149763 (OMFG !!!)