Prime Numbers, Encryption and the Linux Factor Command
Have you ever needed to print the prime factors of a number on the Linux command line? Me neither. However, a tool does exist for it. Enter the factor command.
The factor command is part of the GNU Core Utilities package, therefore it is available on almost any Linux system. This little beauty has the singular purpose of producing the prime factors of any number. To me, this is pretty neat. To anyone interested in learning cryptography or number theory, this may be a useful, if not fun, little utility.
Prime Numbers and Prime Factors
Prime numbers have long been subjects of great interest to mathematicians, especially in the field of combinatorics. They are interesting because they are whole numbers that are only divisible by themselves and one. For example, the only way to multiply two whole numbers together to produce '5' is '5 x 1=5', whereas '6' factors by '3x2=6' as well as by one and itself.
Six is a composite number, numbers that are not prime numbers.
According to Wolfram-Alpha, a Mersenne prime is a prime that fits the formula M = 2^n - 1. Or, one subtracted from any power of 2. They were named for Martin Mersenne, a 17th-century French monk that studied the numbers. There exists an infinite number of Mersenne prime numbers.
Prime numbers can get large in and of themselves: the current, largest prime number has 24,862,048 digits!
Multiplying prime numbers together, even large ones is a straightforward task. The product of two prime numbers is called a semi-prime. A cheap desk calculator can do this with ease. Plenty of people can count by prime numbers and multiply big numbers without paper using a variety of techniques.
Prime factors are a different problem altogether. Any composite number can be made up of many different combinations of prime numbers.
Simply put, prime factors are the prime numbers that can be factored from any number, other than 1 and itself.
Factoring is the process of breaking down a number into the two numbers originally multiplied together. For example, 9 is the product of the prime number 3 and itself. This seems simple with very small numbers like 9, especially if you've had experience factoring hundreds of polynomials in high school. As with polynomials, prime factors become infinitely more complex the larger the numbers involved.
Big Prime Number, Big Problem
Multiplying big prime numbers, while still relatively easy, results in even bigger non-prime numbers. The number 330 has prime factors of 2, 3, 5, and 11. The larger your numbers get the more possible factorizations. Now, go through one by one and multiply each of those prime numbers together in different combinations until you get 330. Not impossible, but certainly more difficult than 9.
Factoring very large numbers, like the Mersenne prime numbers can take powerful computers years to complete.
Any method used to multiply and divide large numbers is useless when factoring prime numbers. Prime factors can only be found through trial and error. To find the correct pairing of primes to factor requires testing every prime against each other from 2 up to the nth prime, except for one and the very large number in question.
Linux and its Factor command use an algorithm called Pollard-Brent Rho to derive prime factors for relatively small numbers. The algorithm is quite powerful and can calculate the eighth Fermat number, 2^256+1 in approximately 20 seconds, depending upon hardware constraints. Distributions not using the GNU MP will have reduced capability with this command.
Prime Factors and Encryption
Cryptography is an essential aspect of modern society. Computers transfer data to other computers all over the world every nanosecond of every day. Threats to the security and accuracy of information pathways challenge hardware and infrastructure improvements as fast as they are conceived.
Globally, industries rely on encryption protocols to protect themselves and, sometimes only tangentially, consumers from identity theft, fraud, and violations of privacy. Prime factors are very useful in creating encryption keys to secure information over digital transmission media.
Because all composite numbers are made up of prime numbers, any composite number can be used as the public key, that allows messages to be encrypted. Only those in possession of the secret key can decrypt the message into plain text.
So any public key will be a very large composite number. The secret key will be the very large prime numbers, otherwise known as the prime factors of the composite number.
Prime factor cryptography guarantees security and privacy by creating a factorization problem that even supercomputers, let alone the most advanced consumer electronics, would be hard-pressed to solve within a century. Because of this, some law enforcement entities seek to restrict cryptography and prime factor usage to prevent freedom fighters and terrorists alike from obtaining secure means of communication.
It is fairly common to hear or read the phrase 1024-bit encryption. This describes the number used for the public key. The public key number used will be an integer with more than 2^1023 digits but less than 2^1024 digits. The secret key would be the two primes that produce this integer.
While modern supercomputers cannot crack this encryption in any reasonable amount of time, quantum computing will eventually render this method useless.
Linux Factor Command
As nifty as the Factor command may be, it is not useful in modern cryptography. Since Factor cannot find the prime factors of large numbers within any reasonable amount of time, it would be to simplistic for modern cryptography. But it is useful for learning cryptography basics or simply enjoying the elegance of numbers.
Factor Command Syntax and Options (or lack thereof)
The factor command has no functional options. The only options that exist are --help and --version. It simply takes a argument or list of arguments in the form of an integer number. It will also accept an integer from standard input (STDIN).
[mcherisi@putor ~]$ factor 11
[mcherisi@putor ~]$ factor 77
77: 7 11
[mcherisi@putor ~]$ factor 34578 11 77
34578: 2 3 3 17 113
77: 7 11
The Linux factor command is a cool bit of computing history and it's interesting that it has remained a part of Unix since 1979. In 1986, Paul Rubin wrote a free software version of factor for the GNU project.
Some UNIX/Linux variants consider factor a game rather than a utility.The current GNU documentation categorizes Factor as a numerical operation, which makes more sense in my opinion. It finds use with number theorists, number enthusiasts, and when you require simple derivation of prime factors.
Resources and Links
This site uses Akismet to reduce spam. Learn how your comment data is processed.