The Power of Prime Numbers: Generating arbitrarily large primes

Saturday - July 15 2023, 08:45 UTC - 1 year ago

Prime numbers have been studied for centuries.Constructing large prime numbers is complicated, and can be done with either a random approach with a risk of inconsistency or a deterministic approach with heavy computational costs. In May, a team of scientists showed that a kind of hybrid approach could be used to output a prime number of a specific length with a high probability of getting the same prime number even if the algorithm is run multiple times.

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." .

The challenge of making an efficient recipe for primes has deep roots. "We really don’t know that much about how primes are distributed, or about gaps in primes," said Ofer Grossman, who studies pseudorandom algorithms. And if we don’t know where to find them, there’s no easy way to generate a prime number from scratch.

Over time, researchers developed the aforementioned approaches. The simplest way is just to guess. If you want a prime with 1,000 digits, for example, you could pick a 1,000-digit number at random and then check it. "If it’s not prime, you just try another one, and another, and so on until you find one," said Rahul Santhanam, a computer scientist at the University of Oxford and co-author of the new paper. "Because there are many primes, this algorithm will give you some number that’s prime with a high probability, after a relatively small number of iterations." But using randomness means you’ll likely get a different number every time, he said. That could be a problem if you need consistency — if, say, you’re employing a cryptographic method of security that depends on the availability of large primes.

The other approach is to go with a deterministic algorithm. You could pick a starting point and start testing numbers, sequentially, for primality. Eventually you’re destined to find one, and your algorithm will consistently output the first one you find. But it could take a while: If you’re looking for a prime number with 1,000 digits, even a calculation with 2500 steps — which would take much longer than the age of the universe — is known to be insufficient.