How can I check the primality of extremely large numbers such as those used in RSA, in Linux?
RSA is guaranteed to use prime numbers. In fact, if the numbers were not primes, RSA key operations would simply not work (with overwhelmingly high probability). However, the OpenSSL command line utility has the ability to check the primality of a number using Miller-Rabin primality testing, the standard test algorithm for checking large primes for use in cryptography:
OpenSSL> prime No prime specified options are -hex hex -checks <n> number of checks -generate generate prime -bits <n> number of bits -safe safe prime error in prime OpenSSL> prime -generate -bits 256 315016830147073940139675761214468273143 OpenSSL> prime 315016830147073940139675761214468273143 ECFE08DCA281B26A5EDDE8DF7D2A33F7 is prime OpenSSL> prime 10000000000000 9184E72A000 is not prime
I believe the default number of checks is 64, but you can increase this to improve accuracy using the
-checks option. Each check runs one Miller-Rabin test round which individually has a 75% chance of detecting that a composite number is indeed composite. Specifically, the chance of failing to identify a composite number as such is 4-n, where n is the number of rounds used. With the default of 64 rounds, this is 4-64, or 2-128. To put that into perspective, if you put a composite number through 64 rounds of M-R primality testing, the chance that it is falsely labeled a prime is equivalent to the chance of correctly guessing a 128-bit encryption key on the first attempt.
I explained more about primality testing in OpenSSL in another answer.