Modular arithmetic is very important to cryptography. It is arithmetic that allows us to achieve a set of operations over a set of numbers that wrap around a circle.
While modular addition, subtraction, and multiplication are easy to understand, the modular division is somehow tricky. The main reason is that the modular division doesn't have always a solution, and sometimes it gives multiple solutions!
To explain it clearly, I present two approaches to calculating the modular division. The first approach uses the modular multiplication table, while the second approach uses the successive subtraction method. Both approaches allow us to see whether there are zero, one, or multiple solutions to the modular division. However, none of these approaches are efficient to calculate the modular division of big numbers.
The objective of this article is to explain when the modular division can have zero, one or multiple solutions. The article shows also that when multiple solutions to the modular division are possible, Python interpreter returns only one of them.
To illustrate the idea of modular division, I will use the set of integers modulo 6 as an example. I use also SageMath tool to generate the multiplication and the addition tables for this set: ZZ6={0,1,2,3,4,5}
Here is the command to generate the set of integers modulo 6:
sage: ZZ6=Integers(6)
ZZ6.multiplication_table() method allows giving the multiplication table for modulo 6 integers.
sage: ZZ6.multiplication_table("digits")
* 0 1 2 3 4 5
+------------
0| 0 0 0 0 0 0
1| 0 1 2 3 4 5
2| 0 2 4 0 2 4
3| 0 3 0 3 0 3
4| 0 4 2 0 4 2
5| 0 5 4 3 2 1
From the multiplication table, we can see that (5 mod 6) * (4 mod 6) is equal to (2 mod 6). We can verify this using Python (sage is based on Python):
sage: (5%6*4%6)%6
2
The modular multiplication can be represented as a set of successive modular additions. For example, the previous multiplication operation can be achieved by adding (5 mod 6) to itself 4 times.
sage: (5%6+5%6+5%6+5%6)%6
2
Similarly, the modular division can also be represented by a set of successive subtraction as is the case in normal integer division.
However, we might have different possibilities for the outcome of the modular division. Sometimes, we have one solution, sometimes we have multiple solutions and sometimes we don't have any solution.
We know that the modular division has only one solution when the divisor has a modular multiplicative inverse. For example, (5 mod 6) has a modular multiplicative inverse because (5 mod 6) * (5 mod 6) is equal to (1 mod 6). So we are sure that any division by (5 mod 6) will exist and there is only one solution.
However, (3 mod 6), (4 mod 6), and (2 mod 6) have no modular multiplicative inverses. It means that they might have either multiple solutions or no solution. We can use the successive subtraction method to calculate the modular division for them. We consider that there is a solution if we can reach to (0 mod 6) after a set of successive subtraction operations. If we are not able to reach (0 mod 6), it means that there is no solution to our division in mod 6.
But let’s first calculate the division for a number that has a modular multiplicative inverse. Because (5 mod 6) has a modular multiplicative inverse, (4 mod 6) / (5 mod 6) is equivalent to (4 mod 6) * (5 mod 6). This gives us the following result (we can also check it from the multiplication table)
sage: (4%6*5%6)%6
2
We can use Python to verify the modular division:
sage: (4%6/5%6)%6
2
Let's prove now that there is only one solution through the successive subtraction method, by testing all the possible solutions from 1 to 5.
sage: (4%6-5%6)%6
5
sage: (4%6-5%6-5%6)%6
0
sage: (4%6-5%6-5%6-5%6)%6
1
sage: (4%6-5%6-5%6-5%6-5%6)%6
2
sage: (4%6-5%6-5%6-5%6-5%6-5%6)%6
3
Thus the only solution that allowed us to obtain ( 0 mod 6 ) was when we subtract two times (5 mod 6) from (4 mod 6). So there is only one solution to our modular division.
Let's now check the division by (3 mod 6). We can not divide using the modular multiplicative inverse because it doesn't exist.
If we try with Python.
sage: (4%6/3%6)%6
We get the following error
ZeroDivisionError: inverse of Mod(3, 6) does not exist
Now let's try the successive subtraction method. Because we don't know the solution, we will try all the possible subtractions. In our example, we know that the result of the division must be any value between 1 and 5 (mod 6). It means that we have a maximum of 5 subtraction operations to test if there is a solution to our division.
sage: (4%6-3%6)%6
1
sage: (4%6-3%6-3%6)%6
4
sage: (4%6-3%6-3%6-3%6)%6
1
sage: (4%6-3%6-3%6-3%6-3%6)%6
4
sage: (4%6-3%6-3%6-3%6-3%6-3%6)%6
1
None of the possible results allowed us to reach the value (0 mod 6). This means that this division has no solution in mod 6.
Let's now confirm our conclusion using the multiplication table. Our division can be re-written in this way :
Y=(4 mod 6) / (3 mod 6) <==> (3 mod 6) * Y=(4 mod 6)
It means that all the numbers that we can multiply by (3 mod 6) and give us the result (4 mod 6) are possible solutions to our division. Let's have a look again at our multiplication table and see the possible numbers that can satisfy this equation.
* 0 1 2 3 4 5
+------------
0| 0 0 0 0 0 0
1| 0 1 2 3 4 5
2| 0 2 4 0 2 4
3| 0 3 0 3 0 3
4| 0 4 2 0 4 2
5| 0 5 4 3 2 1
We can see that none of the possible multiplication results gives the value (4 mod 6). It means there is no solution to our equation.
Let's now try another division
(2 mod 6) * Y = (4 mod 6)
We know that (2 mod 6) has no modular multiplicative inverse, but we need to know whether there are multiple solutions to our division or not.
We can see clearly that there are multiple solutions to our equation (2 mod 6) * Y=(4 mod 6), which are (2 mod 6) and (5 mod 6) .
* 0 1 2 3 4 5
+------------
0| 0 0 0 0 0 0
1| 0 1 2 3 4 5
2| 0 2 4 0 2 4
3| 0 3 0 3 0 3
4| 0 4 2 0 4 2
5| 0 5 4 3 2 1
Let's check this using the successive subtraction method.
The first solution (2 mod 6):
sage: (4%6-2%6-2%6)%6
0
The second solution (5 mod 6):
sage: (4%6-2%6-2%6-2%6-2%6-2%6)%6
0
This confirms that this equation has two solutions. However, if we check with Python, it gives us only one solution.
sage: (4%6/2%6)%6
2
As a developer, we need to be careful about this fact. However, in cryptography, we are only interested in the numbers that have modular multiplicative inverses. In this case, the modular divisions return only one solution.
Comments
Post a Comment