Let's break down the maths that could potentially "crack" RSA cryptography in a simple way.

Imagine you want to send a secret message. One common way to do this is using something called RSA cryptography. It's a popular method for encoding and decoding secure communications. The clever part about RSA is that it uses really big prime numbers.

Here's the main idea:

It's quite easy for computers to find really large prime numbers.
It's also easy for computers to multiply two of these large prime numbers together to get an even bigger number.
But, here's the tricky bit – it's really, really hard for a computer to do the opposite: start with that big number and figure out which two prime numbers were multiplied to get it. These original prime numbers are called the prime factors.

Think about the number 35. Its prime factors are 5 and 7 because 5 multiplied by 7 equals 35, and both 5 and 7 are prime numbers. For a small number like 35, you can probably just guess the factors or quickly check small prime numbers (like 2, 3, 5, etc.). But for a number that's hundreds of digits long, checking every possibility would take a computer a very, very long time.

In RSA, these big prime factors are like secret keys used to unlock and read (decrypt) messages. So, if someone wanted to secretly read a message (eavesdrop), they would need to find these prime factor keys. This means they need a way to quickly find the prime factors of a very large number used in the cryptography.

Where Clever Maths Comes In

This is where some clever maths comes in, partly thanks to a mathematician named Euler. He thought a lot about prime numbers and something called modular arithmetic.

Modular arithmetic is like counting in a circle. Think about a clock – it counts up to 12, and then goes back to 1. That's like counting "mod 12." In modular arithmetic, you're interested in the remainder when you divide one number by another.

Example:

2 multiplied by 3 is 6.
What is 2 times 3 "mod 5"? Well, 6 divided by 5 has a remainder of 1.
So, 2 times 3 is "congruent to" 1 mod 5.

Euler’s Discovery: Cycles and Periods

Euler noticed a cool pattern when you take a number and raise it to different powers (like 3 to the power of 1, 3 to the power of 2, 3 to the power of 3, and so on) and then look at the result using modular arithmetic.

For example, let's look at the powers of 3, "mod 10" (just looking at the last digit):

3 to the power of 1 is 3 (mod 10 is 3)
3 to the power of 2 is 9 (mod 10 is 9)
3 to the power of 3 is 27 (mod 10 is 7)
3 to the power of 4 is 81 (mod 10 is 1)
3 to the power of 5 is 243 (mod 10 is 3)
3 to the power of 6 is 729 (mod 10 is 9)

Notice the pattern: 3, 9, 7, 1, then it repeats. This repeating section (3, 9, 7, 1) is called a cycle, and the length of this cycle is called the period. In this case, the period is 4.

The important thing about the period ('r') is that it's the smallest number where your starting number ('a') raised to the power of 'r' is "congruent to 1 mod N." So, 3 to the power of 4 is congruent to 1 mod 10.

How This Helps Break the RSA Code

The four-step process uses this idea to find the prime factors (p and q) of a large number N (where N = p × q). This process is the basic idea behind something called Shor's algorithm.

Here are the steps, made simple:

Step 1: Pick a number 'a'.
Choose any number 'a' that is smaller than N. Check if 'a' and N share any prime factors. A quick way to do this is by finding their Greatest Common Divisor (GCD) – the largest number that divides both 'a' and N.

If the GCD is 1, they don't share factors, and you can go to Step 2.
If the GCD is bigger than 1, congratulations! You've found a factor of N right away, and you can stop.

There’s a quick way to find the GCD called the Euclidean algorithm.

Step 2: Find the period 'r'.
Find the period 'r' for your chosen number 'a' when you calculate its powers "mod N".
This is the smallest positive number 'r' such that 'a' raised to the power of 'r' is congruent to 1 mod N.
This is the step that usually takes a very long time for big numbers on a regular computer.

Step 3: Check 'r' and a^(r/2) + 1.
For the final step to work nicely:

The period 'r' must be an even number.
The number 'a' raised to the power of (r divided by 2), plus 1, must not be congruent to 0 mod N.

If either of these conditions isn't met, you have to go back to Step 1 and pick a different number 'a'. Luckily, there's a good chance (at least 50%) that your first pick for 'a' will work.

Step 4: Find the factors using GCD.
One of the prime factors (p) will be the GCD of (your number 'a' raised to the power of r/2, minus 1) and N.
The other prime factor (q) will be the GCD of (your number 'a' raised to the power of r/2, plus 1) and N.

Worked Example: Factoring 35

Let's walk through an example:

N = 35

Step 1: Pick a number 'a'.
The example uses 'a' = 8.

The GCD of 8 and 35 is 1, so they are relatively prime. Good.

Step 2: Find the period of 8 mod 35.

The period 'r' is 4.

Step 3: Check conditions.

'r' is even (r = 4).
Check a^(r/2) + 1:
- 8^(4/2) + 1 = 8² + 1 = 64 + 1 = 65
- 65 mod 35 = 30, so it is not congruent to 0. Good.

Step 4: Calculate the GCDs:

p = GCD(8² - 1, 35) = GCD(64 - 1, 35) = GCD(63, 35) = 7
q = GCD(8² + 1, 35) = GCD(64 + 1, 35) = GCD(65, 35) = 5

Thus, the factors are 7 and 5, and 7 × 5 = 35.

Why RSA Is Still Safe

These steps show a mathematical way to find the prime factors of a large number. However, Step 2—finding the period 'r'—takes an incredibly long time for a normal computer when working with huge numbers. That’s why RSA remains safe today.

The Quantum Twist

Here’s the twist:
Finding the period is exactly the kind of problem that a quantum computer is very good at solving quickly. The four steps described form the basis of Shor's algorithm, which proposes using a quantum computer specifically to speed up that difficult Step 2.

If we can build large and stable quantum computers in the future, Shor's algorithm could potentially make finding the prime factors of huge numbers fast enough to break RSA cryptography. This is why people are urgently looking at new ways to secure information against potential quantum computer attacks.

Fun Fact

Mersenne primes are huge, basically useless—and totally irresistible. They don’t secure your data or run your apps. People hunt them anyway, just for the thrill of finding something massive and rare.