Harristotelian Logic

I've noted a fundamental result in modular arithmetic around studying the simple system of equations:

f_1 = a_1*k mod N thru f_m = a_m*k mod N

Specifically by noting that multiplying them together gives:

f_1*...*f_m = a_1*...*a_m*k^m mod N, but ADDING them together gives:

f_1+...+f_m = (a_1 + ...+ a_m)k mod N

Note that the a's are what I call control variables, which can be set to ANY non-zero value.

Remarkably enough that simple result allows one to handle k^m = q mod N through integer factorization.

You can solve for k, when m, q and N are known, or for m, when k, q and N are known, and it is the latter I'll consider in more detail in this post.

Since the a's are control variables their value can be set to some extent, with m degrees of freedom. To handle discrete logarithms entirely, over any m, I need to remove less than m of those degrees of freedom and do so with the following equations:

a_1*...*a_m = q mod N

and

a_1+...+a_m = m mod N

Then k^m = q mod N, and f_1*...*f_m = a_1*...*a_m*k^m mod N, with substitutions gives me:

f_1*...*f_m = q^2 mod N

and f_1+...+f_m = (a_1 + ...+ a_m)k mod N with substitution gives:

f_1+...+f_m = mk mod N

But so far I've removed only 2 degrees of freedom from the a's, so assume that for some unknown number m-c of the f's that the a's are simply the modular inverse of k, then for that number the f's simply equal 1, giving me:

f_1+...+f_c + m - c = mk mod N

Which allows me to solve for m, with:

m = (k-1)^{-1}(f_1+...+f_c - c) mod N

(If k-1 is not coprime to N, then factors in common would be divided off before the modular inverse operation, which actually gives another check for finding useable factors.)

Notice that finding factors then becomes just a matter of considering solutions:

f_1*...*f_m = q^2 mod N

where m-c of the factors have been set to 1. So the reasons for that substitution is clear.

Notice that c is found dynamically from the count of non-unit factors of q^2 mod N.

Here's an example, solve for m, where:

2^m = 13 mod 23

so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 = 8 mod 23.

And I found a solution with f_1*...*f_m = 54, and

f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3

so c=4, and

m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4 = 7

And 2^7 = 128 = 13 mod 23.

Notice that the method then gives you the number c from factoring numbers q^2 mod N. The means mathematically that c of the a's have been set by the algebra itself to cancel out k, with the modular inverse, which is how this approach eliminates the advantage of a large m—the math simply handles it for you.

And that is the basic research showing how a simple set of modular equations can lead to an approach to solving discrete logarithms through integer factorization. It is not clear at this time how practical it can be made to be.

However, I would assume that it is a method that cannot simply be ignored as the idiot mutterings of some "crackpot". But if any of you do, I hope you pay the appropriate consequences if it turns out to be important. Paying as high a price as your world requires of you. No matter what the price might be.