Mathematics, Number Theory

Using the congruence of exponents in integer factorization

I hope that this post isn’t anti-climactic after my last post on the recursive congruence of exponents. I suggested that the recursive congruence of exponents could be used in integer factorization. While there is potential for this, I am not going to offer the holy grail of integer factorization because I don’t have one. What I do have is an explanation of how the recursive congruence of exponents could be used, assuming a few things that are not necessarily valid.

First I’d like to discuss the objective of integer factorization. Integer factorization has very important real-world implications when you consider the RSA problem. The real challenge of integer factorization is the factorization of large semiprimes, which are, of course, the product of two large prime integers. There are no known methods of factoring large semiprimes in polynomial time.

However, given the recursive congruence of exponents, we know that repeated squaring of any integer and reducing to the least positive residue, mod n, results in a cycle. Further, the period of this cycle divides λ(λ(n)). How does this help us factor n?

Well, first consider that every quadratic residue, mod n, where n is a semi-prime, has exactly 4 modular square roots. These 4 modular square roots are always two pairs of modular opposites. For example -1 and 1 both square to 1, and 1 is a quadratic residue, mod n, for all positive values of n. If n is a semiprime, there will be some other modular square root of 1, mod n. If we call that value i, –i will also square to 1, mod n.

Let’s look at a concrete example. We’ll use my favorite semiprime, 66659, which happens to be 191 * 349. The modular square roots of 1, mod 66659, are 1, 10122, 56537, and 66658. 56537 is equal to 66659 – 10122 and 66658 is equal to 66659 – 1.

12 ≡ 1 (mod 66659)
101222 ≡ 1 (mod 66659)
565372 ≡ -101222 ≡ 1 (mod 66659)
666582 ≡ -12 ≡ 1 (mod 66659)

The reason this is useful in factoring is that if you can discover 2 non-opposite modular square roots of the same value, mod a semiprime n, then you can easily factor n. This is because the sum and difference of those 2 modular square roots will be a multiple of one of the factors of n. Because n is also a multiple of the factors of n, the factors of n are trivially obtained using the greatest common divisor function.

Let’s take a look at the example of 66659 again. We know that 1 and 10122 are both modular square roots of 1, mod 66659, and that they are not opposites, mod 66659. Therefore, their sum and difference are both multiples of the factors of 66659, which again, are 191 and 349.

10122 + 1 = 10123
10122 – 1 = 10121

gcd(10123, 66659) = 191
gcd(10121, 66659) = 349

How is this related to the recursive congruence of exponents? The relationship is that the cyclic nature of residues of repeated squaring means that we may be able to find two non-opposite modular square roots of the same value, mod n. Beginning with literally any integer, we can find a cycle. There are 3 integers which will never produce useful cycles, which are 0, 1, and -1. The cycles generated by starting with these numbers will always have length 1 so we can’t use them to find non-opposite modular square roots. However, roughly half of other starting points will give us 2 non-opposite modular square roots, and thus, allow us to factor n.

As is shown by the recursive congruence of exponents, repeated squaring will always yield a cycle and the length of the cycle will divide λ(λ(n)). For the special case of semiprimes, a cycle will be reached within 2 squares. This is because all starting points can be categorized as a quadratic residue that is a member of a cycle, a quadratic residue that is not a member of a cycle, or a quadratic non-residue. Roughly half of all starting points will be quadratic non-residues. All quadratic non-residues squared will be quadratic residues which will either be a member of a cycle of not a member. The square of a quadratic residue will always be a member of a cycle. If you can find a number, x, that is not a member of a cycle but whose square is a member of a cycle, mod n, then x and x2λ(λ(n)) will both be modular square roots of x2, mod n. For semiprimes, roughly 3 out of 4 starting points will either fall into this category or else their square will do so, though in half of the cases found, the modular square roots found in this way will be opposites.

There are, of course, some challenges to using this approach. For example, discovering λ(λ(n)) without knowing the factorization of n is not necessarily easy. In fact, if n is very large, it may be very difficult to calculate λ(λ(n)), even if you know the factorization of n. You can discover it by repeatedly squaring and looking for cycles, though there’s a roughly 5 in 8 chance that you will have to do this a second time. Additionally, λ(λ(n)) may be roughly similar in scale to the factors of n. Squaring repeatedly λ(λ(n)) times is therefore similar in time complexity as the long division factoring method, which is generally the slowest method. However, should there be a way to guess λ(λ(n)), given n, or at least guess some of the factors of λ(λ(n)), then it may, in fact, be useful. Also, while the length of all such cycles will divide λ(λ(n)), some will be much less.

Let’s take a look one more time at the example semiprime, 66659. λ(λ(66659)) is equal to 252. Squaring most integers will yield a cycle after 1 or 2 iterations that has length 252. However, take a look at the cycle formed from the starting point of 136:

1362 ≡ 18496 (mod 66659)
1849628028 (mod 66659)
80282 ≡ 56190 (mod 66659)
561902 ≡ 12565 (mod 66659)
125652 ≡ 30713 (mod 66659)
307132 ≡ 63519 (mod 66659)
635192 ≡ 60727 (mod 66659)
607272 ≡ 59331 (mod 66659)
593312 ≡ 39089 (mod 66659)
390892 ≡ 58982 (mod 66659)
589822 ≡ 9773 (mod 66659)
97732 ≡ 55841 (mod 66659)
558412 ≡ 42579 (mod 66659)
425792 ≡ 46418 (mod 66659)
464182 ≡ 11867 (mod 66659)
118672 ≡ 41881 (mod 66659)
418812 ≡ 19894 (mod 66659)
198942 ≡ 16753 (mod 66659)
167532 ≡ 28619 (mod 66659)
2861928028 (mod 66659)

From this sequence, we can see that 8028 has modular square roots of 18496 and 28619. Because 18496 and 28619 are not opposites, mod 66659, we can use their sum and difference to factor 66659:

gcd(28619 – 18496, 66659) = 191
gcd(28619 + 18496, 66659) = 349

Notice from this that our starting point, 136, is not a quadratic residue, mod 66659. Also, the first square in the sequence, 18496, while a quadratic residue, is not a member of the cycle, but its square is. Also, the length of this cycle is only 18, which both divides 252 and is far less than 252. However, generally only a small number of cycles will be so short. The fact that some cycles are much shorter than λ(λ(n)) does not mean that you are likely to find one.

While normally you would have to perform λ(λ(n)) repeated squarings to get the result of a cycle, if you know λ(λ(n)), you can take advantage of the congruence of exponents to reduce the amount of work required. To calculate modular exponents, there is an algorithm that will allow you to do so in logarithmic time with respect to the exponent value. For example, if you want to calculate:

ae (mod n)

then this algorithm will allow you to do so with O(log(e)) time complexity. Because what we are effectively calculating is a2e in this case, we can’t normally do so in less than O(e) time complexity. However, using the congruence of exponents, we know that the following congruence is true:

a2λ(λ(n))ab (mod n)

where

b ≡ 2λ(λ(n)) (mod λ(n))

Unfortunately, this means that we not only have to guess λ(λ(n)) but we also have to guess λ(n).

Let’s look at our example semiprime, 66659, again for this. λ(66659) is equal to 33060.

2252 ≡ 24796 (mod 33060)

184962252 ≡ 28619 (mod 66659)
1849624796 ≡ 28619 (mod 66659)

Remember that we found that 18496 is not a member of a cycle, mod 66659 but that its square is. To find another modular square root of 184962 by repeated squaring, we would need iterate 252 times. However, we can get the same result (28619) by just raising 18496 to the power of 24796, mod 66659, which we can do in log(24796) time complexity, or in 15 iterations.

Obviously, this is not actually a realistic factoring method. It’s interesting to see the congruence of exponents in use, however.