Abstract:
Prime numbers are deceptively simple yet incredibly powerful. They are the foundation of modern cryptography, securing everything from online banking to national security. But what if this foundation crumbles? Classical computers struggle to factor large numbers, making modern cryptosystems safe—for now. However, in 1994, Peter Shor devised a quantum algorithm that could break RSA in polynomial time. Though current quantum hardware is too limited for large-scale attacks, rapid advancements suggest this won’t be the case forever.
In my project, I explore a quantum-safe defence: cryptographic systems based on non-abelian groups, where operations don’t commute (i.e., a*b ≠ b*a). a
____
Prime numbers have always been a curious subject in mathematics. They’re simple, indivisible numbers, yet even identifying them is far from straightforward. For example, 499 is a prime number. So is 4 999. But what about 49 999? Yes, it’s also prime! Ok, sure, what about 499 999? It ‘looks’ pretty prime to me. But it turns out, it is not; it can be factored into 31 * 127^2. The difficulty in determining the prime factors of a number has intrigued mathematicians for centuries. But beyond pure curiosity, prime numbers have fascinating, practical applications, especially in the world of cryptography.
One of the key uses of prime numbers today is in securing digital communication. Cryptosystems like RSA (Rivest-Shamir-Adleman) rely on the difficulty of factoring large numbers. The RSA algorithm underpins much of the security we rely on when browsing the internet, ensuring that your data remains private from prying eyes.
Currently, even one of the best-known factoring methods, the General Number Field Sieve, takes sub-exponential time in the size of the input. This means that it may well take eons to decrypt an RSA cryptosystem with large enough numbers to factorise using current methods.
However, in 1994, mathematician Peter Shor shattered this paradigm with an algorithm that factors integers in polynomial time on a quantum computer. If realised at scale, Shor’s algorithm would render RSA and similar systems obsolete. Yet, today’s quantum computers lack the stable, error-corrected qubits needed for practical attacks. Currently, the largest number reliably factored via Shor’s algorithm is 21.
Despite this, tech giants like Amazon and Microsoft are rapidly advancing quantum hardware, developing chips with increasing sophisticated qubit architectures. These strides suggest a shrinking timeline for looming quantum threats.
Adversaries are already stockpiling encrypted data, anticipating that future quantum advancements will enable them to decrypt today’s secrets—a tactic commonly termed the “harvest now, decrypt later” strategy. With this threat looming, governments and corporations are now racing to adopt quantum-resistant cryptography. Notably, the Australian Signals Directorate has mandated that organisations transition away from non-quantum-safe cryptographic protocols by 2030.
In my project, I look at shortcomings in Shor’s algorithm when applied to non-abelian groups – these are groups where the group operation isn’t commutative (So, a*b is not equal to b*a). Some well-known examples include symmetric, dihedral and matrix groups.
I explore non-abelian groups as a potential foundation for quantum-resistant cryptography.
Shirley Wang
The University of Sydney
