Wednesday, June 30, 2010


Discrete logs result, sum of the factors upper bound?

I've noted a way to solve discrete logarithms through factoring:

q^2 mod N

where with

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

you can find m simply enough from:

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

where c is the count of factors in your factorization of q^2 mod N, where prior posts explain from where the equations derive.

In a prior post I try to set an upper bound for q^2 mod N, which at approximately 4N^2 is rather high, but there may be many reasons why solutions will not approach that upper bound where I noticed one while playing with small numbers, which is that the sum of the factors of q^2 mod N, can be a constraining factor.

Consider 2^m = 60 mod 107. That gives f_1*...*f_m = q^2 mod N = 69 mod 107, and I've been adding N for my first try at a solution so started with 176, which factors as 2*2*2*2*11, and those sum to give 19 but minus 5, I get 14, which may be close, but it's not right. So I kept going, and quickly noticed that the sum of the factors were not getting closer but further away.

Worrying a bit but knowing the underlying mathematics is solid, I went back to 69, and finally noticed: 6+9-2 = 13.

2^13 = 60 mod 107

Intriguingly, with a larger prime relative to the answer, the factors grew rapidly, so that the sum of the factors was way beyond m fairly quickly, which forced early solution?

But still I'd think there'd be other answer with small primes. But of course the math also has the ability to use a large m, which still works, though it's not the smallest one that I'd prefer.

<< Home

This page is powered by Blogger. Isn't yours?