How to build a big prime number
Prime numbers are tricky things. We learn in school that they’re numbers with no factors other than 1 and themselves, and that mathematicians have known for thousands of years that an infinite number of them exist. Producing one on command doesn’t seem as if it should be difficult.
But it is. Constructing arbitrarily large prime numbers is remarkably complicated. You basically have two computational options, both with drawbacks. You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. Or you could use a more reliable, deterministic algorithm, but at a heavy computational cost.
In May, a team of computer scientists showed that a kind of hybrid approach could also work. They published an algorithm that effectively combines the random and deterministic approaches to output a prime number of a specific length, with a high probability of delivering the same one even if the algorithm is run many times. The algorithm connects randomness and complexity in interesting ways, and it might also be useful for cryptography, where some encoding schemes rely on the construction of big primes.
“They laid out a sequence of attempts, each of them trying to construct a prime number of a different length, and showed that one of the attempts works,” said Roei Tell, a theoretical computer scientist at the Institute for Advanced Study who was not involved with the work. “It’s a construction that outputs a deterministically chosen prime, but allows you to toss coins and make random choices in the process.”