☰

소수성 테스트 바이너리

tag-icon • tag-icon java math
소수성 테스트 바이너리

숫자를 생성하기 위해 Java 프로그램(BigIntegers)을 사용하고 있으며 생성된 숫자에 대한 소수 테스트를 실행하는 데 사용할 수 있는 바이너리가 있는지 알고 싶습니다. 파이프를 통해 Java 프로그램에 공급한다고 가정합니다. 바이너리 파일을 입력하세요. 밖에 있나요? apt에서 aks에 대한 패키지를 찾으려고 했지만 "직접적인" 것은 아무것도 보이지 않았고 프로그래밍할 수 있는 라이브러리(예: GMP 기반)만 표시되었습니다.

답변1

OpenSSL

openssl 프로그램은 소수성 테스트를 수행합니다.

$ a=31
$ openssl prime 31
1F (31) is prime

$ openssl prime 18446744073709551557      
FFFFFFFFFFFFFFC5 (18446744073709551557) is prime

명령은 help() 로 나열됩니다 openssl help.

$ openssl help 2>&1 | grep prime
pkeyparam         pkeyutl           prime             rand

-help실제 명령의 세부 사항은 (or)로 제공됩니다 --help.

$ openssl prime -help
Usage: prime [options] [number...]
  number Number to check for primality
 -help         Display this summary
 -hex          Hex output
 -generate     Generate a prime
 -bits +int    Size of number in bits
 -safe         When used with -generate, generate a safe prime
 -checks +int  Number of checks

매우 긴 숫자도 가능합니다(2^521)-1(십진수 157자리의 메르센 수):

$ time openssl prime $(BC_LINE_LENGTH=0 bc <<<'2^521-1')
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151)
is prime

real    0m0.042s

openssl에 연결되지 않지만 소수와 관련된 두 가지 다른 유틸리티는 다음과 같습니다.

소수 및 인수:

primes - 범위 요인에서 소수 생성 - 요인 수

$  echo $(primes 10 50)
11 13 17 19 23 29 31 37 41 43 47

$ openssl prime 11 13 17 19 23 29 31 37 41 43 47
B (11) is prime
D (13) is prime
11 (17) is prime
13 (19) is prime
17 (23) is prime
1D (29) is prime
1F (31) is prime
25 (37) is prime
29 (41) is prime
2B (43) is prime
2F (47) is prime

$ factor 11 13 17 19 23 29 31 37 41 43 47
11: 11
13: 13
17: 17
19: 19
23: 23
29: 29
31: 31
37: 37
41: 41
43: 43
47: 47

$ factor 18446744073709551557
18446744073709551557: 18446744073709551557

$ factor 18446744073709551559
18446744073709551559: 41 163 269 8807 1165112831

가장 큰(부호 있는) 64비트 정수에 매우 가깝습니다.

$ printf '%X\n' 18446744073709551559 $(( (2<<63) - 1 ))
FFFFFFFFFFFFFFC7
FFFFFFFFFFFFFFFF

관련 정보