2

I'm generating numbers using a Java program (BigIntegers) and I want to know if there's a binary readily available that I could use to run primality tests on the numbers generated.... suppose I feed them through a pipe from my java program into the binary. Is it out there? I'm trying to find packages for aks on apt but I see nothing "straightforward", only libs that I could use to program stuff (like, based on GMP).

Improve this question
1

2 Answers 2

Reset to default
6

openssl

The program openssl does primality tests:

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

The command is listed with help (openssl help):

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

And the details of the actual command are given by (-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

Very long numbers are also possible (2^521)-1 (Mersenne number with 157 decimal digits):

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

Two other utilities not connected to openssl but related to primes are:

Primes and factor:

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

Quite close to the max (signed) 64 bit integer number:

$ printf '%X\n' 18446744073709551559 $(( (2<<63) - 1 )) FFFFFFFFFFFFFFC7 FFFFFFFFFFFFFFFF
Improve this answer
9
  • 1
    Note that GNU coreutils (like some other Unices such as Solaris) has factor but not primes (even though both were introduced in Unix v7 in the late 70s). FreeBSD factor seems to support larger numbers than GNU factor. ITYM primes 10 50 | xargs -n1 openssl prime instead of openssl prime primes 11 13 17 19 23 29 31 37 41 43 47 Commented Aug 5, 2017 at 13:55
  • 1
    Good find about openssl prime BTW. It doesn't seem to be documented. Even the help message with the version on my system doesn't mention the -generate/-bits option. To find out about the -checks option (20 by default as seen in the code), you need to look at the BN_is_prime_ex(3) man page that says it performs a Miller-Rabin probabilistic primality test with nchecks iterations. Commented Aug 5, 2017 at 14:16
  • The primes I have reports BSD Games Manual, so yes it should be from BSD (one of them). But it fails above 32 bits, it lists as primes numbers like 65539 square (4295360521). The number of incorrect primes grows as closer it gets to 64 bits. So, the (February 3, 2008) BSD primes has at least this (important) bug. @StéphaneChazelas Commented Aug 7, 2017 at 1:21
  • GNU factor support quite large numbers, from the manual: factoring the eighth Fermat number 2^{256}+1 takes about 20 seconds on the same machine. Assuming the large number option was compiled in (read info factor). Commented Aug 7, 2017 at 1:22
  • 1
    Really @StéphaneChazelas ? Open ssl 1.1.0 was released on (25 Aug 2016), close to a year ago. Openssl must be updated as soon as possible, there are many vulns to correct, it is presently at 1.1.0f, the fifth release of that version. Please update as soon as possible. And it is openssl prime, without the s. Commented Aug 7, 2017 at 17:05
0

There is a primesieve-bin package:

$ sudo apt install primesieve-bin $ primesieve 20 -p 2 3 5 7 11 13 17 19

to check that a number is prime, you could do:

$ test $(primesieve 11 -p | tail -1) -eq 11 $ echo $? 0 $ test $(primesieve 12 -p | tail -1) -eq 12 $ echo $? 1

EDIT: Not recommended since openssl primes is much faster for that task (as pointed out in the comments).

Improve this answer
4
  • The OP wants to test a number (e.g., 43) to see whether it is prime.  How can they do that with this tool?  … … … … … … … … … … …  Please do not respond in comments; edit your answer to make it clearer and more complete. Commented Aug 3, 2024 at 11:51
  • This seems to be a terrible option for testing if something is a prime. openssl prime 18446744073709551557 returned pretty much immediately on a Raspberry Pi 4B, but prinesieve --dist 1 18446744073709551557 has been running for over an hour on the same system (64 minutes now and counting). Commented Aug 3, 2024 at 13:08
  • That is true @muru . I think the reason is that openssl uses a specialized algorithm for that task called Miller–Rabin primality test Commented Aug 3, 2024 at 18:36
  • Yes, I know. I'm just saying that this tool is impractical for any numbers of real interest. The invocation I mentioned earlier is still running, 27 hours later. Testing the primarily of, say, p from an 4096-bit RSA key would probably require creating a new universe. Commented Aug 4, 2024 at 15:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.