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.

Leave a Reply

Your email address will not be published. Required fields are marked *