The two whole numbers which, multiplied together, give 21 are of course 3 and 7. But which pair of numbers when multiplied together give 1,387? And which other pair give 2,835,773?
It is not often that I can set readers of The Irish Times a puzzle. Mathematicians have struggled for centuries for a general solution for this category of numerical challenges. When given a specific number as above, is there an efficient way to deduce which pair of numbers multiply together to give that result? The only hint is that the pair of factors is prime, each divisible only by itself and 1 – such as 3 and 7 above.
The difficulty in deriving the pair of prime factors of a given known number is the core defence intrinsic to many modern encryption systems, which in turn not only protect military systems but also underpin banking and most internet transmission schemes.
IT Business Person of the Year Barry Connolly: ‘I never really wanted to work for anyone else’
Barry Connolly, the man who brought Red Bull and Kopparberg cider to Ireland has just been named the Irish Times Business Person of the Year. After graduating from UCD with a degree in business, the Dubliner went on to work in advertising and sales at the Sunday Tribune, before moving into the world of entrepreneurship, where he worked alongside a number of successful brands. In 2016, he launched Fulfil, a range of protein bars which took the Irish market by storm. Last April, he sold the business for a reported €160 million to family-owned confectionery giant Ferrero. In this conversation with Ciaran Hancock, he looks back over his career trajectory, explains why Fulfil has become a hit with consumers and shares his top tips for budding entrepreneurs.
Until the mid-1970s, encryption schemes throughout history had relied on a secret key in principle known only to the sender and receiver. If the key is discovered, a third party can then decode the encrypted correspondence. Having to advise both parties of the secret key, and having copies of it in two different places, makes such encryption schemes vulnerable to attack.
In 1977, Ron Rivest, Adi Shamir and Leonard Adleman, three cryptographers at MIT in Boston, published their RSA algorithm (derived from their surnames) describing a practical asymmetric alternative. Their solution is still very widely used today. The sender uses one key, whilst the recipient uses a different key and yet can still decode the encrypted message. In practice, the recipient first chooses a secret pair of prime numbers. They are then multiplied together, and the resulting number is made public. Anyone – not just a single sender – who wants to send a secret message to the recipient encodes their message using the recipient’s “public key”. Because of the challenge of deducing the pair of prime factors of the public key, only the recipient can decode the message.
The challenge of deducing the pair of prime factors becomes harder the larger the number. RSA schemes typically use numbers with approximately 617 decimal digits (or, equivalently, 2,048 binary digits), although some use 1,234 digits (4,096 bits). It is generally considered that it would take a conventional computer many millions of years to break a 2,048-bit public key, let alone a 4,096-bit key.
However, a quantum computer may be able to do very much better. The binary digits of a conventional computer are in one of two states (0 or 1). A quantum computer uses “qubits”, each of which in principle can hold an infinite number of states. In fact, the accuracy of the control mechanism and interference limit the number of states possible in a quantum computer, but nevertheless the resulting computing power is immense.
The potential vulnerability to public key encryption systems from quantum computers has been recognised since the 1980s. A typical estimate is that a quantum computer with 20 million qubits would take about eight hours to break a 2,048-bit public key. But the largest announced quantum computer to date, the IBM Osprey, has only 433 qubits. It would seem that public key encryption might be safe for some time yet.
However, over Christmas, a number of Chinese academic researchers asserted that they had derived a new method, successfully breaking a 48-bit public key using a 10-qubit quantum computer. They predicted that they could break a 2,048-bit public key by using just 372 qubits, thus within the range of the IBM Osprey - although they themselves did not have access to such a machine.
Their approach corrects a flaw in an algorithm published in 2021 by Claus-Peter Schnorr, a retired mathematics professor in Frankfurt, who had theorised it would break RSA encryption. A number of US cryptographers have expressed strong doubts about the Chinese claims, believing it is highly unlikely that their method can sufficiently scale to threaten 2,048-bit public keys.
Conspiracy theories abound too. If some team somewhere with access to the latest generation of quantum computers can actually break public key encryption systems, would we necessarily be told? Given the backdrop of rising Chinese-American political tensions, why did the Chinese authorities allow some leading academics to publish their results? Could it be a hint that the Chinese have in fact already scaled their approach, and want to place uncertainty in the minds of US military strategists?
IBM expects to have a 1,000-qubit computer before the end of this year. Google wants to build a million-qubit computer by the end of the decade. Even if the Chinese researchers have not yet a full solution, their announcement is a timely alert to the increasing threats and fragility of the public key encryption schemes so widely used today.
Did you solve my two puzzles? The first pair is 19 and 73, giving 1,387. The second is 1,399 and 2,027, giving 2,835,773.
