Harristotelian Logic

I've noted a way to solve for m, when k^m = q mod N, through integer factorization, which is then an approach to solving discrete logarithms in a prior post. In this post I'll explain when the equations MUST work, where a simple analysis can be done trivially using methods familiar to those who've solved simultaneous equations in regular algebra.

Here are relevant equations without the complete detail explaining them all of the prior post which should be read for reference:

Everything follows from use of a simple system of equations:

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

Two important constraining equations:

a_1*...*a_m = q mod N

and

a_1+...+a_m = m mod N

Resultant equations:

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

and

f_1+...+f_m = mk mod N

(These are arbitrary constraints that I used. There may be others that are of practical use.)

Now 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, which allows me to solve for m with:

(k-1)*m = (f_1+...+f_c - c) mod N

If k-1 is coprime to N, you can simply use the modular inverse to get m. Otherwise you'd to divide off common factors from both sides and then use the modular inverse with what remained.

All of which was given in my prior post, but notice I can now go back to the constraining equations for the a's with the information that some of the a's have been set to the modular inverse of k:

a_1*...*a_c*k^{-(m-c)} = q mod N, so a_1*...*a_c= q*k^{-(m-c)}

and

a_1+...+a_c + (m-c)k^{-1} = m mod N, so a_1+...+a_c = -(m-c)k^{-1} + m mod N

which means there are two simultaneous congruence equations with c unknowns:

a_1*...*a_c= q*k^{-(m-c)}

and

a_1+...+a_c = -(m-c)k^{-1} + m mod N

Using the first to substitute out a_1 into the second and simplifying slightly gives:

q*k^{-(m-c)} + a_2^2*a_3*...*a_c + a_2*a_3^2*...*a_c...+a_2*...*a_c^2 = a_2*...*a_c[-(m-c)k^{-1} + m] mod N

Notice then that with any c-2 variables set arbitrarily, the existence of the remaining one is set if a quadratic residue exists.

So for instance if c=4, then you can have a_3 and a_4 completely free variables, as long as quadratic residues exist to allow for a_2, which would indicate a 50% probability in that case if N is prime.

However, you can also further constrain one more of the a's to remove squares, for instance let a_3 = a_2^{-1} mod N, and you have:

q*k^{-(m-c)} + a_2*a_4*...*a_c + a_3*a_4*...*a_c...+ a_4*...*a_c^2 = a_4*...*a_c[-(m-c)k^{-1} + m] mod N

which allows a solution for a_2 to always exist. Which would leave with c=4, a_4 completely free.

Assuming human nature will be to look for smaller values to factor to actually use the algorithm, one can assume that

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

will be with smaller values of q^2 mod N, based on human preference, so if a_4 is completely free, and is non-unit, it would likely in many cases mean that f_4 will be 2.

If a_3 and a_4 are free then one would expect f_3 and f_4 to be 2.

With c = 4 or greater then the area to consider variability that cannot just be arbitrarily set to a convenience value is with a_1 and a_2 which could make f_1 and f_2 just about any residue mod N. Worst case they are both near N, so you'd have a size of approximately 4N^2.

So algorithms based on this method should exit within q^2 mod N less than 4N^2.

Here's the example given in my prior post, which should make more sense given the information above:

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 2 is a factor as are small primes. The method will try to fit small primes if you are using small values which is about human preference. The algebra tries to give you what you want based on the size of the numbers you are factoring.

The value of c is dynamically set by the factorization of q^2 mod N. But the results above indicate that the algebra must give you a factorization within that range which will work.

And that is what's found with a first blush basic analysis. It's not clear at this time what further information might result from more basic research. My aim at this point is to answer criticism against this approach.

Routinely posters reply requesting I demonstrate by breaking current encryption. Well, if I could do that I wouldn't need to bother posting on newsgroups now would I?

It's basic research. Early stages.