teste binário primality

Question

Estou gerando números usando um programa Java (BigIntegers) e quero saber se há um binário prontamente disponível que eu poderia usar para executar testes de primalidade nos números gerados ... suponha que eu os alimente por um cano de meu programa java no binário. Está lá fora? Eu estou tentando encontrar pacotes para aks no apt mas não vejo nada "simples", apenas libs que eu poderia usar para programar coisas (como, baseado em GMP).

    

Answer 1

openssl

O programa abre os testes de primalidade:

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

$ openssl prime 18446744073709551557      
FFFFFFFFFFFFFFC5 (18446744073709551557) is prime

O comando é listado com ajuda ( openssl help ):

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

E os detalhes do comando real são dados por ( -help ou --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

Números muito longos também são possíveis (2 ^ 521) -1 (número de Mersenne com 157 dígitos decimais):

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

real    0m0.042s

Dois outros utilitários não conectados ao openssl, mas relacionados a primos, são:

Primes e fator:

primes - generate primes in a range factor - factor numbers

$  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

Muito próximo do número inteiro máximo (assinado) de 64 bits:

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