Mathematics, Number Theory

Semiprime modular square root of 1

There is already a well-known efficient algorithm to find the modular square root of a number that is quadratic residue when the factorization of the modulus is known. I believe I’ve found a new way of finding the modular square root for the special case when the quadratic residue is 1 and the modulus is an odd semiprime with a known factorization of two distinct odd primes. The interesting thing about this method is not that it’s possible to find the modular square root of 1 but in how this method works.

Note that for a semiprime, there will always be exactly four modular square roots of 1. Since 1 is already the square of itself, there are two square roots of 1 that are trivial, being 1 and -1. The challenge is to find the other two. Since 1 is square and less than any semiprime, it is quadratic residue. Therefore, there must be two other modular square roots of 1, mod m.

In fact, I don’t have a proof to show that the method described here works in all cases, but I’ve verified that it works for thousands of cases and haven’t yet found a counter-example. I’d love to someday find a proof but I don’t expect that it will be worth my time to search for one.

The basis for this method is the tree of primitive Pythagorean triples. The entire tree can be generated from arbitrary combinations of the following 2×2 matrices:

A = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}, B = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}, C = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}

Every primitive Pythagorean triple in the tree can be generated using a pair of coefficients, u and v, where u and v are coprime and have opposite parity, meaning one is even and the other is odd, and where u > v. Every possible pair of positive integers meeting these criteria will generate a unique Pythagorean triple with sides a, b, and c using the following equations:

a = u2v2
b = 2uv
c = u2 + v2

The root of the tree is the well known primitive Pythagorean triple 3, 4, 5, and is generated using the coefficients u = 2 and v = 1.

Given a semiprime, m, which is the product of two primes, p and q, where p > q, there exists a primitive Pythagorean triple where m is the length of the odd non-hypotenuse side of the triangle. In fact, there are exactly two such primitive Pythagorean triples. In general, for any positive odd number greater than 1, there is exactly one primitive Pythagorean triple with the odd non-hypotenuse side with that length for every distinct factorization pair, without respect to order, of that number where the two factors are coprime. Given this, there are exactly two primitive Pythagorean triples where the odd non-hypotenuse length is the semiprime m, corresponding to the two distinct pairs of factors of m, which are:

m = p * q
m = m * 1

For the case of m = m * 1, u = (m + 1) / 2 and v = (m – 1) / 2.

For the case of m = p * q, u = (p + q) / 2 and v = (pq) / 2. It is this case that will be useful to help us find the square root of 1, mod m.

To prove that u and v are, in fact, coefficients that will generate a primitive Pythagorean triple, it is necessary to show that u and v are both coprime and that they have opposite parity.

To show that u and v are coprime, let’s consider the case where there is some integer n that divides both u and v. We can then rewrite u and v like so:

u = s * n
v = t * n

where s and t are integers. We can then substitute these into the equations for u and v like so:

s * n = (p + q) / 2
t * n = (pq) / 2

If we solve the first equation for p we get this:

p = 2(s * n) – q

Now if we substitute that equation for p in the second equation, we can reduce the second equation to this:

q = n(st)

We know that n divides both sides of the equation, so therefore n must divide q. Because we defined q to be a prime integer, n can only be 1 or q. However, if we perform the substitutions in the opposite direction, we will arrive at this equation:

p = n(s + t)

Again, we know that n divides both sides of the equation, so therefore n must divide p. Because we defined p to be a prime integer, n can only be 1 or p. However, we’ve already established that n must be either 1 or q and we have defined p > q which means that n can not be both p and q so it must be neither. The only remaining possibility is that n is 1, which means that u and v are coprime.

To show that u and v are opposite parity is easy as well. First, we’ll demonstrate the u and v are both integers. Because p and q are both odd primes, they are both congruent with 1, mod 2. According to the rules of modular algebra, we know that these congruences are true:

p + q ≡ 1 + 1 ≡ 0 (mod 2)
pq ≡ 1 – 1 ≡ 0 (mod 2)

Therefore, both the sum and difference of p and q are even and therefore half their sum and difference are integers.

We’ll use the same technique to show that they have opposite parity. Because we know that p and q are odd integers, we know that they are both congruent with either 1 or 3, mod 4, because if they were congruent with 0 or 2, mod 4, they would not be odd. There are a limited number of possible combinations which I will enumerate here:

p + q ≡ 1 + 1 ≡ 2 (mod 4) and pq ≡ 1 – 1 ≡ 0 (mod 4) or
p + q ≡ 1 + 3 ≡ 0 (mod 4) and pq ≡ 1 – 3 ≡ 2 (mod 4) or
p + q ≡ 3 + 1 ≡ 0 (mod 4) and pq ≡ 3 – 1 ≡ 2 (mod 4) or
p + q ≡ 3 + 3 ≡ 2 (mod 4) and pq ≡ 3 – 3 ≡ 0 (mod 4)

In all four possible scenarios, either p + q is congruent with 2, mod 4, and pq is congruent with 0, mod 4, or else p + q is congruent with 0, mod 4, and pq is congruent with 2, mod 4. If p + q is congruent with 2, mod 4, then u is congruent with 1, mod 2, meaning u is odd. If p + q is congruent with 0, mod 4, then u is congruent with 0, mod 2, meaning u is even. The same logic applies to v. Since p + q and pq can’t both be congruent with 0, mod 4, and they can’t both be congruent with 2, mod 4, u and v can’t both be even and they can’t both be odd.

We’ve now established that u and v are coefficients that correspond to a primitive Pythagorean triple. To use this information to find the non-trivial modular square roots of 1, we want to find the path taken to find that primitive Pythagorean triple corresponding to u and v.

To do this, we will use the inverses of the matrices defined above which are these:

A^{-1} = \begin{bmatrix} 0 & 1 \\ -1 & 2 \end{bmatrix}, B^{-1} = \begin{bmatrix} 0 & 1 \\ 1 & -2 \end{bmatrix}, C^{-1} = \begin{bmatrix} 1 & -2 \\ 0 & 1 \end{bmatrix}

Starting with the coefficients u and v, we can try pre-multiplying the two coefficients as a column vector with each of the three inverse matrices. Two of the results will be invalid because they will have non-positive coefficients. The remaining one is the true parent along the path of the tree of Pythagorean triples leading to that pair of coefficients. Repeating this process will eventually lead to the root of the tree with the coefficients 2, 1. At that point, the complete path to the Pythagorean triple corresponding to m will have been found.

Now, if we follow the same path but in reverse, starting with the identity 2×2 matrix and pre-multiplying the corresponding matrix A, B, or C, above, we will arrive at a 2×2 matrix that will produce a different (in most cases) Pythagorean triple. The exception is when the path to the original Pythagorean triple is reflexive, for example the path ABCBA, in which case following the reverse path will lead to the original triple.

Now comes the trick. It turns out that the bottom two coefficients of this 2×2 matrix can be used to find the non-trivial modular square roots of 1, mod m. If we assign variables to the matrix coefficients like so:

\begin{bmatrix} w & x \\ y & z \end{bmatrix}

Then, like magic, we can calculate the two non-trivial modular square roots of 1, mod m, like so:

(m * (3y + z) * (y + z))2 ≡ 1 (mod m)

Let’s look at a concrete example, for which I will use my favorite semiprime, 66659, which is the product of the primes 349 and 191. Here are the coefficients we start with:

m = 66659
p = 349
q = 191
u = 270
v = 79

Using the method described above, we find that the path to the Pythagorean triple with odd non-hypotenuse leg of length 66659 is this:

CCBACAAC = \begin{bmatrix} 41 & 188 \\ 12 & 55 \end{bmatrix}

If we follow the reverse of this path, we arrive at this 2×2 matrix:

CAACABCC = \begin{bmatrix} 79 & 112 \\ 12 & 17 \end{bmatrix}

Using the bottom two coefficients in this matrix we can generate the two non-trivial modular square roots of 1, mod 66659:

(66659 * ((3 * 12) + 17) * (12 + 17))2 ≡ 101222 ≡ 1 (mod 66659)
(66659 – 10122)2 ≡ 565372 ≡ 1 (mod 66659)

It is interesting to note that the u coefficient obtained by the matrix resulting from following the reverse path of the original Pythagorean triple will be identical to the u coefficient corresponding to m. In this example, the u and v coefficients generated by the matrix generated using the reverse path are 270 and 41.

I don’t have a good explanation for why this method works, much less a proof. I can therefore, obviously, not be certain that it works for all semiprimes. Given that the problem of finding modular square roots is already known in the general case, this method is not particularly useful. The point of presenting this method is mostly just to illustrate an interesting relationship between semiprimes and the tree of Pythagorean triples.

Leave a Reply

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