Crypto Math Crash Course: What is 50^300,000,000,003 (mod 221) ?

In the last post I introduced the concept of quotient rings and these will be crucial for todays episode. If you dont know them, please first check out that post, otherwise what I do here might sound somewhat strange.

source

In this post I will define a second ring living on top of a quotient ring. The ring is generated by repeated multiplication ( = exponentiation). Lets look at quotient ring and find out what happens when I compute the various exponentiations of a number m for different exponents n. As an example I choose the quotient ring of 7. Then
1ⁿ=1
but
2¹=2, 2²=4, 2³=1, 2⁴=2 and it starts repeating from there.
We find the sequence 2 → 4 → 1 ↪ 2; a new ring that is living on top of the quotient ring to the number 7.
Similarly 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1, 3⁷=3 is generating the closed sequence
3 → 2 → 6 → 4 → 5 → 1 ↪ 3

You can try for some other combinations and always find closed rings with varying number of elements that seem to have little understandable structure. Actually there is a lot that can be said about them, but that would be another post on its own. Here I want to focus on the essentials and explore the overall structure of these rings.

The first statement is that the sequence of numbers always must be periodic simply because the underlying quotient ring has only a finite number of elements and exponentiation is a deterministic process. Furthermore it can never include the number 0, unless this is the starting element, since exponentiation does not add new prime factors. Therefore the maximum possible length of the ring (until numbers start repeating) is the quotient base minus one, removing the zero.

The further structure of these rings depends a lot on whether the underlying quotient ring is based on a prime or non-prime number. We will now first explore the more simple prime case.

In that case the ring starting from the number m always has to include the 1. This is because the ring has to close and the last number before closing has the be the 1 as only 1⋅m=m. This is guaranteed by the existence of an inverse in the prime based quotient rings. Suppose there would be a number n such that n*m = m. Then using that an inverse to m exists we immediately find that n = 1 by multiplication with that inverse. In addition the number that comes before the 1 has the be the inverse of m as only m⁻¹m=1.

We see this demonstrated nicely for the ring 3ⁿ above that includes the 1 at the final position and the element before is 3⁻¹=5. This ring also closes after the maximum possible p−1=6 steps, hitting all the non-zero elements in the quotient ring (in a seemingly random order). But what about the ring 2ⁿ that closes after only 3 steps?

We have already seen that the rings maximum length, based on the prime p, is p-1. But in fact it can close already before that. Suppose we have a number n such that the ring closes after p-1 elements, or put in math nᵖ=n.

This implies that for a second number m=n², we run through the same ring of n, only twice as fast since mᵏ=n²ᵏ. In our example above n would be 3 and m=3²=2. 3 generates the ring 3 → 2 → 6 → 4 → 5 → 1 ↪ 3 while 2 generates 2 → 4 → 1 ↪ 2, hitting exactly every second element in the first ring.

When we potentiate any number n: m=nᵏ, we use the ring of n, but always jump over k-1 elements. There are two distinct cases. First, if the length l of the ring generated from n can be divided by k, then after l/k steps we are already back at the beginning. The new ring generated by m does not close at l, but at l/k elements. This is the case for k = 2 (the square numbers) in our example above as l = (p-1) = 6 can be divided by 2 and then generates a ring of length 3.

But there is also the case where l cannot be divided by k. In that case we move thorough the ring of n jumping k elements each step, but keep missing m for some while. If k is coprime to l we only close after l steps after hitting every possible element. Otherwise we may close early after l divided by the shared prime factors. In our example only k = 5 is a coprime to the length of 6. 3⁵=5 and consequentially we find a ring of maximum length of 6 generated form potentiating 5: 5 → 4 → 6 → 2 → 3 → 1 ↪ 5

Now we have studied the length of all possible rings but one may wonder why this could be interesting. Given our findings we can formulate a very powerful statement: nᵖ⁻¹=1 (mod p).
It is obviously true for rings closing after the maximum allowed p-1 elements, but also for for the ones that are closing earlier as they have (p-1)/k elements for k a positive integer that is not coprime to (p-1). The ring is closing earlier, but after p-1 steps we have made multiple complete loops and are at the 1 regardless. This statement is also known as Fermat’s little theorem

Note that in our example of p=7 above we immediately find that the maximum length is 6 = 2*3 in prime decomposition. Then we may immediately conclude that all square numbers close after 3 steps only, all cubed numbers close after 2 steps and all other numbers after 6 steps. This also implies that in this ring square roots have 2 solutions, third roots have 3 solutions, and all other roots are unique.

This is the situation for prime quotient rings. It is significantly more complex for non-prime numbers and I will not provide the entire calculation. But let us consider a quotient ring to a base q = n*m as the prime decomposition.

The first conclusion is that numbers that are coprime to q, remain coprime also after exponentiation and numbers not coprime remain not coprime. The rings generated by these numbers thus run over distinct sets of elements.

For the coprimes the longest possible ring is therefore n*m-(n-1)-(m-1)-1=(n-1)(m-1), removing all numbers that are not coprime and the zero. In fact it can be shown that the rings may close earlier and the actual maximum length is the Least Common Multiple (LCM) of n-1 and m-1, because shared prime factors cause the ring to close early. But (n-1)(m-1) can always be divided by the LCM, so the difference is not important for the generalisation of Fermat's little theorem.

The numbers not coprime to n*m do not have an inverse. The generated exponent ring thus does not include the 1. This can also be seen from the statement that they can only run over the set of non coprimes, while the 1 is a coprime to all numbers. But interestingly it can also be shown that the ring will close after LCM(n-1,m-1) steps. It usually closes much earlier, but the required number of steps is a divisor of the LCM.

How can such a ring close if it does not include the 1? Simply because for the non-coprimes there are numbers such that a * b = b where a is not 1. An example is the quotient ring generated by 6 = 2*3 in the prime decomposition. The maximum length of rings is the LCM(1,2) = 2.
The only coprime number is the 5 generating 5 → 1 ↪ 5, with a predicted length of 2.
All other numbers share a prime factor with 6 and close at either 2 or 1 step (a divisor of the LCM of 2).

• 2 → 4 ↪ 2
• 3 ↪ 3
• 4 ↪ 4

In case of a base with a more complex prime decomposition this generalises to the LCM(all prime bases - 1).
Note that for a prime this is the LCM(prime - 1) = prime - 1, as already stated in Fermat’s little theorem.
While we cannot get such a nice result as Fermat’s little theorem anymore since there does not exist an inverse for all possible elements, we may still conclude that for any number in any quotient ring

nᵏ⁺¹=n (mod q) where k = LCM(all prime factors of q - 1).
k is also called the Euler totient function and in fact there is a slight improvement possible using the Carmichael function instead, but this is not essential.

How is all this useful? The quotient rings already remove the ordering from the natural numbers, but calculations are still simple to perform in both directions. The structure of quotient rings is very predictive and simple (1 → 2 → 3 → 4 → 5 → 6 → 0 ↪ 1). But building exponent rings on top of quotient rings reshuffles the elements in a very non-trivial way. While there is still a lot that can be learned about them, for large numbers the ring has the be constructed by brute force. Computations are simple in one way, but hard to invert.

For example mᵃ=c (mod q) is easy to compute given m and a. But what is a given m and c ? For real numbers it would be the logarithm, thus it is called the discrete log problem. In order to find out one has to try (almost) all possible exponents and the value of c gives no real insight into the size of a. For natural numbers on the other hand this problem is not very hard as a can be inferred quickly just from the size of c using the organised structure of the natural numbers!

This provides a one-way trapdoor function and is extremely useful for cryptography. In fact some cryptographic algorithms are based on exactly this. More on this in my next post. For now let me provide an example to illustrate this point.

What is 50³⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰³ (mod 221) ?
Since the computer will not tell you many people will stop right there, but in the post above there is all the necessary information to compute this in a few steps. This is only the easy part.

The same computation is extremely hard to invert.
Which exponent did i use to find 55ˣ=217 (mod 221)?
This is a discrete log problem and in contrast to the case above there is no magic shortcut. It can only be solved since the involved numbers are (very) small so that brute-forcing it is an option.

I will set up a small steem-bounty to find the answers in order to encourage playing around a bit with these examples and getting familiar with the rings.

For big bases the first task does not really get much more difficult, but the second quickly becomes computationally unfeasible.