Mathematics, Number Theory

Modular square roots of compound integers

The title of this post might be misleading. While solving the following congruence for x is an interesting problem:

x2a (mod m)

this is not the objective of this post.

Instead, my goal is to show a method to find, for a given solution x to the above congruence, where x and a are positive integers, where m is an odd positive integer, and where x is coprime with m, what other solutions also exist.

It should already be fairly obvious that for a value of x that is a solution to the above congruence, -x is also a solution because x2 = –x2. This solution is trivial.

First, let’s consider when m is prime. For this case, we will use p instead of m to show that p is prime. If we have the following congruence:

x2a (mod p)

then x and -x are the only modular square roots of a, mod p.

Now, let’s consider the case when m is compound. If m is an odd compound integer with at least 2 distinct prime factors, and d is an integer divisor of m greater than 1 and less than m, and if we say that e = m/d, then e is also a an integer divisor of m and e is greater than 1 and less than m. We will now restrict the selection of d such that d and e must be coprime. We will see shortly why this is necessary.

In summary, we now have:
1 < d < m
1 < e < m
d | m
e | m
gcd(d, e) = 1
m = de

The Chinese Remainder Theorem will show that the only solution for the following system of linear congruences:

yx (mod d)
yx (mod e)

is this congruence:

yx (mod m)

Now, watch what happens when we solve the following system of linear congruences:

yx (mod d)
y-x (mod e)

The solution to this system of linear congruences is slightly more complicated. Let’s use the Chinese Remainder Theorem to solve this, but we’ll write out the steps so that the result is clear. First, we’ll transform the first congruence into an equation:

y = td + x

where t is some integer. Now we can substitute the value of y into the second congruence:

td + x ≡ –x (mod e)

We can subtract x from both sides, which gives us this:

td ≡ -2x (mod e)

Now, if we define i = d-1 (mod e) and multiply both sides of the congruence by i, we get this:

t ≡ -2ix (mod e)

We can now transform this congruence into an equation:

t = se – 2ix

Where s is some integer. Now if we substitute the value of t into the earlier equation, we get this:

y = d(se – 2ix) + x
= sde – 2idx + x
= sm – 2idx + x
= sm + x – 2idx

Now we can transform this back into a congruence, mod m:

yx – 2idx (mod m)

Let’s now see what we get when we evaluate y2, mod m:

y2 ≡ (x – 2idx)2 (mod m)

If we multiply out the expression on the right hand side of this congruence we get this:

y2x2 – 4idx2 + 4i2d2x2 (mod m)

From the second and third terms of the expression on the right hand side of this congruence, we can factor out 2idx:

y2x2 + 2idx(2idx – 2x) (mod m)

Let’s focus on the second term of the expression on the right hand side of this congruence. Clearly, because d is part of the term outside the parenthesis, the entire term is an integer multiple of d. Let’s look carefully at the terms inside the parenthesis. Remember that i is the modular multiplicative inverse of d, mod e. Therefore, if we evaluate these terms, mod e, we get this congruence:

z ≡ 2idx – 2x (mod e)

Because i is the multiplicative inverse of d, mod e, id is congruent with 1, mod e, so we can eliminate the id from this congruence. Therefore we have this:

z ≡ 2x – 2x (mod e)

And from this we can conclude:

z ≡ 0 (mod e)

This means that 2idx – 2x is an integer multiple of e.

Let’s look again at the congruence above. Because the term outside the parenthesis is an integer multiple of d and the terms on the inside the parenthesis evaluate to an integer multiple of e, we can conclude that the product of 2idx(2idx – 2x) is an integer multiple of m, which means that entire term is congruent with 0, mod m, and it can be removed from the congruence. Finally, we have this:

y2x2 (mod m)

Now to show that y is a non-trivial modular square root of a, it only remains to show that y ≢ ±x, mod m. Remember that this is the congruence that defines y, mod m:

yx – 2idx (mod m)

To show that yx, mod m, it is sufficient to show that 2idx ≢ 0, mod m. To show this, we will first assume that 2idx is congruent with 0, mod m, and then show that this leads to a conclusion that is impossible. Our assumption is this:

2idx ≡ 0 (mod m)

Because 2x divides both sides of the congruence and because m is odd and x is coprime with m, we can divide both sides of the congruence by 2x, which gives us this:

id ≡ 0 (mod m)

Now, because d divides both sides of the congruence and d divides m, we can divide it out of both sides of the congruence and the modulus, which gives us this:

i ≡ 0 (mod e)

However, this is impossible because i is the modular multiplicative inverse of d, mod e. If i ≡ 0, mod e, then di ≡ 0, mod e. However, by definition, di ≡ 1, mod e, which means that i ≢ 0, mod e. Therefore, we can conclude that yx, mod m.

To show that y ≢ –x, mod m, it is sufficient to show that 2idx ≢ -2x, mod m. To show this we will again begin by assuming that this congruence exists and show that it leads to a conclusion that is impossible. Our assumption is this:

2idx ≡ -2x (mod m)

Because we have defined m as an odd integer, m is not divisible by 2, and because we defined x and m to be coprime, we can divide both sides of the congruence by 2x, which gives us this:

id ≡ -1 (mod m)

However, we know that m is divisible by d and we know that d > 1, because that’s how we defined d to begin with. Given that, there is no multiple of d that could be 1 less than m. Therefore, we must reject the assumption we made and we can say that 2idx ≢ -2x, mod m. We can conclude from this that y ≢ ±x, mod m.

Let’s follow this discussion with a concrete example. As an example, I will use my favorite semi-prime, 66659, which is the product of the primes 191 and 349. In my last several posts, I described methods for finding the non-trivial modular square roots of 1, so why not use the value 1 for x? If x is 1, obviously a is also 1. We will define the terms like so:

m = 66659
d = 349
e = 191
x = 1
a = 1

Now, let’s solve for y. The only really complicated part of finding y is calculating the modular square root of d, mod e. Notice that this doesn’t involve x. Once we find the non-trivial modular square roots of 1, mod m, we can find all others corresponding to the pair of divisors of m which are d and e just by multiplying the result by x. For this example, the multiplicative modular inverse of 349, mod 191, is 81. Therefore, the non-trivial modular square roots of 1 are:

y ≡ 1 – (2*81*349*1) (mod 66659)
y ≡ (2*81*349*1) – 1 (mod 66659)

which evaluates to:

y ≡ 10122 (mod 66659)
y ≡ 56537 (mod 66659)

Let’s check our work. Let’s find out if 101222 and 565372 are congruent with 1, mod 66659.

101222 = 102454884 ≡ 1 (mod 66659)
565372 = 3196432369 ≡ 1 (mod 66659)

This confirms that 10122 and 56537 are non-trivial modular square roots of 1, mod 66659.

Let’s try a different value for x, to confirm that the other non-trivial modular square roots, mod 66659, are just multiples of the non-trivial modular square roots of 1. Let’s try the value x = 947. Now we have:

m = 66659
d = 349
e = 191
x = 947
a = 30242

y ≡ 947 – (2*81*349*947) (mod 66659)
y ≡ (2*81*349*947) – 947 (mod 66659)

which evaluates to:

y ≡ 53297 (mod 66659)
y ≡ 13362 (mod 66659)

Let’s check our work again.

532972 = 2840570209 ≡ 30242 (mod 66659)
133622 = 178543044 ≡ 30242 (mod 66659)

This confirms that 53297 and 13362 are non-trivial modular square roots of 30242, mod 66659.

Recall that we defined d such that it must be coprime with e. This is necessary because if we choose a divisor, d, of m that is not coprime with e = m/d, then the modular multiplicative inverse of d, mod e, would not exist, and vice-versa.

Speaking of vice-versa, we solved for y using the Chinese Remainder Theorem from this system of linear congruences:

yx (mod d)
y-x (mod e)

What happens if we switch x and –x, like so:

y-x (mod d)
yx (mod e)

The result is we get the same result, but negated:

y ≡ 2idxx (mod m)
yx – 2idx (mod m)

The same is also true if we solve for y in terms of e rather than d. If we say that j is the modular multiplicative inverse of e, mod d, then the following congruences can both be derived by solving for y in terms of e:

yx – 2jex (mod m)
y ≡ 2jexx (mod m)

Mathematics, Number Theory

Semi-prime modular square root of 1 revisited again

In my last post, I described a way to use the matrix, M, corresponding to the coefficients u and v that can be used to generate a primitive Pythagorean triple, to find the non-trivial modular square root of 1 for the odd leg of the triple. For reference, we have this:

m = pq = u2v2

where p and q are odd prime integers and p > q. Knowing the values of p and q, we can easily obtain u and v like so:

u = (p + q) / 2
v = (pq) / 2

We can trivially identify that

±12 ≡ 1 (mod m)

But given that m is the product of p and q, there should be two other modular square roots of 1. In my last post, I showed how, given the matrix that will generate the coefficients u and v, we can calculate the non-trivial modular square roots of 1, mod m, using two of the coefficients of that matrix. In the post prior to that, I described how to obtain the matrix from the factorization of m by following the path to the corresponding triple in the tree of primitive Pythagorean triples. I showed that if the matrix, M, is this:

M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}

then the non-trivial modular square root of 1, mod m, can be obtained easily like so:

r2 = m(a2c2) + 1

and so the non-trivial modular square roots of 1, mod m, are r and -r.

I’d like to revisit this once again to show that it is not necessary to obtain the complete matrix, M, to determine the values of the two matrix coefficients, a and c, that can be used to obtain the non-trivial modular square root of 1, mod m. I’d like to thank Nikhilesh Chamarthi for providing me with this solution. As Nikhilesh pointed out to me, the coefficients u and v can be generated by multiplying the vector [2, 1] by the matrix M, which gives us this:

u = 2a + b
v = 2c + d

If we solve these equations for b and d, respectively, we get this:

b = u – 2a
d = v – 2c

We know that the determinant of the matrix, M, is either 1 or -1, which gives us this:

adbc = ±1

If we substitute the values for b and d here, we get this:

a(v – 2c) – c(u – 2a) = ±1

If we multiply out across the parenthesis, we get this:

av – 2accu + 2ac = ±1

which can then be simplified to this:

avcu = ±1

Now what we have is a linear Diophantine equation which can easily be solved using Bézout’s identity via the extended Euclidean algorithm, given that u and v are coprime.

In practice, this is a significant improvement over the method I proposed of finding the path to the matrix M by traversing the tree of Pythagorean triples to its root using u and v. While the path will typically have a depth that is logarithmic with respect to m, the path could have a depth that approaches m. Using the extended Euclidean algorithm instead is strictly better. Because we know the values of u and v, we can easily solve for a and c without traversing the path to M through the tree. In fact, once we have the values of a and c, we can easily calculate b from a and u and we can easily calculate d from v and c.

While we might assume that we have to solve Bézout’s identity twice, once for the case where the determinant is 1 and once for the case where the determinant is -1, this isn’t necessary. It turns out that if we get it wrong, both coefficients will be negated. Since the method for finding the non-trivial modular square root of 1, mod m, involves squaring both a and c, it doesn’t matter if we get their signs correct.

Thanks again, Nikhilesh, for this insight.